[C++/프로그래머스] 보석 쇼핑 (2020 카카오 인턴십)

문제

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

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

문제 요약:

보석들이 일렬로 진열되어 있을 때,

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서,

구간의 [시작 진열대 번호, 끝 진열대 번호]를 return해라.

 

가장 짧은 구간이 여러 개라면, 시작 진열대번호가 가장 작은 구간을 return해라.

 

진열대를 나타내는 gems 배열의 크기는 최대 100000이다.

풀이

[code로 만들기, 보석 종류 세기]

보석의 종류가 몇 개인지 input에서 알려주지 않는다. 따라서 gems배열을 순회하면서 보석의 종류를 count해야한다.

또한, string형태로 연산하는 것이 불편할 것으로 생각되어 string을 code로 바꿔주었다. 

 

[슬라이딩 윈도우]

gems배열의 길이가 N이라고 할 때,

각각의 시작위치(i)마다 모든 종류의 보석을 1개이상 포함하는 가장 짧은 구간을 찾게되면, O(N^2)의 복잡도가 된다.

gems배열의 최대 크기가 10^5이므로, O(N^2)의 복잡도일 때 최대 10^10번 돌기 때문에 효율성 테스트를 통과하지 못할 가능성이 크다. 

그래서 슬라이딩 윈도우방식을 사용하였다. 

 

아래의 예시에서, 보석의 종류는 0,1,2의 총 세가지 이다.

0번 진열장에서 시작하면, 2번 진열장까지 구매하면 모든 종류의 보석을 포함한다.

1번 진열장에서 시작하는 구간을 구할 때, 처음부터 다시 세는 것이 아니라 이전에 세어놓은 것을 활용하는 것이다.

0번 진열장을 버리고, 뒷부분의 진열장을 모든 종류의 보석을 포함할 때 까지 세어나간다. 

 

그림을 보는 것이 이해가 쉬울 것 같다!

슬라이딩 윈도우 예시

 

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer = {1, (int)gems.size()};
    vector<int> gem_codes; // int형태의 gems 배열
    map<string, int> codes;
    
    int code = 0;
    for (string gem: gems) {
        if (codes.count(gem)) 
            gem_codes.push_back(codes[gem]);
        else {
            codes[gem] = code;
            gem_codes.push_back(code++);
        }
    }
    vector<int> have(code);
    int end = 0;
    for (int i=0;i<gem_codes.size();i++) {
        bool flag = true;
        while(find(have.begin(), have.end(), 0) != have.end()) {
            // 모든 종류의 보석을 포함하기전에, 진열장이 끝나버린 경우를 구분하기 위함
            if (end >= gem_codes.size()) {
                flag = false;
                break;
            }
            have[gem_codes[end++]]++;
        }
        if (flag && end - (i + 1) < answer[1] - answer[0]) {
            answer[0] = i+1; answer[1] = end;
        }
        have[gem_codes[i]]--;
    }
    return answer;
}

결과

정확성 테스트

효율성 테스트