[C++] 프로그래머스 체육복

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

코딩테스트 연습 - 체육복

 

1. 서론

 

level 1짜리 간단한 문제이다. 그리디로 푸는 문제란다. 문제 자체는 어렵지 않으나 테스트 케이스가 까다로웠다.

 

2. 문제 풀이

 

체육시간에는 체육복을 입어야 수업을 들을 수 있다. 그리고 체육복을 도난당한 학생과 더 가져온 학생이 있다.

여벌의 체육복을 가져온 학생은 딱 한 벌 더 가져오며, 도난당한 학생은 1명 이상, 전체 학생은 2명 이상이다. 

도난당한 학생과 여벌의 가져온 학생이 같은 학생일 수 있으며, 그런 경우엔 남은 체육복이 하나라 다른 학생에게 체육복을 빌려줄 수 없다.

그리고 도난 당한 학생은 자신의 앞, 뒤 번호 학생에게만 체육복을 빌릴 수 있다.

 

입출력 예시

 

학생 수: 5

도난 당한 학생: 2, 4

여벌 있는 학생: 1, 3, 5

 

2번 학생은 1, 3번 학생 중 한 명에게, 4번 학생은 3, 5번 학생 중 한 명에게 받을 수 있다.

즉 5명의 학생이 전부 수업에 참여할 수 있다.

 

3. 코드 설명

 

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0, i, j;
    vector<int> c;
    
    for (i = 0; i < n + 1; i++)
        c.push_back(0);
    
    //만약 도난 = 여벌일 시 둘다 그냥 제거
    for (i = 0; i < reserve.size(); i++)
    {
        for (j = 0; j < lost.size(); j++)
        {
            if (reserve[i] == lost[j])
            {
                reserve.erase(reserve.begin() + i);
                lost.erase(lost.begin() + j);
            }
        }
    }
    
    //여벌 옷 있나 체크
    for (i = 0; i < reserve.size(); i++)
        c[reserve[i]]++;
    
    answer = n - lost.size();
    
    for (i = 0; i < lost.size(); i++)
    {
    	//도난 = 여벌인 경우(?)
        if (c[lost[i]] == 1)
        {
            c[lost[i]]--;
            answer++;
        }
        //앞사람에게 빌리기
        else if (c[lost[i] - 1] == 1)
        {
            c[lost[i]- 1]--;
            answer++;
        }
        //뒷사람에게 빌리기
        else if (c[lost[i] + 1] == 1)
        {
            c[lost[i]+ 1]--;
            answer++;
        } 
    }
      
    return answer;
}

 

 

reserve는 여벌이 있는 학생의 배열, lost는 도난당한 학생의 배열, c는 여벌이 있는지 없는지 체크하기 위해 만든 배열.

처음 코드를 짰을 때는 도난 = 여벌일 경우 동시 제거하는 for문이 없었다.

c배열에 여벌이 있는 항은 1 없는 항은 0으로 값을 주고, 도난 당한 사람이 여벌 있는 사람인 경우에는 그냥 스스로 카운트를 하고 0으로 만들었다. 그리고 그 후엔 앞사람부터 도난당한 사람이 빌리고 나면 1을 0으로 만들어서 그다음 사람이 빌리지 못하게 하고 앞사람이 없으면 뒷사람에게 아무도 없으면 카운트를 하지 않는다.

이렇게만 짰을 때 12개의 테스트 케이스 중에 단 한 개, 12번째 케이스 말고는 전부 다 맞았다. 

그래서 질문하기에 들어가 보니 12번 케이스가 

 

'도난당한 학생과 여벌의 가져온 학생이 같은 학생일 수 있으며, 그런 경우엔 남은 체육복이 하나라 다른 학생에게 체육복을 빌려줄 수 없다.'

 

이 부분을 적용한 거란다. 근데 나는 도난 = 여벌인 경우를 if문으로 처리해주는데 왜 안되는 걸까 생각하면서 도난 = 여벌일 시 둘 다 제거해주는 for문을 넣었다. 그랬더니 정답이었는데 문제를 혼자 푼 것 같지 않아 썩 후련하지 않았다.

도난 = 여벌을 처리해주는 for문이 생겼으니 밑의 for문에서 if문으로 도난 = 여벌인 경우를 지우고 다시 돌리니 테스트 케이스 3개 인가가 다시 실패로 떴다. 진짜 솔직히 나는 내가 짰지만 이 코드를 이해하지 못하겠다...

 

도난 = 여벌을 처리하는 for문과

도난 = 여벌을 처리하는 if문의 역할이 결국 다르다는 뜻인데 그 부분을 잘 모르겠다.

이 if문도 안 넣었을 때는 5번과 12번이 둘 다 틀렸었는데 저걸 넣고 5번은 맞아졌다. 

이거 설명해 주실 분 댓글로 남겨주세요... 그리고 12번 테스트 케이스 뭔지 아시는 분 제보 바랍니다.