보석 쇼핑

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

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

1, DP로 풀었을 시 O(n^2)이기 때문에 시간초과 결과로 실패

 

2, 투포인터 알고리즘을 이용하여 O(N+M)으로 해결

 

소스코드

#include <set>
#include <vector>
#include <string>
#include <map>
#include <utility>
using namespace std;


vector<int> solution(vector<string> gems) {
    vector<int> answer;
    set<string> jewelry;
    set<string> search;
    pair<int, int> check;
    map<string, int> count;
    int v_size;
    int aim_size;
    int start = 0, end = 0;
    int len;

    v_size = gems.size();

    for (int i = 0; i < v_size; i++) {
        jewelry.insert(gems[i]);
    }
    aim_size = jewelry.size();

    check = make_pair(0, aim_size - 1);

    len = gems.size()+1;
    
    count[gems[0]]++;
    search.insert(gems[0]);

    if (search.size() == aim_size) {
        if (len > (end - start + 1)) {
            check.first = start;
            check.second = end;
            len = end - start + 1;
        }
    }

    while (true) {

        if (start == end && end == v_size - 1) break;

        if (search.size() == aim_size) {

            if (len > (end - start + 1)) {
                check.first = start;
                check.second = end;
                len = end - start + 1;
            }
            
            count[gems[start]]--;

            if (count[gems[start]] == 0) search.erase(search.find(gems[start]));
            start++;
        }
        else {
            if (end != v_size - 1) {
                end++;
                count[gems[end]]++;
                search.insert(gems[end]);

            }
            else {
                count[gems[start]]--;
                if (count[gems[start]] == 0) search.erase(search.find(gems[start]));
                start++;
            }
        }
    }

    answer.push_back(check.first + 1);
    answer.push_back(check.second + 1);

    return answer;
}

 

1) set을 이용하여서 보석의 수를 구함

 

2) 주워진 보석들을 순회

- start와 end에서 쇼핑을 진행한다고 생각함

- count map은 start와 end사이에 있는 보석들의 수를 저장

- search set은 start와 end사이에 있는 보석을 저장하여 종류의 수를 판별

- 모든 보석을 포함하면 답을 갱신하는 로직을 구현하고 start혹은 end포인터를 움직여 count와 search를 갱신함

- start와 end를 움직이는 경우는 다음과 같다.

1) 사이에 있는 보석의 종류가 부족할 시 end를 증가

2) 사이에 있는 보석의 종류가 모든 졸유를 포함 할 시 start를 증가

3) end가 마지막 포인트에 있으면 start를 증가

4) start와 end가 마지막 인덱스에 있으면 종료