[프로그래머스] 보석 쇼핑

2020 카카오 인턴십 보석쇼핑

 

문제 링크

programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

---

C++ 풀이

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

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    unordered_map<string, int> gem_map; //key-보석, value-보석 포함 개수
    set <string> gem_set(gems.begin(), gems.end()); //중복 원소 제외 저장
    int unique_gem_count = gem_set.size();
    int minDist, start = 0, end = gems.size() - 1;

    for (int index = 0; index < gems.size(); index++) {
        gem_map[gems[index]]++;
        if (gem_map.size() >= unique_gem_count) { //모든 보석을 포함하는 지점을 찾음
            end = index;
            break;
        }
    }

    answer = { start + 1, end + 1 };
    minDist = end - start;

    while (end < gems.size()) {
        string gem = gems[start];
        gem_map[gem]--;
        start++; //start포인트를 증가시켜가며 가장 짧은 구간 검색

        if (gem_map[gem] == 0) { //구간에 포함된 보석 개수가 0이라면
            end++; //end포인트 증가
            while (end < gems.size()) {
                gem_map[gems[end]]++;
                if (gems[end] == gem)
                    break;
                end++; //해당 보석이 나올 때까지 end포인트 증가
            }
        }
        if (end - start < minDist) {
            answer = { start + 1, end + 1 };
            minDist = end - start;
        }
    }
    return answer;
}

단순 저장과 반복문으로는 효율성 테케를 통과하기 어려웠다.

 

여러 풀이 방법들을 참고한 뒤, 투포인터 알고리즘을 활용하여 코드를 작성해보았다.

투 포인터 알고리즘은 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 해를 구하는 방법이다.

 

풀이는 다음과 같이 진행된다.

 

1. 주어진 gems를 set에 저장함으로써 보석의 종류를 구한다.

2. 0 index를 start포인트로 두고, 이로부터 모든 보석을 포함하는 지점을 end포인트로 지정한다.

3. start포인트를 증가시켜가며 모든 보석을 포함하는 가장 짧은 구간을 찾는다.

   - start포인트를 증가하였을 때, 모든 보석을 포함하지 않는다면

   - 모든 보석을 포함할 때까지 end포인트를 증가시킨다

   - (end포인트 - start포인트) 가 저장한 최소 구간보다 작다면 최소 구간을 갱신한다.

 

투 포인터 알고리즘이 무엇인지 학습하고 적용해 볼 수 있었다.

화이팅😳