[Programmers] 스타 수열

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/70130

코딩테스트 연습 - 스타 수열

문제의 조건대로 풀면 되는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 우선 주어진 a 내 등장한 숫자와 해당 숫자가 몇 개 나왔는지를 파악합니다.

2. 이후 문제의 조건대로 스타 수열의 길이를 구해줍니다.

2.1 "{x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다."이므로 1번에서 구한 a 내 등장한 숫자를 순서대로 순회하면서 a 내 등장한 숫자가 {a[j], a[j+1]} 집합 내 등장하는지 확인합니다.

2.2 "x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1]"이므로 2.1번의 조건을 성립한 상태에서 a[j] != a[j+1]이라는 조건도 성립해야 합니다.

2.3 2.1과 2.2 조건이 모두 성립할 경우 {a[j], a[j+1]} 집합은 스타 수열의 일부분이므로 현재 구한 부분 수열의 길이를 1 증가시켜주고 j+2부터 다시 2번의 과정을 반복해줍니다.

3. 2번에서 구한 스타 수열의 길이 중 최댓값의 두배를 반환해줍니다. (각 집합의 크기는 2이므로)

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <map>
	using namespace std;
	int solution(std::vector<int> a) {
	if (a.size() < 2)
	{
	return 0;
	}
	map<int, int> visited;
	for (int num : a)
	{
	visited[num]++;
	}
	vector<pair<int, int>> v(visited.begin(), visited.end());
	int answer = 0;
	for (auto data : v)
	{
	int num = data.first;
	int cnt = data.second;
	if (answer >= cnt)
	{
	continue;
	}
	int len = 0;
	for (int j = 0; j < a.size() - 1; j++)
	{
	if (a[j] != num && a[j + 1] != num)
	{
	continue;
	}
	if (a[j] == a[j + 1])
	{
	continue;
	}
	len++, j++;
	}
	answer = max(len, answer);
	}
	return answer * 2;
	}
	int main(void)
	{
	vector<int> a = { 0, 0, 0, 2, 3, 4, 3, 5, 3, 1 };
	cout << solution(a) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~