[프로그래머스] 체육복 문제

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

탐욕법 문제로, 여분의 체육복을 가져온 학생이 체육복을 잃어버린 학생에게 빌려줘서 최대한 많은 학생이 체육수업에 참여할 수 있도록 하는 문제입니다.

문제 정의

lost 배열: 체육복이 없는 학생 리스트
reserve 배열 : 여벌의 체육복이 있는 학생 리스트
n : 전체 학생 수
결과 : 체육 수업을 들을 수 있는 학생 수

제약조건:
1. 체육복은 자신의 앞 또는 뒤 학생에게만 빌려줄 수 있다.
2. 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있지만, 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없다.
-> 즉, lost와 reserve배열에 동일한 학생이 존재할 수 있지만, 이 학생은 다른 체육복을 빌릴 수도, 자신의 여분을 빌려줄 수도 없다는 의미입니다.

---

첫 번째 시도

알고리즘

lost를 순서대로 순회하면서 현재 학생의 앞 뒤 학생이 reserve에 있는지 확인하자!

위의 알고리즘을 C++로 작성했습니다

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    int i=0, j=0; //lost 스캔 인덱스
    
    for(i=0; i<lost.size() i++){
        if(lost[i]-1 == reserve[j]){
            j++;
        }
        else if(lost[i]-1>reserve[j]){
            j++;
            i--;
        }
        else{
            if(lost[i]+1 == reserve[j]){
                j++;
            }
            else if(lost[i]+1<reserve[j]){
                answer--;
            }
        }
    }
    
    return answer;
}

결과

위의 풀이는 제출했을 때 50%의 정확도만 받을 수 있었습니다.
분명 if문에서 잘못된게 없다고 생각했는데 낮은 점수를 받아서 gpt에게 피드백을 요청했습니다.

gpt 피드백

이 피드백을 통해 제약조건을 확인하지 않았다는 것을 발견했습니다.

1. lost와 reserve가 정렬되어있지 않으면 reserve와 lost를 크기비교하는 것이 의미가 없습니다.
2. 여벌 옷이 있는 학생이 도난을 당한 케이스를 제외하지 못했습니다..(이거는 문제를 잘 안읽어서 생긴 문제)

---

두번째 시도

피드백을 읽고 다시 알고리즘을 작성했습니다.

알고리즘

1. 두 배열의 교집합을 제거하기
2. 교집합이 제거된 배열을 각각 정렬하기
3. reserve를 순회하면서 앞이나 뒤 학생이 lost에 있다면 해당 학생을 lost에서 제거하기
   -> reserve를 순회해야 앞과 뒤 두 학생에게 중복으로 빌려주는 일이 없음

이번에는 파이썬으로 코드를 작성했습니다.

def solution(n, lost, reserve):
    answer = 0
    
    lost = set(lost)
    reserve = set(reserve)
    
    both = lost&reserve
    lost -= both
    reserve -= both
    
    lost = sorted(lost)
    reserve = sorted(reserve)
    
    for r in reserve:
        if r-1 in lost:
            lost.remove(r-1)
        elif r+1 in lost:
            lost.remove(r+1)
    
    answer = n - len(lost)
    return answer

결과

성공!
저는 set을 이용해 집합으로 만들어서 교집합을 구했지만 다른 사람들의 코드를 살펴보니 for문을 이용하는 경우가 많았습니다.