[틀림] [자바] 프로그래머스 보석쇼핑 c++ //슬라이딩윈도우, map,set, size를 활용하라.

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;
}

 

* 25.5.4. 2회독

시도1

전체 배열을돌면서 카운팅 <문자열, 등장횟수>

st=0, en=m으로 두고 en의 등장횟수가 2회이상이면 e--

안되면 st++ ?

복잡하고, 최적해를 놓칠수 있음.

 

행동영역

map, set의 size를 활용하라!

set.size() //유일한 보석의 종류 갯수

map.size() 를 활용하라. // 윈도우 구간에서 보석의 종류의 갯수!

 

풀이

카카오 공식 해설

set에 넣고, size를 유일보석 종류 갯수로 사용

s=0, e=0 (포함) 으로 시작

map<보석이름, 등장횟수>  : 구간에서 보석들의 상태를 카운팅 , size = 보석의 종류갯수

size가 부족? -> e증가, 맵갱신

만족? -> 정답후보에넣기, 맵갱신

 

import java.util.*;

class Pair {
    int first;
    int second;
    
    Pair(int first, int second){
        this.first = first;
        this.second = second;
    }
    
    public String toString() {
        // System.out.println(this.first +" "+this.second);
        return this.first +" "+this.second;
    }
}

class Solution {
    static HashMap<String,Integer> m = new HashMap<>();
    static ArrayList<Integer> v = new ArrayList<>();
    static HashSet<String> s = new HashSet<>();
    
    static ArrayList<Pair> ret = new ArrayList<>();
    
    public int[] solution(String[] gems) {
        int[] answer = {};
        
        for(String gem : gems){
            // if(m.containsKey(gem)){
            //     m.put(gem,m.get(gem)+1);
            // }
            // else{
            //     m.put(gem,1);
            // }
            s.add(gem);
        }
        
        int n=gems.length;
        
        int kk = s.size(); //보석의 종류
        
        int st=0;
        int en=0; //포함
        
        m.put(gems[0],1);
        
        while(true){
            if(st>=n || en>=n){
                break;
            }
            
            // System.out.println(m.size() + " " + kk+ " " + st+ " " + en);
            // System.out.println(m);
            // System.out.println("==========================");
            
            //만족한다면, 정답후보에 추가, 시작을 증가시켜보기
            if(m.size()==kk){
                ret.add(new Pair(st,en));
                
                //2개이상이면, 갯수만 뺴주기
                if(m.get(gems[st]) >=2){
                    m.put(gems[st],m.get(gems[st])-1);
                }
                else{ //1개이하면 제거해주기
                    m.remove(gems[st]);
                }
                
                st++;
            }
            
            //만족하지않으면, en을 증가시켜야함
            else{
                en++;
                if(en==n) break;
                
                if(m.containsKey(gems[en])){
                    m.put(gems[en],m.get(gems[en])+1);
                }
                else{
                    m.put(gems[en],1);
                }
                // en++;
            }
            
        }
        
        // System.out.println(m);
        Collections.sort(ret, (a, b) -> {
            int dist1 = a.second - a.first;
            int dist2 = b.second - b.first;
            if(dist1 == dist2){
                return a.first==b.first? a.second - b.second : a.first - b.first;
            }
            return dist1 - dist2;
            
        });
        // System.out.println(ret);
        answer = new int[2];
        answer[0] = ret.get(0).first+1; //1-idx임
        answer[1] = ret.get(0).second+1;
        return answer;
    }
}

 

람다

정답후보를 정렬하는 과정에서 람다활용

Collections.sort(ret, (a, b) -> {
            int dist1 = a.second - a.first;
            int dist2 = b.second - b.first;
            if(dist1 == dist2){
                return a.first==b.first? a.second - b.second : a.first - b.first;
            }
            return dist1 - dist2;
            
        });

람다를 안쓰는 버전은 아래와 같다

Collections.sort(ret, new Comparator<Pair>() {
    @Override
    public int compare(Pair a, Pair b) {
        int dist1 = a.second - a.first;
        int dist2 = b.second - b.first;
        if(dist1 == dist2){
            if(a.first == b.first) {
                return a.second - b.second;
            } else {
                return a.first - b.first;
            }
        }
        return dist1 - dist2;
    }
});

맵 탐색 코드 최적화

문제 : 맵에 값이있으면, 없으면 ~ 분기가 불편하다.

if(m.containsKey(gems[en])){
    m.put(gems[en],m.get(gems[en])+1);
}
else{
    m.put(gems[en],1);
}

merge를 활용하면 코드를 간결하게 할 수 있다.

m.merge(gems[en],1,(a,b)->a+b);
( 키, 없을때 채울기본값 , 있으면 기존값+새값(1) )