[Programmers] Level 1. 체육복 (C++)

정리

정말 많은 고민을 했던 문제였다.
처음에 문제를 보고나서 어떻게 풀지 고민을 했는데 2가지 방법이 생각이 났다.

첫 번째는,
체육복이 있으면 1, 체육복이 없으면 0, 여벌의 체육복이 있으면 2 로 정해두고
여벌의 체육복이 있는 학생의 수를 1 감소하고 없는 학생의 수를 1로 증가시켜서
마지막에 1인 학생의 수를 세서 출력하는 방법이다.
두 번째는,
체육복이 없는 학생을 일단 제외하고
여벌의 체육복이 있는 학생의 것을 빌려주면서 카운트를 더하는 방식이었다.

결과는 두 번째 방법으로 풀었는데 2~3시간 가량 고민 끝에 해결한 문제였다.
이 문제를 이렇게 풀어보았다.

1) 체육복을 잃어버린 학생과 여벌의 체육복이 있는 학생이 같다면 제외시켜준다.
2) 전체 학생에서 체육복을 잃어버린 학생을 빼준다.
3) 여벌이 있는 학생의 체육복을 앞, 뒤 번호에 있는 학생에게 빌려주고 체육복이 있는 학생을 증가시켜준다.
4) 여벌의 체육복이 있는 학생이 체육복을 빌려준다면 제외시켜준다.

이렇게 풀어보았는데 되게 쉬워보였지만 vector를 사용함에 있어 이해가 많이 부족했던 탓에 어려웠던 것 같다.
그리고 테스트케이스 7번을 계속 실패하면서 어떤 부분이 틀렸는지 계속해서 고민했었다.

일단, 내가 문제를 풀면서 잘못 생각했던 부분은
반복문을 통해서 vector 에서 erase 함수를 통해 지워주는 부분이었다.

vector 에서 erase 함수를 통해 해당 인덱스의 값을 지워주게 되면
인덱스의 값이 사라지게 되면서 다음 값이 앞으로 채워지고 크기 또한 줄어들게 된다.
평상시와 같이 반복문을 사용했을 때 여기서 문제가 생겼다.

예를 들어보면,
vec 안에 들어있는 값이
1 2 3 4 5 6 7 8 9 10
이렇게 10개의 값이 들어가있다고 하자.
erase를 통해 3번에 해당하는 값을 지워준다.
그럼 3번의 값이 지워지고 크기가 1 감소한다.
1 2 4 5 6 7 8 9 10 ( 3번째 인덱스의 값이 4가 된다. )

여기서 내가 생각하지 못했던 부분이 있었다.
반복문을 돌릴 때, 나는 항상

for(int i=0; i<5; i++){
	...
}

for(vector<int>::iterator itr = vec.begin(); itr != vec.end(); itr++){
	...
}

이런 식으로 반복문을 사용했었다. 하지만 이렇게 사용하면 문제가 발생한다.
반복문을 통해서 인덱스의 값을 증가시켜주기 때문에
위에서 말한 예시과 같이 반복문을 수행하는 중간에 erase를 통해서 값을 지워준다고 생각하면
i = 3 일 때, erase(3)을 한다고 하자.
i = 4 일 때, 당연히 4가 나올거라고 생각했다.
하지만 i=4 일 때, 값은 5이 나오게 된다.
그 이유는 erase를 통해서 값이 앞으로 밀렸기 때문에
3번째 인덱스의 값이 4가 되고, 4번째 인덱스의 값이 5가 된다.

이 부분 때문에 문제를 해결하는데 오래 걸렸던 것 같다.
덕분에 STL에 대해서 많은 공부를 할 수 있었던 시간이었다.

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    for(vector<int>::iterator iter = lost.begin(); iter != lost.end(); iter++){
        for(vector<int>::iterator itr = reserve.begin(); itr != reserve.end(); ++itr){
            if(*iter == *itr) {
                lost.erase(iter);
                reserve.erase(itr);
                break;
            }
            
        }
    }
    answer = n - lost.size();
    for(int i=0; i<lost.size(); i++){
        for(vector<int>::iterator itr = reserve.begin(); itr != reserve.end();){
            if(lost[i] == *itr-1 || lost[i] == *itr+1) {
                answer++;
                reserve.erase(itr);
                break;
            }
            itr++;
        }
    }

    return answer;
}