2020 카카오 인턴십 문제 ②

 

2020 카카오 인턴십

 

 

 

#4 보석 쇼핑

map과 two pointer을 사용해 푸는 문제

i부터 j까지 구간에 모든 보석을 가지고 있는가를 판단할 때 map을 사용,

아니라면 j, 맞다면 i를 증가하여 왼쪽에서 오른쪽으로 이동하며 가장 짧은 구간을 구한다.

처음엔 구간 길이에 대한 이분탐색으로 접근했다. 시간초과 났음

비슷한 문제를 다른 코테에서 본 적 있다. 이 문제의 2차원 버전이었는데,,, 아쉽다

map<string,int> M;
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int N=gems.size();
    
    // Gems
    for(string g:gems){
        auto iter=M.find(g);
        if(iter==M.end()) M.insert({g,0});
    }
    int G=M.size();
    M.clear();
    
    // Two Pointer
    int left = 0, right = N - 1;
    for (int i = 0, j = 0; j < N; ++j) {
        //printf("i:%d j:%d\n", i, j);
        auto iter = M.find(gems[j]);
        if (iter == M.end()) M.insert({ gems[j],1 });
        else (iter->second)++;

        while (M.size() == G && i<=j) {
            if (right - left + 1 > j - i + 1) left=i, right=j;

            auto iter = M.find(gems[i]);
            if ((iter->second) > 1) (iter->second)--;
            else M.erase(iter);
            i++;
        }
    }
    answer.push_back(left+1), answer.push_back(right + 1);
    
    return answer;
}

 

 

 

#5 동굴 탐험

위상정렬

모든 노드에 대해, 해당 노드보다 부모 노드를 먼저 방문해야 한다.

이를 이용해 indegree배열을 만들어 위상정렬로 해결

입구에 들어가지도 못할 때(다른 방을 0보다 먼저 방문해야할 경우)에 주의한다.

queue<int> Q;
vector<int> e[200000];
int ind[200000];
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    
    //1. tree edge 정리
    for(vector<int> p:path){
        e[p[0]].push_back(p[1]);
        e[p[1]].push_back(p[0]);
    }
    
    //2. BFS, tree build
    Q.push(0); ind[0]=-1;
    while(!Q.empty()){
        int cur=Q.front(); Q.pop();
        
        for(int nxt:e[cur]){
            if(ind[nxt]) continue;
            ind[nxt]=1; Q.push(nxt);
        }
    }
    for(vector<int> o:order) ind[o[1]]++, e[o[0]].push_back(o[1]);
    
    //3. get answer
    if(ind[0]>=0) answer=false; //입구에 들어가지도 못할 때
    else{
    	Q.push(0);
    	while(!Q.empty()){
        	int cur=Q.front(); Q.pop();
        	ind[cur]=-1;
        
        	for(int nxt:e[cur]){
            	if(ind[nxt]<0) continue;
            	ind[nxt]--;
            	if(!ind[nxt]) Q.push(nxt);
        	}
    	}
    
    	for(int i=1;i<n;++i){
    	    if(ind[i]>=0) {answer=false; break;}
    	}
    }
    return answer;
}