Programmers [2020 카카오 인턴십]: 보석 쇼핑 풀이 및 코드

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

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

아래와 같이 진열된 보석 진열대에서 각 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 찾아내는 것

문제의 설명을 보고 DP인가? 라고 생각했는데 DP의 접근방식과 유사하지만 다르게 풀이했다

이러한 경우에서는 번호 3~7번까지의 구간이 R, D, D, E, S의 모든 종류를 포함하면서 가장 짧은 구간이다😉

 

1. 보석 이름은 string 형식으로 되어있기 때문에 stl map을 만들어 각각의 보석을 번호에 매핑한다

2. 진열대 번호 개수만큼 아래의 과정을 반복한ㄷㅏ

3. start(초기 0)을 하나씩 늘려가면서 start ~ cur 구간이 보석 종류를 유지하는지 체크한다

4. 구간 안의 보석 종류가 줄어들지 않을 때 까지 start를 늘린다

5. 만약 구간 안에 모든 보석 종류가 있다면 구간 최소값을 갱신한다

6. cur를 +1하고 3번으로 돌아간다

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

typedef struct {
	int s, f, d;
}str;

bool cmp(str a, str b) {
	if (a.d == b.d)return a.s < b.s;
	return a.d < b.d;
}

vector<int> solution(vector<string> gems) {
	vector<int> answer;
	vector<int> v;
	map<string, int> m;
	int count = 1;

	for (int i = 0; i < gems.size(); i++) {
		map<string, int>::iterator it;
		it=m.find(gems[i]);

		if (it == m.end()) {
			m[gems[i]] = count;
			v.push_back(count);
			count++;
		}
		else
			v.push_back(m[gems[i]]);
	}

	int start = 0;
	vector<int> check(count);
	vector<str> ans;
	for (int cur = 0; cur < gems.size(); cur++) {
		check[v[cur]]++;
		vector<int> tmp = check;
		while (start < cur) {
			tmp[v[start]]--;
			int i = 1;
			for(;i<tmp.size();i++)
				if (check[i]!=tmp[i]&&!tmp[i])break;
			if (i == tmp.size()) {
				check = tmp;
				start++;
			}
			else break;
		}
		bool b = 1;
		for (int i = 1; i < check.size(); i++)
			if (!check[i])b = 0;
		if (b)
			ans.push_back({ start,cur,cur-start+1 });
	}
	sort(ans.begin(), ans.end(), cmp);
	answer.push_back(ans[0].s+1);
	answer.push_back(ans[0].f+1);
	return answer;
}

시간복잡도:

gems배열의 크기를 N이라 할 때,

보석 종류가 모두 같아도, 모두 달라도 시간복잡도는 O(N)이다. 

 

아마 보석 종류가 루트N 정도일 때 가장 클 듯 . . . ?🤔