C++ / 프로그래머스 / 보석 쇼핑

문제

 

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

프로그래머스

문제풀이

 

어느정도 틀은 잡았는데 구현하는 부분에서 고생을 했다.

반복문을 통해 보석들의 배열을 탐색하면서, map을 이용해 기존 보석의 위치를 지우고 새 보석의 위치를 저장하고, 가진 보석들 중 가장 작은 인덱스가 시작부분으로 두고, 새 보석을 찾을 때마다 해당 위치를 끝 부분으로 뒀다.

가장 작은 인덱스를 찾으려고 벡터를 이용해 map의 value를 기준으로 정렬을 해봤는데 잘 안됐다..

그래서 다른 풀이를 참고했다.

 

보석 종류와 개수를 저장하는 map을 이용한다.

처음보는 보석이면 보석의 개수를 늘리고, 시작부분과 끝부분을 바꾼다.

 

기존 보석이면 보석의 개수를 늘리고, 보석의 개수가 2개 이상인지 판별한다.

2개 이상이면 보석의 개수를 줄이고, ++start를 한다.

start가 1 커졌으므로 다시 반복문에 의해 보석의 개수가 2개 이상인지 판별한다.

이 과정을 반복한다.

 

반복문이 종료되었으면 갱신한 부분이 현재 answer로 둔 값보다 작은 구간인지 판단을 하고, 작다면 교체한다.

 

마지막으로 문제는 첫 보석의 인덱스를 0이 아닌 1로 두므로 각각 +1씩 한다.

 

 

코드

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

vector<int> solution(vector<string> gems) {
    int idx(0), start(0);
    vector<int> answer(2, 0);
    map<string, int>gem_cnt;

    for (idx = 0; idx < gems.size(); ++idx) {
        if (gem_cnt[gems[idx]] == 0) {
            ++gem_cnt[gems[idx]];
            answer[0] = start;
            answer[1] = idx;
        }
        else {
            ++gem_cnt[gems[idx]];
            while (gem_cnt[gems[start]] > 1) {
                --gem_cnt[gems[start]];
                ++start;
            }
            if (answer[1] - answer[0] > idx - start) {
                answer[0] = start;
                answer[1] = idx;
            }
        }

    }

    ++answer[0];
    ++answer[1];
    return answer;
}