[2020 카카오 인턴십] 보석 쇼핑

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

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

#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

vector<int> solution(vector<string> gems) {
	vector<int> answer(2);

	unordered_set<string> s;
	for (string gem : gems)
		s.insert(gem);

	unordered_map<string, int> m;

	int start = 0;
	int end;
	int cnt = 100001;

	for (end = 0; end < gems.size(); end++) {
		m[gems[end]]++;

		while (m.size() == s.size()) {
			if (end - start + 1 < cnt) {
				cnt = end - start + 1;
				answer[0] = start + 1;
				answer[1] = end + 1;
			}

			if (m[gems[start]] == 1)
				break;

			m[gems[start++]]--;
		}
	}
	return answer;
}

 

투포인터를 사용해서 풀면 되는 문제!

start, end라는 두 개의 포인터를 사용한다.

 

for문에서는 end의 값을 1씩 증가시키고,

안쪽의 while문에서는 (start~end) 범위 사이에 모든 보석이 포함되는 동안 start 포인터의 값을 증가시킨다.

 

모든 범위를 탐색하는 동안 start, end 모두 값이 증가만 하기 때문에 시간복잡도는 O(n)이 된다.