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

문제 주소 : programmers.co.kr/learn/courses/30/lessons/67258

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

문제 확인

 

투포인터 문제입니다. 트라이를 활용해서 풀 수 있지만 최악의 경우 100000개의 보석의 이름 모두 10글자이며 중복이 없고 각 단어가 하위 트라이를 계속해서 만드는 경우 메모리 사용량이 너무 커질 수 있습니다.

ex) "abcdefghij", "bcdefghijk", ... "aabcdefghi" ..

 

풀이

 

2가지 풀이법이 있습니다.

1. 배열을 탐색해서 미리 보석의 종류를 map에 기록해둔 후 투포인터 알고리즘 적용
2. map에 기록해두지 않고 탐색하면서 종류가 늘어나는 경우를 기준으로 투포인터 알고리즘 적용

1번 풀이법의 경우 현재 가지고 있는 보석의 종류가 최대 종류보다 낮은 경우 right 포인터를 옮기고, 같은 경우 left를 옮깁니다. 이때 마지막 보석이 left의 보석과 같은 경우 동선 길이가 짧아지는 경우가 있으므로 한번 더 체크 해 주어야 합니다.

ex) a, b, b, c, d, e, a 의 경우 마지막 보석을 탐색하기 전 단계는 a, b, b, c, d, e = 6 이며 마지막 보석을 탐색할 시 a, b, b, c, d, e, a 에서 b, c, d, e, a로 갱신해 주어야 합니다.

 

2번 풀이의 경우 map에 보석의 개수를 기록해두어 훨씬 간단하게 문제를 풀 수 있습니다.

right을 늘려가며 탐색하며 새로운 종류를 추가하는 경우 최대 종류의 개수가 늘어나므로 min_left, min_right 값을 즉시 경신해 주고, 이미 들고 있는 종류의 보석을 추가하는 경우는 들고 있는 left의 보석 개수가 1개 이상인 경우 left를 넘겨주어 모든 보석의 개수를 최소 1개 이상 들고 있도록 합니다.

이때 min_left, min_right의 경우 길이가 그전에 찾아낸 동선의 길이보다 짧다면 갱신합니다.

 

코드

1번 풀이법

#include <string>
#include <vector>
#include <map>
using namespace std;
 
vector<int> solution(vector<string> gems) {
 
    map <string, int> mp;//int 값이 0이 되면 들고있는 해당 보석의 수가 0개 = 모든 보석을 가지고 있지 않음
    int kind = 0, min_len = 100001, min_left, min_right;
    int cur_count = 0, left = 0, right = 0;
    for (auto &t : gems)
        if (mp.emplace(t, 0).second)//보석 종류
            kind++;
    while (right < gems.size()) {
        if (cur_count != kind) {//보석의 종류가 부족한경우
            auto &cur = mp[gems[right]];
            if (!cur)//들고 있지 않은 보석이라면 종류 수 늘림
                cur_count++;
            cur++;
            right++;
        }
        else {//모든 보석을 들고있는 경우
            if (min_len > right - left) {//짧은 경우 갱신
                min_len = (min_right = right) - (min_left = left);
            }
            auto &cur = mp[gems[left]];
            if (!(--cur))//들고 있는 보석 수 줄임
                cur_count--;//0이 되면 종류 수를 줄임
            left++;
        }
    }
    while (cur_count == kind) {//왼쪽 갱신
        if (min_len > right - left) {
            min_len = (min_right = right) - (min_left = left);
        }
        auto &cur = mp[gems[left]];
        if (!(--cur))
            cur_count--;
        left++;
    }
    return { ++min_left, min_right };
}

 

2번 풀이법

#include <string>
#include <vector>
#include <map>
using namespace std;
 
vector<int> solution(vector<string> gems) {
    map <string, int> mp;//int 값이 0이 되면 들고있는 해당 보석의 수가 0개 = 모든 보석을 가지고 있지 않음
    int min_left=0, min_right=0;
    int left = 0, right = 0;
    while (right < gems.size()) {
        auto t = mp.emplace(gems[right], 1);
        if (t.second) {//새로운 보석인 경우
 
            right++;
            min_right = right;//즉시 갱신
            min_left = left;
 
        }
        else {//들고 있는 보석인 경우
            t.first->second++;
            right++;
            while (mp[gems[left]] > 1) {//왼쪽 동선을 모든 보석을 들고있는 선에서 갱신
                mp[gems[left]]--;
                left++;
                if(min_right - min_left > right - left)//동선이 짧은 경우에만 갱신
                    min_right = right, min_left = left;
            }
        }
    }
    return {++min_left, min_right};
}
 
int main() {
    auto t = solution({ "DIA", "RUBY", "DIA", "a", "DIA", "EMERALD", "SAPPHIRE", "RUBY" });
    printf("%d %d", t[0], t[1]);
}