<프로그래머스 C++> 체육복 풀이

문제

점심시간에 도둑이 들어 일부 학생이 체육복을 도난당했다. 여벌 체육복이 있는 학생이 바로 앞번호 또는 바로 뒷번호 학생에게만 빌려줄 수 있다. 체육수업을 들을 수 있는 학생의 최댓값을 return하라.

 

제한사항

• 여벌 체육복이 있는 학생도 도난당했을 수 있으며, 이 경우 남은 체육복 하나로 자기가 입어야 해서 빌려줄 수 없다.

n	lost	reserve	return
5	2, 4	1, 3, 5	5
5	2, 4	3	4
3	3	1	2

---

문제 흐름 파악

1. lost와 reserve에 동일한 번호 처리

: 여벌옷을 자기가 입어야할 경우 (양쪽 벡터에서 제거)

 

2. 남은 reserve 학생이 인접한 lost 학생에게 빌려줌

: 왼쪽 우선 탐색

 

3. 최종적으로 수업을 들을 수 있는 학생 수를 카운트

 

핵심조건 : reserve가 정렬되어 greedy 알고리즘이 올바른 결과를 냄

 

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int arr[31];

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    
    for(int i=1; i<=n; i++)
        arr[i] = 1;
    
    // 전처리: lost와 reserve 동시에 있는 학생 처리
    for(int i=0; i<lost.size(); i++)
    {
        arr[lost[i]] = 0;
        for(int j=0; j<reserve.size(); j++)
            if(lost[i] == reserve[j])
            {
                reserve[j] = 0;
                arr[lost[i]] = 1;
            }
    }

    // 빌려주기
    for(int i=0; i<reserve.size(); i++)
    {
        if(reserve[i] == 0) continue;
        if(reserve[i]-1 >= 1 && arr[reserve[i]-1] == 0)
        {
            arr[reserve[i]-1] = 1;
            continue;
        }
        if(reserve[i]+1 <= n && arr[reserve[i]+1] == 0)
        {
            arr[reserve[i]+1] = 1;
            continue;
        }
    }
    
    for(int i=1; i<=n; i++)
        if(arr[i] == 1)
            answer++;
    
    return answer;
}

 

코드 흐름

1. 정렬

sort(lost.begin(), lost.end());
sort(reserve.begin(), reserve.end());

Greedy 알고리즘이 올바르게 동작하려면 두 배열 모두 오름차순 정렬이 필요하다.

 

2. 전체 학생 체육복 보유로 초기화

for(int i=1; i<=n; i++) arr[i] = 1;

1번부터 n번까지 모두 체육복이 있다고 설정한 후, 잃어버린 학생만 0으로 바꿈.

 

3. 전처리 : 양쪽에 끝에있는 학생 처리

arr[lost[i]] = 0;
if(lost[i] == reserve[j]) {
    reserve[j] = 0;   // 빌려줄 수 없음
    arr[lost[i]] = 1; // 자기가 입음
}

여벌이 있는데 도난당한 학생은 남은 체육복으로 자기가 입어야 한다.

 

4. 인접 학생에게 빌려주기

if(reserve[i]-1 >= 1 && arr[reserve[i]-1] == 0)  // 왼쪽 우선
if(reserve[i]+1 <= n && arr[reserve[i]+1] == 0)  // 왼쪽 안 되면 오른쪽

---

트러블 슈팅

1. 경계 조건에서 인덱스와 학생번호를 혼동

if(i-1 >= 0 && arr[reserve[i]-1] == 0)  // i는 배열 인덱스
if(i+1 <= n && arr[reserve[i]+1] == 0)  // n과 비교하는 건 학생 번호여야 함

이 부분에서 i는 reserve 배열의 인덱스인데, 학생 번호의 범위 체크에 사용했다. 그래서 대부분의 결과에선 정답이 나왔지만 일부 결과에서 오답이 나왔다.

 

실패 케이스 : n=2, lost=[1], reserve = [2]

 

해결 방법

if(reserve[i]-1 >= 1 && arr[reserve[i]-1] == 0)  // 학생 번호로 비교
if(reserve[i]+1 <= n && arr[reserve[i]+1] == 0)  // 학생 번호로 비교

 

2. 정렬 누락

원인파악 : 문제의 예시를 보고, 정렬이 되어서 나온다고 생각해서 정렬을 누락하고 코드 작성을 진행함.

 

실패 케이스 : n=7, lost = [4,6], reserve = [5, 3]

단계	상황
reserve[0] = 5 → 왼쪽 4에게 줌	arr[4] = 1
reserve[1] = 3 → 4도 6도 못줌	학생 6 수업 불가
결과 : n - 1	정답 : n ( 3 → 4, 5 →  6)

 

reserve가 정렬되어 있었다면, 3이 먼저 4에게, 5가 6에게 줄 수 있었다.

 

해결방법 : sort로 정렬시킨 후 진행함.

---

핵심 포인트

1. 반드시 정렬 후 탐욕적 탐색

 

2. 경계 조건 잘 체크하기

 

3. 전처리 순서 중요