프로그래머스 문제 풀이 체육복

이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.

문제 URL 체육복

Contents

1. 문제 지문 파악하기
2. 강사님의 알고리즘 풀이
3. 구르미의 알고리즘 풀이

문제 지문 파악하기

이 문제는 얼마나 많은 학생들이 체육복을 입을 수 있느냐를 물어보는 문제입니다. 제일 중요한 것은 이것입니다.

 

• reserve에 있는 학생들, 그러니까 여벌이 존재하는 학생들은 자신의 앞,뒷 번호 학생에게 체육복을 전달할 수 있다.
• reserve, lost에 둘 다 들어있는 학생들은 체육복을 빌려주지 않는다. (어찌보면 당연한 것)

"탐욕법"은 말 그대로 그 상황에서 제일 최적의 해를 선택하는 알고리즘 패러다임입니다. 먼저 일련의 예를 들어봅시다.

 

입력 : n = 5 lost = [2, 4] reserve = [1, 3, 5]

 

이 경우, 2가지 방식으로 전달할 수 있습니다. 첫 번째로는 나보다 높은 번호를 우선적으로 주는 방법, 두 번째로는 나보다 낮은 번호를 우선적으로 주는 방법입니다.

 

(1 -> 2), (3 -> 4) (5 -> 4), (3 -> 2)

 

근데 만약 나보다 높은 번호를 우선적으로 준다면, 이 경우에 문제를 풀 수 없을 때가 생깁니다.

 

입력 : n = 5 lost = [1, 3] reserve = [2, 4, 5] 나눠주는 법 : (2 -> 3) ...

 

하지만 낮은 번호를 우선적으로 전달한다면, 이런 경우는 생기지 않습니다.

 

입력 : n = 5 lost = [1, 3] reserve = [2, 4, 5] 나눠주는 법 : (2 -> 1), (4 -> 3)

 

즉, 이 문제에서 항상 최적해를 도달하는 방식은 자신보다 낮은 번호부터 주는 것입니다.

강사님의 알고리즘 풀이

강사님은 2가지 방식을 제시하고 있습니다. 먼저 첫 번째 방식은 입력 "N의 크기가 30 이하"라는 것에 착안하여, 먼저 초기화한 후 진행하는 방식입니다. 알고리즘의 순서는 다음과 같습니다.

 

1. 먼저 N+2 크기의 배열 u을 만들고 모두 1로 초기화합니다.
2. reserve를 순회하여 존재하는 원소를 u의 인덱스로 하여 +1을 해줍니다.
3. lost를 순회하여 존재하는 원소를 u의 인덱스로 하여 -1을 해줍니다.
4. u를 1 <= i < N+1 범위만큼 순회합니다.
   1. 만약 u[i-1] == 0 && u[i] == 2 인 경우, 체육복을 나눠줍니다.
   2. 1의 조건이 아니고 u[i] == 2 && u[i+1] == 0 인 경우 체육복을 나눠줍니다.
5. 값이 0인 원소, 즉 체육복이 없는 학생의 수를 구하고 n에 빼줍니다.

왜 N+2 인 공간을 생성할까요? 그것은 배열 인덱스와 학생 번호를 맞추는 것과 동시에, 모든 요소를 접근할 때 같은 방식으로 접근하게 하기 위함입니다. 만약 N 크기만큼 배열을 만들었다면, 4번 과정을 진행할 때, 처음과 끝에 존재하는 인덱스인지를 검사해야 합니다. 위 알고리즘을 토대로 만든 코드는 다음과 같습니다.

 

def solution(n, lost, reserve):
    u = [1] * (n + 2)

    for i in reserve:
        u[i] += 1

    for i in lost:
        u[i] -= 1

    for i in range(1, n+1):
        if u[i-1] < 1 and u[i] > 1:
            u[i-1:i+1] = [1, 1]
        elif u[i] > 1 and u[i+1] < 1:
            u[i:i+2] = [1, 1]

    answer = n - len([e for e in u[1:-1] if e < 1]) 
    return answer

 

두 번째 방식은, 파이썬의 set 과 정렬을 이용하는 방법입니다. 알고리즘을 순서대로 표현하면 다음과 같습니다.

 

1. lost와 reserve의 교집합을 구합니다. (공통으로 들어있는 학생의 번호를 구함)
2. lost와 교집합의 차집합을 구합니다. (lost에만 있는 학생)
3. reserve와 교집합의 차집합을 구합니다. (reserve에만 있는 학생)
4. 3번에서 구한 집합을 정렬합니다.
5. 4번에서 구한 집합을 순회합니다. (여기서 체육복 전달이 이루어집니다.)
   1. 만약 x-1이 2번에서 구한 집합에 속할 경우, 그 원소를 삭제합니다.
   2. x-1이 없을 때, x+1을 2번에서 구한 집합에 속해 있는지 확인하고 있다면, 그 원소를 삭제합니다.
6. 5번을 통해 구해진 잃어버린 학생들의 집합의 길이를 구하고 n에 빼줍니다.

코드는 다음과 같습니다.

 

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    
    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)

    answer = n - len(l)        
    return answer

 

첫 번째 방식은 O(N)의 성능을, 두 번째 방식은 O(Nlog(N))의 성능을 보입니다. N이 작기 때문에, 2 알고리즘 모두 효율성에서 어긋나지는 않습니다. 1번 방식은 n, lost, reserve가 다 적당히 클 때 좋은 방식이고 두 번째 방식은 lost 혹은 reserve의 크기가 적을 때 효율적인 방식입니다. 또한 두 번째 방식은 파이썬 이외에 다른 언어에서는 표현하기가 쉽지는 않아 보입니다.

구르미의 알고리즘 풀이

저의 코드는 다음과 같습니다.

 

파이썬 코드

def solution(n, lost, reserve):
    # 교집합 생성
    s = set(lost) & set(reserve)
    # lost에만 있는 학생 집합 생성
    l = set(lost) - s
    # reserve에만 있는 학생 집합 생성
    r = set(reserve) - s
    
    # r 정렬 후, 낮은 번호 우선으로 체육복 지급
    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
            
    return n - len(l) 

if __name__ == '__main__':
    n = 5
    lost = [2, 4]
    reserve = [1, 3, 5]
    print(solution(n, lost, reserve))

 

CPP 코드

#include <string>
#include <vector>

#include <iostream>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    // N+2 만큼 1로 채운 배열 생성 // 0, N+1 인덱스는 계산x
    auto u = vector<int>(n+2, 1);

    // reserve에 들어있는 번호 체육복 1개 추가
    for (const auto & i : reserve) {
        u[i] += 1;
    }

    // lost에 들어있는 번호 체육복 1개 감소
    for (const auto & i : lost) {
        u[i] -= 1;
    }

    // 자신보다 낮은 번호 우선으로 체육복 지급
    for (int i=1; i<n+1; i++) {
        if ( u[i-1] == 0  && u[i] == 2) {
            u[i-1] = 1;
            u[i] = 1;
        } else if ( u[i] == 2 && u[i+1] == 0 ) {
            u[i] = 1;
            u[i+1] = 1;
        }
    }

    // 체육복 지급 못 받은 학생 수 구함
    int unavailable = 0;

    for (const auto & elem : u) {
        if (elem == 0 ){
            unavailable += 1;
        }
    }

    // 답 = N - 체육복 지급 못 받은 학생 수
    answer = n - unavailable;
    return answer;
}

int main() {
    int n = 5;
    vector<int> lost = {};
    vector<int> reserve = {};
    auto result = solution(n, lost, reserve);
    cout << result << endl;
    return 0;
}