프로그래머스, 보석쇼핑 : C++ [CPP]

어렵다.

처음에 생각하기는 어렵지 않은데 효율성 문제가 어렵다.

 

 

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

 

---

 

효율성이 어렵다

생각나는대로 for문으로 한 번 풀어봤다.

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> gems){
    vector <int> answer;
    vector <pair<int, pair<int,int>>> rank;  // 길이 , 시작, 도착
    set <string> s(gems.begin(), gems.end()); // gems의 종류를 알기 위함.
    int size_gem = gems.size(); // 총 탐색해야하는 보석 수
    
    
    
    //시작지점
    for(int i = 0; i<size_gem; i++){
        vector<string> kind(s.begin(), s.end()); // 구간을 탐색하면서 체크하기 위함
        string start = gems[i];
        auto it = find(kind.begin(), kind.end(), start); // 해당 iterator 반환(없으면 kind.end()를 반환)
        // 사실 start일 때 못찾으면 말이 안됨
        if(it != kind.end()){
            kind.erase(it); // 해당 보석 종류 삭제(it 가 kind.end()면 그냥 아무일 안일어남)
        }else{
            continue;
        }

        //도착지점
        for(int j = i+1; j<size_gem; j++){
            //비어있다면 이전 검색에서 모든 종류의 보석을 뽑은 것임 (다른 시작지점을 찾아야함 -> break)
            if(kind.empty()){
                int length = (j-i-1);
                rank.push_back({length, {i+1,j}}); //배열은 0부터시작하지만 보기는 1부터 시작함
                break;
            }
            // 비어있지 않으면 계속 뽑아야함
            string end = gems[j]; // 현재 고름
            it = find(kind.begin(), kind.end(), end); // 해당 iterator 반환(없으면 kind.end()를 반환)
            if(it != kind.end()){
                kind.erase(it); // 해당 보석 종류 삭제(it 가 kind.end()면 그냥 아무일 안일어남)
                //삭제했을 때 비어있으면 거기까지도 기록해야함
                if (kind.empty()) {
                    int length = (j - i - 1);
                    rank.push_back({ length, {i + 1,j+1} }); // 여기선 현재니까 j+1로 기록함
                    break;
                }
            }else{
                continue;
            }
            
        }
    }
    
    sort(rank.begin(), rank.end());
    answer.push_back(rank[0].second.first);
    answer.push_back(rank[0].second.second);

    return answer;
}

 

뭐 접근은 맞았을지 모르나 털려버림

 

투 포인터 알고리즘을 써야 한다고 한다.

그래서 남의 코드를 잠깐 리뷰해보았다. 그리고 풀었다.

 

#맞은 풀이

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <map> // 보석 종류
#include <climits>

using namespace std;

vector<int> solution(vector<string> gems){
    vector <int> answer(2); // 크기 2로 설정
    set <string> s(gems.begin(), gems.end()); // gems의 종류를 알기 위함.
    int size_gem = gems.size(); // 총 탐색해야하는 보석 수
    
    unordered_map<string, int> count; // 보석, 수 (key중복데이터 허용 x -> 중복되어도 오류가 생기진 않고 원소는 늘어나지 않음)

    //(인덱스)
    int start = 0;
    int end = 0;
    int m = INT_MAX; // 길이 최솟값 비교
    int i;
    
    //투포인터 사용 end 포인터 이동 조건과 start 포인터 이동조건 설정
    //end가 더이상 움직이지 못하면(start도 다 움직인 이후에) 종료
    while(1){
        
        //1. end부터 움직임
        for(i = end; i<size_gem; i++){
            count[gems[i]]++; // 해당 종류의 보석 세기
            //맵에 들어간 보석의 종류와 모든 보석 종류의 수가 같으면
            if(count.size() == s.size()){
                end = i; // end포인터는 우선 여기서 멈춤.
                break;
            }
        }
        //옮겨도 end가 업데이트 되지 않는 경우 -> end를 뒤로 보내도 조건이 만족하지 않는 경우
        if(i == size_gem ) break;
        
        
        //2. start 움직임
        for(i = start; i<size_gem; i++){
            //1이면 해당 보석을 빼면 안됨 -> start 갱신
            if (count[gems[i]] == 1){
                start = i;
                break;
            }
            //해당 지점에서의 보석이 1이 아니라면 start를 더 뺄 수 있음.
            else count[gems[i]]--;
        }
        
        //end 와 start를 한 번씪 움직여줬으면 해당 길이 조사
        int length = end - start;
        //현재 최솟값보다 작으면 갱신 -> 같으면 갱신 안해도 되는 것이 먼저나온 것이 우선이기 때문
        if(m>length){
            m = length;
            answer[0] = start + 1; // start 지점
            answer[1] = end + 1; //end 지점
        }
        
        //이제 다시 start를 움직였으니 end 포인터를 움직여야함
        //그러기 위해서 while문 다시 들어가기 전에
        //start에 있는 보석은 빼버리고 end를 옮김
        //만약 안빼면 start는 바로 멈춤
        count.erase(gems[start]);
        start++;
        end++;
        
    }

    return answer;
}

 

어렵다기보다

end 움직이는 조건

start 움직이는 조건

end가 움직이지 못할 때 조건

3가지를 생각해줘야해서 조금 까다로웠다.