보석 쇼핑

원래는 한번 푼 문제는 다시 안올리지만 어제 투포인터 문제를 풀어본 후에 생각이 나서 리뷰겸 다시 풀어보았다. 처음 이 문제를 풀었을때는 2021년 마지막날이였던 12/31 일날 풀었다. 아직 군대에 있었을때고 상병 4호봉의 한해의 마지막에 풀었던 문제여서 괜히 감성적이게 됐었다.

당시에는 투포인터 개념을 확실히 못잡아서 많이 해맸지만 어제의 문제도 풀고보니 그래도 꽤 자신감이 생기고 한번에 통과했다.

내가 생각하는 투포인터의 핵심 2가지이다.

1. 특정 조건에 맞을때까지 right 포인터를 증가
2. 특정 조건의 "최소화" 를 위해서 left 포인터를 증가 그리고 계산 해준다.

예전에 이 문제를 풀었을때는 한번에 하나의 left 포인터를 옮기느라고 답이 틀렸었는데 문제가 물어보는 조건에 맞다면은 최소화를 맞추기 위해 최대한 left 를 올리는게 핵심인거 같다.

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

vector<int> solution(vector<string> gems) {
    vector<int> answer; 
    int left = 0, right = 0, len = 0, cnt = INT_MAX; 
    map<string,int> hashMap; 
    for(string& gem : gems) hashMap[gem]++; 
    len = hashMap.size(); 
    hashMap.clear(); 
    while(right < gems.size()){
        hashMap[gems[right]]++; 
        if(hashMap.size() == len){
            
            while(hashMap[gems[left]] > 1){
                hashMap[gems[left++]]--; 
            }
            
            if(cnt > (right - left) + 1){
                cnt = (right - left) + 1; 
                answer = {left+1,right+1}; 
            }
        }
        right++; 
    }
    return answer;
}

내 전 포스팅에 있었던 리트코드 HARD 난이도 문제도 그렇고 굉장히 정석적으로 푸는 방식 같아서 앞으로도 많이 사용해보려고 한다. 여기서도 알겠지만 hashMap이 조건과 맞게되면은 while 룹을 사용해서 보석이 하나 이상이라도 있으면 left를 올리면서 조건을 최소화 해주었다.

투포인터류의 문제를 연습하고 싶을때 이 방법들을 적극 사용해주자.