2020 카카오 인턴십 for Tech developers 코딩테스트 3번

문제

programmers.co.kr/learn/courses/30/lessons/67258#

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

문제 분석

접근법은 어렵지 않았던것 같다.

배열의 길이가 100,000 = 10^5이므로, n^2는 안되고 nlogn정도로 불어야 하기 때문에, 모든 인덱스를 기준으로 한칸씩 움직이며 모든 보석이 확인될 때 까지 순회를 하면 안된다. 대충 n^2이니까

그렇다면 배열을 한번만 돌아야 한다는게 키 포인트인데, 이를 위해서 현재 insert하는 인덱스와 pop하는 인덱스를 저장하고, 그 사이에 모든 원소가 들어간다면 output을 갱신하는 방식으로 구현되어야 할 것이다.

이를 위해서 map과 set을 사용했으며, 하나의 원소를 set에 집어 넣었을 때, 보석 종류의 갯수와 같다면 pop index를 한칸 씩 올리면서 범위에 모든 보석의 종류가 있는지 다시 확인하는 것이다. 이는 map을 통해 그 보석이 현재 몇개 들어있는지 확인하고 1을 줄임으로써 구현되었는데.  만약 줄여진 값이 0이라면, 즉 현재 범위에 그 보석이 더이상 존재하지 않는다는 의미이므로 set에서 그 원소를 지울것이다. 

접근법은 괜찮았으나.... 이 pop index의 증가 위치와 while문의 break 포인트가 맞물리면서 break가 먼저되서 index 적용이 안되고, set에서 원소를 삭제하기 전에 index가 먼저 적용되서 참조 오류가 나고... 쨋든 설계가 완벽하지 않아서 꽤나 헛고생을 많이 했다. 

 

코드

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

vector<int> solution(vector<string> gems) {
    set<string> total_set;
    for(int i=0; i<gems.size(); i++)
        total_set.insert(gems[i]);
    
    map<string, int> tmp_map;
    set<string> tmp_set;
    int low_pos = 0;
    int now_min = 100000000;
    int min_idx = -1;
    for(int i=0; i<gems.size(); i++)
    {
        tmp_set.insert(gems[i]);
        map<string,int> :: iterator it = tmp_map.find(gems[i]);
        if(it == tmp_map.end())
            tmp_map.insert(make_pair(gems[i], 1));
        else
            it->second = it->second + 1;
        while(1)
        {
            if(tmp_set.size() == total_set.size())
            {
                if(i-low_pos+1 < now_min)
                {
                    now_min = i-low_pos+1;
                    min_idx = low_pos;
                }
                map<string,int> :: iterator second_it = tmp_map.find(gems[low_pos]);
                second_it->second = second_it->second - 1;
                if(second_it->second <= 0)
                {
                    tmp_set.erase(gems[low_pos]);
                    low_pos++;
                    break;
                }
                low_pos++;
            }
            else
                break;
        }
    }
    vector<int> answer;
    answer.push_back(min_idx+1);
    answer.push_back(min_idx + now_min);
    return answer;
}

개선점?

수도 코드를 짜든 스캐치를 하든 전체적인 흐름을 잡고가야할거같다.