[프로그래머스] 2020 카카오 인턴십 - 보석 쇼핑(C++)

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

프로그래머스

 

 

단순히 정확도만 맞춘다면 N^2으로 처리 가능하지만 10만개를 확인해야하기 때문에 O(N)으로 처리해야한다. 일정 구간을 나타내야하기 때문에 슬라이딩 윈도우라고 봐도 되고 투포인터라 봐도 될 것 같다.

 

그래서 답을 찾았다고 탈출, 리턴해주는 방식으로는 이 문제를 풀 수 없다. 후에 다이아몬드라는 보석이 더 있을 수도 있기 때문에 끝까지 탐색하고 값을 계속 최적화해야한다.

 

AAABBCA 라고 주어졌다고 하자. 정답은 마지막 BCA가 정답이 된다 어떻게 최적화 해야할까?

 

먼저 만약 ABCBBB 가 주어졌다면 정답은 ABC이다. 그러므로 우선 모든 보석을 포함하는 경우를 찾는다.

 

AAABBC 의 경우 모든 보석을 포함한다! 그러므로 정답 후보가 될 수 있다.

이제 다음과 같은 연산을 해본다.

• 맨 앞에서 구간을 한 칸 줄여보자 -> AABBC
• 만족하므로 더 줄여보자 -> ABBC
• 더 줄여볼까? -> BBC 이제 정답이 될 수 없음!

AAABBC 는 최적으로 규격을 줄이면 ABBC 가 된다. 그 다음부턴 BBC이므로 정답 후보가 될 수 없다. 정답후보가 되지 않으면 다시 뒤의 인덱스를 옮기며 새로운 정답 규격후보지를 찾는다.

 

-> BBCA 정답후보를 찾았다. 만족하므로 또 줄여보자

• 맨 앞에서 구간을 한 칸 줄여보자 -> BCA
• 만족하므로 더 줄여보자 -> BC 이제 정답이 될 수 없음! 

그리고 중요한 것은 지금 구간이 보석을 포함하는지 안하는지 검사하는 것을 최적화 해야한다. 순회하며 확인하면 안된다.

 

그래서 맵 방식과 셋 방식을 고루 사용한다.

 

ABBCA를 예로 들자

 

만족구간을 넣을 때 까지 모두 맵과 셋에 삽입한다. 

A: 1

B: 2

C: 1

 

이고 셋의 사이즈가 보석의 종류와 같다.

 

이제 최적화를 해서 규격을 줄여보면.. A가 빠지므로 맵에서 -1 해준다. 그리고 맵에서 0이되면 셋에서도 지워주는 방식을 사용한다.

 

#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    set<string> s;
    int low = 0;
    int hi = 0;

    for(string st : gems) s.insert(st);
    
    map<string, int> status;
    set<string> nowGemSize;
    int gemSize = s.size();
    
    int min_gap = 100001;
    int ans_lo = 0;
    int ans_hi = 0;
    
    while(low <= hi && hi < gems.size() && low < gems.size()){
        
        if(gemSize == nowGemSize.size()){
            int gap = hi - low;
            
            if(gap < min_gap){
                min_gap = gap;
                
                ans_hi = hi;
                ans_lo = low;
            }else if(gap == min_gap){
                if(ans_lo > low){
                    ans_hi = hi;
                    ans_lo = low;
                }
            }
            status[gems[low]]--;
            if(status[gems[low]] == 0){
                nowGemSize.erase(gems[low]);
                hi++;
            }
            low++;
        }else if(gemSize > nowGemSize.size()){ // 아직 부족함
            status[gems[hi]]++;
            nowGemSize.insert(gems[hi]);
            if(gemSize > nowGemSize.size())
                hi++;
        }
    }
    answer.push_back(ans_lo + 1);
    answer.push_back(ans_hi + 1);
    return answer;
}

 

어려워