프로그래머스 보석 쇼핑 c++ [투포인트]

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

프로그래머스

 

 

해당 문제는 효율성 테스트가 존재하고, 투포인트로 풀어야 시간초과가 발생하지 않는다.

 

우선, 투포인트를 사용하지 않아 틀린 풀이를 확인해보자.

 

 

오답 풀이(시간 초과)

#include <string>
#include <vector>
#include<iostream>
#include<map>
#include<unordered_set>
using namespace std;
map<string,int> ma;

pair<int,int> getLen(){
     int min=987654321,max=-987654321;
     for(auto pr: ma){
         if(pr.second<min)min=pr.second;
         if(pr.second>max)max=pr.second;
     }
     return {min,max};
}
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int min=987654321;
    pair<int,int> ans;
    
    int st=1,ed=1;
    for(int i=0;i<gems.size();i++){
        if(ma[gems[i]]==0){
            ed=i;
            min=987654321;
        }else{
            
        }
        ma[gems[i]]=i+1;
            pair p=getLen();    
            if(p.second-p.first<min){
                min=p.second-p.first;
                ans=p;
            }
    }
    answer.push_back(ans.first);
    answer.push_back(ans.second);
    
    return answer;
}

map을 통해 가장 마지막에 해당 보석이 나온 위치를 찾고, 매번 새로운 보석이 추가될 때마다, 

map에 저장해둔 각 보석의 가장 마지막(오른쪽)위치 들 중 가장 왼쪽, 오른쪽에 위치한 보석의 위치를 통해 구간의 길이를 찾는다.

하지만, 이 방법의 경우, 전체 gems를 탐색하는데 O(N)의 비용이 들고, 각 탐색마다 구간의 길이를 찾기 위해 모든 map을 탐색하게 된다. 

 

이 문제의 제한 조건은, gems 배열이 최대 10,0000 까지 가게되는데, 시작~끝 까지map의 크기(보석의 종류)가 평균적으로 1000이 넘는다면, 연산이 1억이 넘게되고, 이 경우 시간초과가 발생할 수 있다.

 

그리고, 실제로, 시간초과가 발생하여 해당 방법은 실패했다.

 

이제, 시간초과가 발생하지 않게 투포인터를 통해 해결한 풀이법을 알아보자.

 

 

투포인트 알고리즘 풀이(정답)

 

포인트는 끝지점(ed)를 먼저 모든 보석을 포함할 때까지 움직이고, 해당 끝지점을 기준으로 st를 1씩 증가 시켜나가며 여전히 모든 보석을 포함하는지 체크하는 것이다. 만약 st를 앞으로 1칸 증가했을 때 모든 보석의 가짓수를 충족하지 않는다면, 다시 ed를 조건이 만족할 때까지 증가 시킨다.

종료조건은, ed가 마지막 원소까지 탐색한 시점이 된다.

#include <string>
#include <vector>
#include<iostream>
#include<map>
#include<unordered_set>
using namespace std;
map<string,int> ma;
map<string,int> tmp;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
  
    unordered_set<string> num(gems.begin(), gems.end());

    int n=num.size();//보석 종류 개수
   
    int min=987654321;
    pair<int,int> ans;
    int len=0,st=0,ed=0;
    int ast=0,aed=0;
   
    for(int i=0;i<gems.size();i++){
        
        ed=i;//끝지점을 계속 갱신
        if(ma[gems[i]]==0)len++;//새로운 원소 찾으면, 가짓수 추가
        ma[gems[i]]++;//추가된 보석의 개수를 1 증가
         
        if(len!=n)continue; //아직 모든 가짓수를 포함하지 않았다면, st를 그대로 둔다.
        
        for(int j=st;j<=i;j++){//새롭게 갱신된 ed에 대해, 가능한 가장 가까운 st를 찾는다.
            if(ma[gems[j]]>1){//1개 이상이면, 제거가능.
                ma[gems[j]]--;
            }else{ 
                st=j;
                break;
            }
        }
        if(ed-st<min){ //찾은 st-ed 중 가장 짧은 구간이라면 갱신한다.
            min=ed-st;
            ast=st;
            aed=ed;
        }
    }
    answer.push_back(ast+1);
    answer.push_back(aed+1);
    return answer;
}

순차적으로 gems 배열을 탐색하며, 끝지점을 갱신하고, 해당 끝지점에서, 모든 종류의 보석을 포함하는 구간을 형성하는 가장 마지막(오른쪽)의 start까지 시작점을 앞당긴다. 각 loop 마다 끝지점이 i일때, 가장 가까운 시작지점을 찾고, 이 구간의 길이를 연산하게 되고, 이렇게 각 loop 마다 찾은 구간의 길이 중, 최단 거리를 리턴하면 정답이다.