[Programmers] Lv3. [카카오 인턴] 보석 쇼핑 | C++

🔗문제 보러가기

프로그래머스

 

🧑‍💻풀이 과정

 

문제를 보자마자 양 쪽에 인덱스를 가리키는 변수 2개를 두고 구간을 줄여가며 구해야겠다고 생각했는데, 이게 투 포인터(Two pointer) 알고리즘이더군요. 몰랐지만 자연스럽게 사용하게 되었습니다..?

풀이 방식은 다음과 같습니다.

 

1. gems 배열을 순회하며 보석의 종류 개수를 알아낸다.
2. 시작 인덱스(start)와 끝 인덱스(end) 변수를 각각 0으로 두고, 보석의 종류 개수를 다 포함하는 구간이 될 때까지 end를 증가시킨다.
3. 보석의 종류를 모두 포함하는 가장 작은 구간까지 시작 인덱스를 증가시킨다.
4. 그 과정에서 구간, start, end 값을 갱신시키며, 다음 조건을 만족할 때까지 위 과정을 반복한다.
   • end == gems.size()인데, start > end가 되는 경우
   • end == gems.size()인데, 모든 종류 개수를 포함하지 못하는 경우

 

✏️ 소스 코드 및 결과

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

vector<int> solution(vector<string> gems) {
    // 1. 보석 종류 및 개수 세기
    int N = gems.size();
    map<string, int> counts;
    for (const string& gem : gems)
        counts[gem]++;

    int gemKind = counts.size();
    counts.clear();

    // 2. 모든 종류의 보석을 포함하는 구간을 찾으며 갱신하기
    int range = N;
    int start = 0, end = 0;
    vector<int> answer(2);

    while (true)
    {
        if (counts.size() != gemKind and end < N)
        {
            counts[gems[end++]]++;
            continue;
        }

        if (start > end or counts.size() != gemKind)
            break;

        counts[gems[start]]--;
        if (counts[gems[start]] == 0)
            counts.erase(gems[start]);
        start++;

		if (end - start < range)
		{
			range = end - start;
			answer[0] = start;
			answer[1] = end;
		}
    }

    return answer;
}