프로그래머스 - 체육복

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

 

문제 설명

점심 시간에 도둑이 들어 일부 학생이 체육복을 도난당했다.
다행히도 여벌 체육복이 있는 학생이 있어, 체육복을 빌려줄 수 있다. 하지만, 학생들의 번호는 체격 순으로 매겨져 있기 때문에, 바로 앞번호 혹은 뒷번호 학생에게만 체육복을 빌려줄 수 있다.

전체 학생수 n명 중, 체육복을 도난 당한 학생들의 번호가 담긴 배열 lost와 여벌을 가진 학생들의 번호가 담긴 배열 reserve를 토대로, 체육복을 갖출 수 있는 학생의 최댓값을 리턴하자.

 

제한 사항

• 2 <= 전체 학생수 <= 30
• 1 <= len(lost) <= 전체 학생수
• 1 <= len(reserve) <= 전체 학생수
• 여벌 체육복이 있어야만 체육복을 빌려줄 수 있다.
  • 여벌 체육복을 가진 학생도 도난을 당할 수 있다. 이렇게 되면 해당 학생은 남은 체육복이 1개이므로, 빌려줄 수 없다.  

1. 탐색 - O(N)

최대한 많은 학생들이 체육복을 입을 수 있는 경우를 찾아야 한다. 그러기 위해서는, 각 학생마다 가지고 있는 체육복의 수를 파악할 필요가 있다.

다음 예제를 살펴보자.

n=8, lost=[2,4,6,7], reserve=[1,3,7,8]

점심 시간 이전의 학생들의 체육복 보유 현황은 다음과 같다.

1	2	3	4	5	6	7	8
2	1	2	1	1	1	2	2

점심 시간에 도둑이 든 이후 학생들의 체육복 보유 현황은 다음과 같다.

1	2	3	4	5	6	7	8
2	0	2	0	1	0	1	2

이렇게 되면, 지금 체육복을 가지고 있지 않은 학생은 2, 4 그리고 6번 학생이다.
그리고 여유 체육복을 가진 학생은 1, 3 그리고 8번이다.

2번 학생은 누구에게 체육복을 빌릴 수 있을까?
1번과 3번에게 체육복을 받을 수 있다.

1	2	3	4	5	6	7	8
2	1	1	0	1	0	1	2

만약 2번 학생이 3번 학생의 체육복을 빌렸다고 치자. 그러면 4번 학생은 누구에게 체육복을 빌릴 수 있을까? 누구에게도 빌릴 수 없다.

1	2	3	4	5	6	7	8
1	1	1	1	1	0	1	2

하지만 2번이 1번 학생의 체육복을 빌린다면, 4번 학생은 3번 학생에게 체육복을 빌릴 수 있다. 위의 상황을 보아하니 누구의 체육복을 빌리느냐에 따라 체육복의 분배가 달라질 수 있다는 것을 알 수 있다.

 

여기서 6,7,8번의 관계에 대해 주의해야 할 점이 있다.
7번은 원래 여벌을 가지고 있던 학생이었으나, 체육복을 도둑맞아 단 하나의 체육복만 남은 상황이다. 그리고 자신의 옆번호인 6번은 체육복을 가지고 있고, 또 다른 옆번호인 8번은 여벌을 가지고 있는 상태다.

7번이 6번에게 체육복을 빌려주고, 7번은 8번의 체육복을 빌려서 6,7,8번 모두가 체육수업을 들을 수 있으면 좋겠지만, 안타깝게도 이 문제에서는 이러한 동작은 허용하지 않는 것으로 보인다.
체육복이 2벌 있을 때에만 옆친구에게 빌려줄 수 있다고 생각하자.

그러면 위의 예시에서 체육복을 입을 수 있는 학생은 6번 빼고 모두이므로, 정답은 7이 된다.

그러면 이 과정을 일반화를 해야 한다. 어떻게 해야 할까?

 

맨 왼쪽의 학생, 1번부터 n번까지 탐색을 해 보자. 그리고 현재 탐색중인 학생을 i번이라고 하자.

만약 i번 학생의 체육복이 1개 이상이라면 다음 학생으로 넘어가면 된다.

만약 i번 학생의 체육복이 0개라면, 옆의 학생으로부터 체육복을 빌려야 한다. 이 때 누구의 체육복부터 확인하는 것이 좋을까?

지금까지 지나온 i-1번째 학생의 체육복부터 확인하는 것이 좋을 것이다. i번 학생까지의 체육복 수를 검사하면서, i-1번의 학생의 체육복이 여유가 남아있다는 것은, i-1번 학생은 이제 i번 학생 말고는 체육복을 빌려줄 사람이 없다는 것을 의미한다. 하지만 i+1번 학생은 i번 학생에게도 체육복을 빌려줄 수 있지만, 아직 확인해보지 않은 i+2번 학생에게도 빌려줄 여지가 있다. 그러므로, i-1번 학생의 여유 체육복을 먼저 확인해야 한다.

그러면 i-1번 학생은 체육복이 없고, i+1번 학생이 체육복이 있다면? 그 때는 i+1번 학생의 체육복을 빌려도 된다. 이 경우에도 i+2번 학생의 체육복이 없을 수도 있고, i+3번 학생도 체육복이 없어서 i번 학생이 i+1번 학생의 체육복을 빌리면 i+2번 학생은 체육복을 빌리지 못하게 될 것이다.
그렇다고 i번 학생이 양보해서 i+2번 학생이 체육복을 입으면? 어자피 i번이나 i+2번 중 한 명만이 입을 수 있는 경우다. 그리고 i+3번 학생이 여벌이 있는 경우를 생각한다면, 그냥 i번 학생이 빌려가는 편이 생각을 덜 해도 되서 간단해진다.

그러면 다음과 같은 과정을 거치면 될 것이다.

---

• 1번 학생부터 n번 학생까지 체육복 수를 검사한다. 그리고 현재 탐색하는 학생의 번호를 i번이라고 한다.
  1. 만약 i번 학생의 체육복이 1개 이상이라면 그냥 넘어간다.
  2. 만약 i번 학생의 체육복이 0개라면, 다음과 같은 과정을 거친다.
  1. i-1번 학생에 여벌이 있다면 빌린다.
  2. 만약 i-1번에게서 빌리지 못했다면, i+1번 학생에게 여벌이 있다면 빌린다.
     1. 그리고 다시 모든 학생의 체육복 수를 검사하여, 1개 이상의 체육복을 가진 학생의 수를 리턴한다.

---

 

그러면 위의 내용을 코드로 표현해보자.

 

solution.cpp

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    vector<int> suit(n+2,1);
    suit[0] = 0;    suit[n+1] = 0;
    
    for (int i=0;i<lost.size();++i)
        --suit[lost[i]];
    for (int i=0;i<reserve.size();++i)
        ++suit[reserve[i]];
        
    for (int i=1;i<=n;++i)
        if (0 == suit[i])
            if (suit[i-1] == 2)
                suit[i-1] = suit[i] = 1;
            else if (suit[i+1] == 2)
                suit[i+1] = suit[i] = 1;
    
    int answer = 0;
    
    for (int v : suit)
        if(v)   ++answer;
    
    return answer;
}

 

이 코드에서는 작은 순번부터 큰 순번대로 훑었지만, 반대로 훑어도 통과가 가능하다. 단, 이 때는 순서를 반대로 훑듯이 체육복도 반대로 큰 번호부터 확인해야 한다.