[Programmers 코딩 연습] 보석 쇼핑 [Level 3]

Sunghee Kim·2021년 8월 24일

그리디 코딩연습 투 포인트 프로그래머스

programmers-coding-practice

목록 보기

7/10

알고리즘

탐욕법
투 포인터 알고리즘 (2개의 포인터(or index)를 이용해 원하는 바를 구하는 알고리즘)

문제 풀이

이 문제를 요약하면 원하는 조건을 만족하는 최소 길이의 연속된 구간을 구하는 것이다.
따라서 2개의 index를 잘 조절하여 해당 구간을 구해야 한다.
(이를 투 포인터 알고리즘이라고 한다.)

구간의 왼쪽 끝을 left, 오른쪽 끝을 right라고 하자.

우선 left와 right모두 0(첫 번째)부터 시작한다.

가. right을 오른쪽으로 이동시키면서 모든 종류의 보석들이 해당 구간 안에 들어오는 위치에서 멈춘다.

나. left를 마찬가지로 오른쪽으로 이동시키면서 해당 위치의 보석이 구간 안에 단 1개만이 있을 때 멈춘다.

이때, 구간의 상태는 다음 2가지를 만족한다.

1. 보석의 모든 종류가 1개 이상은 구간에 포함된다.
2. left 위치의 보석은 구간 안에 단 1개다.

구간 (left, right)는 해당 right 위치가 오른쪽 끝이 되는 구간들 중 문제의 조건을 만족하는 최소 길이 구간이 된다.
그러나 아직 이것 만으로는 이 구간이 답인지 속단할 수 없다.
구간의 끝점을 옮겨 가면서 모든 경우를 따져야 한다.

다. left, right를 한 칸씩 움직이고 '가'와 '나'를 수행하기를 반복하고 최소 길이가 되는 구간, 즉 문제의 답을 기록한다.

( left를 한 칸씩 이동시키는 이유는 (left, right+1)에는 (left, right)가 포함되어 있기 때문이다. 더 간단히 말하면 어차피 (left, right+1)은 최소 길이가 될 수 없기 때문에 left+1로 증가 시켜 주는 것이다. )

소스코드

#include <string>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

bool find_gem(unordered_map<string, int> &umap, string &str) {
    if (umap.find(str) == umap.end())
        return false;
    return true;
}

vector<int> solution(vector<string> gems) {
    set<string> gem_kinds;
    unordered_map<string, int> gem_cnt_map;
    
    for (string &gem : gems)
        gem_kinds.insert(gem);
    
    int len = gems.size();
    int kinds_cnt = gem_kinds.size();
    int left = 0, answer_left, right = 0, answer_right;
    int minLen = 100001;
    
    string gem;
    
    while(true) {
        // left(현재 고정)부터 right까지 모든 종류의 보석 포함하는 최소의 right 구하기
        while (right < len) {
            gem = gems[right];
        
            if (find_gem(gem_cnt_map, gem))
                gem_cnt_map[gem]++;
            else
                gem_cnt_map[gem] = 1;
            
            if (kinds_cnt == gem_cnt_map.size())
                break;
            
            right++;
        }
        
        // 위 while문을 빠져 나올 때, break가 아닌 while의 조건이 거짓이어서 빠져나왔을 경우 고려
        if (kinds_cnt != gem_cnt_map.size())
            break;
        
        // left부터 right(현재 고정)까지 모든 종류의 보석 포함하는 최대의 left 구하기
        while (left <= right) {
            gem = gems[left];
            
            if (gem_cnt_map[gem] == 1)
                break;
            
            gem_cnt_map[gem]--;
            left++;
        }
    
        if (minLen > right-left+1) {
            minLen = right-left+1;
            answer_left = left+1;
            answer_right = right+1;
        }
        
        gem_cnt_map.erase(gems[left]);
        right++;
        left++;
    }
        
    return {answer_left, answer_right};
}