체육복

Posted on Edited on In , ,

문제정의

체육복을 도둑맞아 빌려야 하는 상황. 체육복을 빌려야 체육 수업이 가능하다. 자신의 앞이나 뒤에 있는 번호의 체육복만 빌릴 수 있는 경우, 체육 수업을 들을 수 있는 최대 학생 수를 구하는 문제이다.

문제풀이

앞에서부터 부족한 학생이 있을 때 마다 자신보다 앞에 있는 학생의 체육복을 먼저 확인한 다음 빌릴 수 없다면 뒤에 있는 학생의 체육복을 빌려보는 식으로 한다. 앞에 있는 학생의 체육복을 먼저 확인하는 이유는 자신보다 앞에 있는 학생의 경우 자신보다 뒤에 있는 학생들에게 절대 체육복을 못 빌려주기 때문이다.

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static void main (String[] args)
    {
        int n = 5;
        int[] lost = {2, 4};
        int[] reserve = {1, 3, 5};
        int answer = 0;
        int[] cnt = new int[n];
        Arrays.fill(cnt, 1);
        for(int idx : lost)
            cnt[idx-1]--;
        for(int idx : reserve)
            cnt[idx-1]++;
        for(int i = 0; i < n; i++)
        {
            if(cnt[i] > 0)
                answer++;
            else
            {
                if(i == 0)
                {
                    if(cnt[1] > 1)
                    {
                        answer++;
                        cnt[1]--;
                    }
                }
                else if(i == n-1)
                {
                    if(cnt[n-2] > 1)
                        answer++;
                }
                else
                {
                    if(cnt[i-1] > 1)
                    {
                        answer++;
                    }
                    else if(cnt[i+1] > 1)
                    {
                        answer++;
                        cnt[i+1]--;
                    }
                }
            }
        }

       System.out.print(answer);
    }

부분부분 살펴보자

1
2
3
4
5
6
7
8
9
10
int n = 5;
int[] lost = {2, 4};
int[] reserve = {1, 3, 5};
int answer = 0;
int[] cnt = new int[n];
Arrays.fill(cnt, 1);
for(int idx : lost)
    cnt[idx-1]--;
for(int idx : reserve)
    cnt[idx-1]++;

학생마다 가지고 있는 체육복의 개수를 알아내기 위해 cnt 배열을 선언한다. 초기화는 모두 1로 한다. 그리고 체육복을 도둑맞은 학생의 개수는 줄이고 여분을 가지고 있는 학생의 개수는 1 증가한다. 이 부분에서 시간이 제일 오래 걸리는 부분은 fill이 \(O(n)\)만큼 걸리기 때문에 이 부분에서 시간복잡도는 \(O(n)\)이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
for(int i = 0; i < n; i++)
{
    if(cnt[i] > 0)
        answer++;
    else
    {
        if(i == 0)
        {
            if(cnt[1] > 1)
            {
                answer++;
                cnt[1]--;
            }
        }
        else if(i == n-1)
        {
            if(cnt[n-2] > 1)
                answer++;
        }
        else
        {
            if(cnt[i-1] > 1)
            {
                answer++;
                continue;
            }
            else if(cnt[i+1] > 1)
            {
                answer++;
                cnt[i+1]--;
            }
        }
    }
}

초기 answer를 0으로 한다. 그리고 모든 학생을 보며 만약 체육복을 가지고 있다면 answer를 증가하고 넘긴다. 만약 학생이 체육복을 가지고 있지 않다면 체육복을 빌린다. 맨 앞에 있는 학생의 경우 자신보다 앞이 없으므로 뒷번호의 학생에게 밖에 빌릴 수 없다(i == 0). 맨 뒤에 있는 학생의 경우 자신보다 뒷번호가 없으므로 앞에서 밖에 빌릴 수 없다(i == n-1). 사이에 있는 학생의 경우 둘 다 빌릴 수 있다. 따라서 자신보다 앞에 있는 학생한테 체육복을 빌릴 수 있는지 확인한 후, 빌릴 수 있는 경우에 answer를 증가한다. 만약 앞에 학생한테 체육복을 빌릴 수 없으면 뒤에 있는 학생한테 빌려본다. 전체 n만큼 반복하므로 최종 시간복잡도는 \(O(n)\)이 된다.

테스트



코드를 보면 알겠지만, 약간 지저분한 느낌이 든다. 맨 첫번째 학생과 맨 뒤에 학생을 따로 처리해줘서 그런데, 이 경우 배열의 크기를 n+2로 하면 이러한 연산을 없앨 수 있다. 앞으로 코드를 작성할 때 기억해야겠다.