2020 카카오 인턴 코딩 테스트 - 3번. 보석쇼핑(c++)

이 문제는 투포인터를 이용하면 쉽게 풀 수 있는 문제이다.

문제에서 gems 배열의 크기가 100,000이하라는 것을 보자마자 이중 for문을 돌렸다가는 터지겠다는 생각이 들었다.

 

따라서, 시간복잡도를 고려하여 투포인터로 풀면 된다.

처음 이 문제를 카카오인턴 코테가 끝나고 바로 올라오자마자 풀어보았는데,,,, 지금 다시 똑같이 풀어보니 틀렸다!!!!!!

 

첫 번째 오류

문제는 End, Start가 모두 다음에 연산할 것을 미리 가르키다보니

End<gems.size()를 하게 되면 연산에 있어서 예외가 생기는 것이다...

ex) ["A", "B", "B", "C", "A"]의 경우 Start = 1, End = 5를 가르키고 끝나버린다...

따라서, tempKind>=kind일 경우에는 End<=gems.size()에도 연산이 되도록 해야한다!

 

두 번째 오류

추후에 이미 End가 gems.size()를 가리키고 있는 상태에서

cnt<kind이면 End부분이 계산이 되어서 segmentation fault가 뜨게 된다....

이러한 경우를 방지하기 위해서 if(End==gemes.size()) break; 조건이 있어야 한다.

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
 
using namespace std
 
map<string, int> m;
int kind = 0;
vector<pair<int, int>> v;
 
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    for(int i=0; i<gems.size(); i++){
        if(m.count(gems[i])==0){
            m[gems[i]] = 1;
            kind++;
        }
    }
    
    m.clear();
    
    int Start = 0, End = 0;
    int cnt = 0;
    
    // 나중에 계산할 부분을 End포인터로 가르키고 있다.
    // End<=gems.size()를 한 이유는 -> 종류는 다 세서 범위를 더 좁힐 수 있는데 못좁히는 경우가 있기 때문이다.
    // Ex) ["A", "B", "B", "C", "A"]의 경우 Start = 1, End = 5를 가르키고 끝나버린다...
    // 왜냐? End<gems.size() 해버리면 이미 End==gems.size()이기 때문에 while문을 돌 수 없어서,,,
    while(Start<=End && End<=gems.size()){
        if(cnt<kind){
            // 추후에 계산될 수 도 있기 때문에 segmentatoin falut가 안뜨려면,,
            if(End==gems.size()) break;
            if(m.count(gems[End])==0){
                m[gems[End]] = 1;
                cnt++; 
            }else{
                m[gems[End]]++;
            }
            End++;
        }else{
            m[gems[Start]]--;
            if(m[gems[Start]]==0){
                m.erase(gems[Start]);
                cnt--;
            }
            Start++;
        }
        
        // 실질적 범위 Start~End-1
        // (범위, 시작점) pair로 저장
        if(cnt==kind){
            v.push_back(make_pair(End-Start, Start+1));
        }
    }
    
    sort(v.begin(), v.end());
    
    answer.push_back(v[0].second);
    answer.push_back(v[0].first+v[0].second-1);
    
    return answer;
}

 

 

문제 첨부

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

코딩테스트 연습 - 보석 쇼핑