[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이므로)

 

 

개발환경:Visual Studio 2017

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