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

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

코딩테스트 연습 - 체육복

---

이 문제를 풀고 나서 다른 분의 풀이를 보고 나서 아..! 싶었다.

알고리즘을 몇 개 아는 지금 이 시점에서, 알고리즘 연습 문제는 어떻게든 풀  수 있다..

그리고 내가 알고 있는 방법 내에서 충분히 효율적으로 풀 수 있음에도

지금의 나는 그냥 무작정 어떻게든 풀어내려는 게 습관화 되어있는 것 같다😥

앞으로는 효율을 생각해봐야지...

1) 풀이

별거 아닌 문제인데도 굉장히 시간을 많이 소요한 문제,,

다 맞는 것 같은데 몇 개의 케이스가 통과되지 않아 굉장히 애를 먹었다...(5, 7, 12번 케이스였던 것 같다)

음 일단 굉장히 비요율적인 방법이지만 이것도 내가 적은 코드니까..

기록용으로 남겨본다! 앞으로 발전하면 되지 모~

 

1. 여분의 체육복이 있는 학생이 체육복을 잃어버렸는지 체크하고, 잃어버렸다면 lost와 reserve에서 해당 학생의 번호를 지운다. (자신이 체육복을 입어야하므로 빌려주지 못하고, 체육수업은 들을 수 있으므로)

2. 1의 과정을 거친 lost 벡터와 reserve 벡터의 인덱스를 하나하나 확인하면서 lost 벡터의 인덱스가 (reserve 벡터의 인덱스-1)이나 (reserve 벡터의 인덱스+1)과 같다면 잃어버린 학생의 번호와 빌려주는 학생의 번호를 지운다.

3. 최종적인 lost 벡터의 사이즈(즉, 잃어버렸지만 빌리지 못한 학생의 수)를 n에서 빼주고 answer에 입력한다. 

 

어떻게 적어야 할지 고민하다가, 이렇게 번호로 적는 게 제일 보기 나을 것 같다..

일단 지우는 과정은 erase 함수를 사용했다.

erase 함수를 사용하면, 해당 인덱스의 값이 아예 지워지고 그 뒤의 값들이 앞으로 당겨지기 때문에

반복문으로 모든 값들을 탐색하기 위해서는 지운 다음에 탐색하는 변수의 값을 -1 해줘야 한다!(해당 내용에 관한 건 참고자료에 첨부해둠)

 

또한, 처음엔 1의 과정을 2에서 같이 해주었는데 따로 빼준 이유는

예를 들어, n=5, lost [2, 3, 4] reserve [3, 4, 5] 이런 상황이 있다고 치자.

3, 4 번 학생은 여분의 체육복이 있지만 자신도 잃어버렸으므로 빌려줄 수가 없다.

하지만 1의 과정을 따로 빼서 처리해주지 않으면 2번이 3번 학생의 체육복을 빌려가는 상황이 먼저 생길 수 있다!

(지금 생각해보면, 탐색을 거꾸로 진행해주면 되나..? 싶긴 한데 나중에 시도해봐야겠다)

 

풀이는 이걸로 대충 마무리가 되는 것 같다!

아까전부터 누누이 말하고 있지만, 너무너무 비효율적이다..

 

설명만 들어도 lost 길이* reserve 길이 만큼의 시간복잡도가 요구된다는 건데...

n이 최대 30이니까 통과가 가능했던 거지, 사실 데이터 크기가 커졌으면 통과 안 됐을 아주아주 비효율적인 방안이다... 

 

아래 참고자료에 내가(나를 포함한 많은 사람이) 굉장히 깔끔한 코드라고 생각하는 다른 사람이 푼 풀이를 첨부해놓겠다.

 

2) 최종 소스코드

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

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    for(int i=0;i<lost.size();i++){
        for(int j=0;j<reserve.size();j++){
            if(lost[i]==reserve[j]){
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
                --i;
                --j;
            }
        }
    }
   
    for(int i=0;i<lost.size();i++){
        for(int j=0;j<reserve.size();j++){
            if(lost[i]==reserve[j]-1||lost[i]==reserve[j]+1){
                reserve.erase(reserve.begin()+j);
                lost.erase(lost.begin()+i);
                --i;
                --j;
            }
        }
    }
    answer=n-lost.size();
    return answer;
}

3) 참고자료

출처: 프로그래머스 - 체육복 - 다른 사람의 풀이

https://jaynamm.tistory.com/entry/C-STL-vector-erase-%ED%95%A8%EC%88%98-%EC%82%AC%EC%9A%A9%ED%95%A0-%EB%95%8C-%EC%A3%BC%EC%9D%98%ED%95%A0-%EC%A0%90

[C++] vector 에서 erase 함수 사용할 때 주의할 점