2020 카카오 인턴쉽 코딩테스트 3번 보석 쇼핑

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

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

2020 카카오 인턴쉽 코딩테스트에 3번에 출제되었었던 보석쇼핑 문제이다.

위 링크를통하여 프로그래머스에서 풀어볼 수 있다.

 

아이디어

투포인터 알고리즘을 사용해서 풀이했다. unorder_map을 이용하여 보석의 종류를 확인하고 연달아 구매한 보석의 종류가 전체 종류와 같을때 start 지점에서 구매한 보석을 하나씩 줄여가며 최댓값을 찾아냈다.

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> solution(vector<string> gems) {

	unordered_map<string, int> gem;
	vector<int> answer(2);
	int start = 0;
	int end = 0;
	int num = 0;
	int kind;
	//최대 쇼핑 개수
	int minSize = gems.size();
	//잼의 종류 카운팅
	for (auto iter : gems)
		gem[iter]++;
	kind = gem.size();
	gem.clear();
	while (true) {
		//start -> end까지의 개수가 보석의 종류와 같을때
		if (answer[1] == kind) break;

		//모든 보석이 포함 되어있을때
		if (kind == gem.size()) {

			//start의 위치를 옮겨봄
			gem[gems[start]]--;
			if (gem[gems[start]] == 0) gem.erase(gem.find(gems[start]));
			start++;


			//길이가 최소일때 최신화
			if (minSize > end - start) {
				minSize = end - start;
				answer[0] = start;
				answer[1] = end;
			}
			continue;
		}
		//end의 위치를 옮겨봄
		if (end < gems.size()) {
			gem[gems[end]]++;
			end++;
			continue;
		};
		break;
	}
	return answer;
}