2020 카카오 인턴십 보석 쇼핑-C++

이번 문제는 혼자 풀지 못해 아래 글을 참고하여 풀었습니다.
참고 블로그

우선, 이 문제는 보자마자 투포인터로 풀어야겠다. 생각은했는데, 계속 segment fault로 풀리지 않아 해답을 봤습니다.

투포인터라고 생각한 이유는, 최단 구간의 처음과 끝을 출력하라 하였으므로 [1,3] 처음이 start, 끝을 end로 설정하여 풀면 될것이라 생각했습니다.

1. 보석 종류 세기

map<string,int>map;
    int gCount=0;
    for(int i=0;i<gems.size();i++){
        string gem = gems[i];
        if(map.find(gem)==map.end()){
            gCount++;
            map[gem]++;
        }
    }
    
    map.clear();

동일한 보석을 map에서 찾지못하면 gCount++하였습니다.

2. start end 최단 구간 설정

 int start = 0;
    int end=0;
    int min_len = 100001;

gems의 최대길이가 100,000이므로 100,001로 설정하였습니다.

3. while문

 while(1){
        //보석이 모두 있는경우
        if(gCount==map.size()){
            //최소구간이라면 갱신
            if(end-start<min_len){
                min_len=end-start;
                answer[0]=start+1;
                answer[1]=end;
            }
            
            if(map[gems[start]]==1){
                map.erase(gems[start]);
            }else{
                map[gems[start]]--;
            }
            
            start++;
        }
...

먼저 보석이 모두 있는경우입니다.
ABABDA라면
현재 start가 0번째이고 End가 D에해당하는 4번 idx에 있을 것입니다.
end - start로 보석이 전부 있을 수 있는 구간인 4와 min_length와 비교하여 갱신합니다.

그다음, start를 end쪽으로 땡기면서 보석이 2개이상이라면 1개를 빼주고 하나라면 map에서 없앱니다.
현재 map이
ABD
221
이므로
ABD
121
이 됩니다.
그리고 또 while문을 보석종류가 3개이므로 start를 땡기는데 이번엔 B를 -1해줍니다.
ABD
111
그다음 또 while문을 돌때 보석종류가 3개지만 start를 땡겼을때 A가 1이므로 A를 지웁니다.
BD
11
그러면 현재 start는 3번 idx end는 4번인덱스에 있습니다.

else if(end==gems.size()) break; //end가 끝까지 간경우 만약 aaaab인경우 위의 if문이 걸려서 ab까지 감

만약 aaaaab라면 end가 이미 b에 도착해있고 0번 idx인 start를 end쪽으로 땡기면서 확인 할 것입니다.
그런데 생각해보면, end가 gems에 마지막에 가있더라도 위의 보석 종류가 있는 경우에 부합하기 때문에 ab가 될때까지 계속 최단구간을 확인 할 것입니다.

else if(map.size()<gCount){
            map[gems[end]]++;
            end++;
        }

마지막으로 보석이 없는경우 end에 해당하는 보석을 추가하고 end를 땡깁니다.

여기서 알수있는게 왜 맨처음 if문에서 갱신을 할때 start는 +1을 하고 end는 더하지 않는지를 알수 있습니다.
ABABDA여기에서 D에 와서 else if(map.size()<gCount){}문을 실행하면 이미 end는 +1이 되어서 A자리에 가있습니다. start는 그렇지 않습니다. answer[0]번째 갱신 이후 start++하기 때문.
그러므로 이미 end는 한자리 땡긴후이므로 +1 하지 않습니다.
여기서 꽤 시간을 많이 썼습니다.

정답코드

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

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    answer.push_back(0);
    answer.push_back(0);
    
    map<string,int>map;
    int gCount=0;
    for(int i=0;i<gems.size();i++){
        string gem = gems[i];
        if(map.find(gem)==map.end()){
            gCount++;
            map[gem]++;
        }
    }
    
    map.clear();
    
    int start = 0;
    int end=0;
    int min_len = 100001;
    while(1){
        //보석이 모두 있는경우
        if(gCount==map.size()){
            //최소구간이라면 갱신
            if(end-start<min_len){
                min_len=end-start;
                answer[0]=start+1;
                answer[1]=end;
            }
            
            if(map[gems[start]]==1){
                map.erase(gems[start]);
            }else{
                map[gems[start]]--;
            }
            
            start++;
        }else if(end==gems.size()) break; //end가 끝까지 간경우 만약 aaaab인경우 위의 if문이 걸려서 ab까지 감
        else if(map.size()<gCount){
            map[gems[end]]++;
            end++;
        }
    }
    return answer;
}