프로그래머스 보석쇼핑 c++ //투포인터 ,슬라이딩윈도우, map,set

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

프로그래머스

1. 투포인터 ,슬라이딩윈도우 코드형식

s,e=0부터시작해서

이렇게 움직이는 투포인터를 슬라이딩 윈도우라고 한다.

while(1):
	e가끝 and 조건불만족 -> 탈출!
    
    if(조건만족)
    	e가 범위밖이면 continue!
    	+1하기전 자료구조 갱신!
    	e+1
    else
    	+1하기전 자료구조 갱신!
    	s+1

해당 형식을 암기하자.

 

2. map,set 활용법

set는 set.size()를 유일값의 갯수로 저장하고 버리면된다.

s를 갱신하는경우, map에서 빼준후, 뺴준후 값이 0이면 해당 key를 지워버리면 된다.

시행착오 : map, set을 동시에 사용하려니 너무 복잡해졌다...

 

3. unorder_map vs map

연산 : 삽입,삭제,검색

O(1), 충돌시 O(N) vs 항상 O(lgN)

이문제에는 unordered가 40ms 더 빨리 동작한다.

 

4.의사코드

※ 시행착오 : s=0, e=n-1로 놨더니, 조건이 분기가 필요하였다(e를 -할지 s를 +할지 결정이 그때그때 다름)

이경우 s=0,e=0으로 슬라이딩 윈도우를 떠올려보자

 

0. 조건 : 현재 map.(key.)size가 유일값과 같으면 조건을 만족하는것이다.

map<문자열, 현재갯수>를 저장한다.

1. 불만족 -> e+1

조건만족 -> 정답후보에 추가, s+1

으로 반복을 이진트리와 비슷하게 단순하게 생각하면된다.

2. e+1전, 범위쳌,

+1하기전 map을 갱신한다.

map의 값이 0이되면, map에서 지운다!

3. 정렬

투포인터 코드 내에서 처리하지말고

정답후보 벡터를두고, cmp로 정렬하도록 하자!

디버깅이 어렵다 ㅜㅜ

 

5.전체코드

#include <bits/stdc++.h>
using namespace std;

map<string,int> m; //unorder : 28ms , map:67ms
set<string> se1,se2;
vector<pair<int,int>> ans; //정답후보들
int limit; //유일문자열의 갯수, curmap.size()가 이거이상이면 조건만족

//1. 거리짧은것 우선
//2. 거리가같으면, s가작은것 우선
bool cmp(pair<int,int> p1, pair<int,int> p2){
    int dist1=p1.second-p1.first;
    int dist2=p2.second-p2.first;
    if(dist1==dist2){
        return p1.first<p2.first;
    }
    return dist1<dist2;
}
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    for(auto s:gems){
        se1.insert(s);
        //m1[s]++;
    }
    limit=se1.size();
    
    int s=0, e=0;
    m[gems[s]]++; //초기값
    while(1){
        //탈출조건 : e가끝에도달 and 조건불만족
        //(e가끝에도달 and 조건만족이면 s를 +1해도 만족하는지 추가탐색이 필요함)
        if(e==gems.size()-1 && m.size()!=limit) break;
        
        //조건불만족하는경우, e를 +시킴(범위체크 필수!, +시키기전 갱신필수!)
        if(m.size()!=limit){
            if(e==gems.size()-1) continue; //범위쳌
            e++;
            m[gems[e]]++;
        }
        //조건만족하는경우, 정답에넣고, s를+ 시킴(+시키기전에 m 갱신해야함)
        else{
            ans.push_back({s,e});
            m[gems[s]]--; //s+1전 갱신
            
            if(m[gems[s]]==0){ //갱신했는데 0개남은경우 map에서 제거!
                m.erase(gems[s]);
            }
            s++;
        }
    }
    
    sort(ans.begin(),ans.end(),cmp);
    // for(auto p : ans){
    //     cout<<p.first<<" "<<p.second<<"\n";
    // }
    answer={ans[0].first+1,ans[0].second+1};
    return answer;
}