[프로그래머스] 보석 쇼핑

20년도 상반기 카카오 인턴십 코딩테스트 문제 보석 쇼핑 문제풀이입니다.

보석쇼핑

문제를 딱 읽자마자 아 이건 투포인터(슬라이딩 윈도우) 문제라는 것을 알 수 있었습니다. 하지만 실제 시험에선 오류를 잡지 못해서 풀지 못했습니다.. 분명 쉽게 접근을 했는데 풀지 못해서 전 매우 아쉬웠습니다.

문제는 다음과 같습니다.

저는 우선 보석종류를 뽑아 내기 위해 입력되는 모든 입력값에서 보석을 뽑아서 set에 넣었습니다. 그렇게 보석 종류를 뽑아낸 뒤 투포인터를 진행하였습니다.

가장 짧은 구간의 시작과 끝 번호를 반환해야 하는데 만약 짧은 길이가 여러개일 경우엔 번호가 가장 빠른 순으로 반환해야 하기 때문에 전 우선순위큐를 사용하였습니다.

또한, 앞 뒤 데이터를 넣고 빼기 쉬운 deque를 사용하여 보석 리스트를 관리하였고, 각 보석별로 몇개씩 놓여있는지를 확인하기 위해 map을 사용하였습니다.

이 부분은 지극히 주관적인 부분입니다. 굳이 deque를 사용 안해도 되고 map을 사용 안해도 됩니다. 전 이 자료구조들을 자주 쓰는 편이라 사용했지만 본인에게 맞는걸 사용하시면 됩니당

소스코드는 다음과 같습니다.

Source Code :

#include <string>
#include <vector>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <algorithm>
#include <fstream>
using namespace std;

set<string> Gem_List; // 보석 종류
map<string, int> Gem_Cnt; // 각 보석이 몇개씩 있는지 확인 

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.first == b.first)
			return a.second > b.second;
		return a.first > b.first;
	}
};

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

	for (string gem : gems) { // 보석 종류 저장 (중복 제거)
		Gem_List.insert(gem);
	}

	int left = 0;
	int right = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	deque<string> total_list;

	while (left <= gems.size() - Gem_List.size()) { // 보석을 다 놓을 수 없을 경우 반복 종료 
		if (Gem_Cnt.size() == Gem_List.size()) { // 모든 보석이 진열대에 놓였다면 비교 시작
			pq.push({ total_list.size(),left });
			bool chk = false;
			for (int i = left; i < right; i++) {
				if (Gem_Cnt[gems[i]] > 1) {
					left++;
					Gem_Cnt[gems[i]]--;
					total_list.pop_front();
					chk = true;
				}
				else {
					break;
				}
			}

			if (chk) {
				pq.push({ total_list.size(),left });
			}
			else {
				if (right > gems.size() - 1) {
					Gem_Cnt[gems[left]]--;
					if (!Gem_Cnt[gems[left]])
						break;
					total_list.pop_front();
					left++;
				}
				else {
					Gem_Cnt[gems[right]]++;
					total_list.push_back(gems[right]);
					right++;
				}
			}
		}
		else { // 보석이 진열대에 다 올라가지 않았다면 
			if (right > gems.size() - 1) {// 만약 마지막 위치라면 
				Gem_Cnt[gems[left]]--;
				if (!Gem_Cnt[gems[left]])
					break;
				total_list.pop_front();
				left++;
			}
			else {
				Gem_Cnt[gems[right]]++;
				total_list.push_back(gems[right]);
				right++;
			}
		}
	}
	answer.push_back(pq.top().second + 1);
	answer.push_back(pq.top().second + pq.top().first);

	return answer;
}

Summary

• 실제 시험에서 좀만 더 신중하게 풀껄 그랬다…
• 실제 시험에서 사용한 코드를 좀 개조하니 바로 풀리는거로 봐선 긴장만 안하면…
• 하지만 커스터마이징을 거의 하지 않아서 좀 비효율적이고 필요 없는 부분이 존재할 수 있습니다.
• 카카오 블라인드 코테 과연 난 .. 풀수 있을까란 의문이..

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이