[프로그래머스] 보석 쇼핑

보석 쇼핑

풀이)

처음에는

인덱스 0부터 ~ 모든 보석을 포함하는 마지막 인덱스를 찾고, 그 안에서 구간을 줄여나가면서 풀었더니

틀렸던 문제다.

예외 존재) ["DIA","EM","EM","RUB","DIA"] 일경우

  answer = [3, 5]

  output = [1, 4] 가 나옴

그렇다고 2중 포문을 사용해서 구간을 찾기에는 보석 배열이 100,000 크기까지 될 수 있으므로 시간초과가 생긴다.

=> 투포인터 방법을 사용해서 풀어야 하는 문제이다.

unordered_map, 투 포인터 사용 풀이법

1. 먼저 보석의 총 개수를 unordered_map을 이용해서 구한다.

2. left, right 두 개의 인덱스 포인터를 이용해서 가장 짧은 구간을 찾는다.

   -> left와 right 인덱스를 조건을 생각하며 한칸씩 이동시켜 모든 보석을 포함하는 구간을 찾는다.

  (구간 내에 모든 보석이 포함되있는지는 unordered_map을 이용해서 판단한다.

   unordered_map 사이즈가 보석의 총 개수와 같다면, 그 구간내에 모든 보석이 포함되어 있다는 뜻이다.)

코드)

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
 
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    unordered_map <string,int> juwel;//맨 처음에는 보석 종류구하는 용도
                                    // 두번째에는 구간내에 보석 종류 빈도 구하는 용도
    int kind = 0;//보석 종류
    for(int i=0;i<gems.size();i++){
        if(juwel.find(gems[i])== juwel.end()){
            juwel[gems[i]] = 1;
            kind++;
        }
    }
   // cout << kind << endl;
    if(kind == 1){//보석이 한 종류뿐일때
         answer.push_back(1);
        answer.push_back(1);
        return answer;
    }
    else if(kind == gems.size()){//각각 모두 다른 보석일때
        answer.push_back(1);
        answer.push_back(gems.size());
        return answer;
    }
    
    juwel.clear();
    int left = 0 , right = 0;
    int result = 987654321;//나올 수 없는 구간 거리
    answer.push_back(0);
    answer.push_back(0);
    while(1){
         //cout << left << ", " << right << endl;
        if(juwel.size() >= kind){//보석이 모든 종류가 포함되어 있을 때
            juwel[gems[left]]--; //맨 왼쪽 인덱스의 보석 하나 제외
            if(juwel[gems[left]] == 0){
                //cout << gems[left] << "삭제 "<< endl;
                juwel.erase(gems[left]);
            }
            left++;
        }
        else if(right == gems.size()) break;
        else{
            juwel[gems[right]]++;//맨 오른쪽 인덱스 보석 포함
            right++;
        }
        if(juwel.size() == kind){
            int per = abs(right - left);
            if(result > per){
                result = per;
                answer[0] = left+1;
                answer[1] = right;
            }
        }
       
        
    }
    
    return answer;
}