[프로그래머스 level1] 체육복

programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

해결방안

• 그리디 알고리즘

알고리즘

1. 전체 인원 만큼 1로 초기화 해줌

   • 모두 체육복을 가지고 있다는 가정
2. 체육복을 잃어버린 사람의 index는 -1 해줌
   • 잃어버린 사람의 경우 체육복의 갯수가 0으로 변화 됨

3. 체육복을 여벌로 가지고 있는 사람의 index는 + 1 해줌

   1. 여벌로 가지고 있는 사람의 경우 체육복의 갯수가 2로 변화 됨
4. 2번과 3번을 통해 여벌을 가지고 있으면서 도둑맞은 사람들도 다 처리 됨
5. 맨 처음 원소만 1번째에 여벌의 체육복 줄 수 있는지 확인
6. 1번째부터 마지막 n - 1번까지 여벌의 체육복을 줄 수 있는지 확인
   1. i번째 학생이 2개의 체육복을 가지고, i - 1번 학생이 체육복이 없는 경우
      1. i번째 학생이 i - 1번째 학생에게 체육복을 빌려줌
   2. i번째 학생이 2개의 체육복을 가지고, i + 1번 학생이 체육복이 없는 경우
      1. i번째 학생이 i + 1번째 학생에게 체육복을 빌려줌

핵심 팁

• 조건을 모두 고려하는 것이 중요함
• set을 이용하여 여분있는 사람중에 잃어버린 사람을 빼는 형식으로 계산을 해주어도 됨
• i 번째 학생이 여벌의 체육복을 가지고 있는지를 각각 한번씩 연속해서 비교해야함
  • 앞의 조건에서 체육복을 빌려줄 수 있으므로 각각의 조건에 대해 여벌을 가지고 있는지 개별적으로 확인해야 함
  • 뒤에 있는 학생과 비교하는 조건의 경우, i + 1 <= n - 1 이라는 조건 필요
    • i가 n - 1 이 될경우, n번째 원소가 없기 때문에 에러 발생할 수 있기 때문에 예외 처리 해줌

 

Python

def solution(n, lost, reserve):
    stu = [1] * n
    answer = 0
    for l in lost:
        stu[l - 1] -= 1
    for r in reserve:
        stu[r - 1] += 1
    # 맨 처음 원소만 미리 체크해줌
    if stu[0] > 1 and stu[1] < 1:
        stu[1] += 1
        stu[0] -= 1
    # 1번부터 카운팅
    for i in range(1, n):
        if stu[i] >= 2:
            if stu[i - 1] < 1:
                stu[i - 1] += 1
                stu[i] -= 1
        # 마지막 원소의 경우 뒤에 있는 원소 체크하지 않음
        if stu[i] >= 2 and i + 1 <= n - 1:
            if stu[i + 1] < 1:
                stu[i + 1] += 1
                stu[i] -= 1

    for i in range(n):
        if stu[i] >= 1:
            answer += 1
    print(stu)
    return answer

Java

package Programmers;

import java.util.Arrays;

public class greedy_workout_level1 {
    public static int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int arr[] = new int[n+1];
        for(int i = 0; i<lost.length; i++) arr[lost[i]]--;
        for(int i = 0; i<reserve.length; i++) arr[reserve[i]]++;
        System.out.println(Arrays.toString(arr));
        for(int i = 1; i<=n; i++){
            // 앞의 값과 비교하는것이 먼저 나와야 함
            if(arr[i] >0 && i-1 > 0 && arr[i-1] <0){
                arr[i]--;
                arr[i-1]++;
                System.out.println("after i : " + i);
            }
            if(arr[i] >0 && i<n && arr[i+1] <0){
                arr[i]--;
                arr[i+1]++;
                System.out.println("before i : " + i);
            }
        }
        System.out.println(Arrays.toString(arr));
        for(int i = 1; i<=n; i++){
            if(arr[i] >=0){
                answer++;
            }
        }
        return answer;
    }
}

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public