[Python] 프로그래머스. 스타 수열 (Level 3)

programmers.co.kr/learn/courses/30/lessons/70130

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

문제의 조건에 따르면 "스타수열을 생성하기 위한 핵심 공통값"이 반드시 존재해야 한다.

• {x[0], x[1]} ... {x[2n-2], x[2n-1]} 의 공통원소가 1개 이상이기 위해서는, 각 쌍마다 공통값이 최소 한 개는 있어야 한다는 의미.

따라서, a 배열에 있는 각각의 원소를 기준으로 '해당 원소가 공통값으로 적용되는 스타수열의 길이' 최댓값을 찾아야 한다.

 

이 때, 각 원소가 a 배열에 몇 번 등장했는지가 중요하다.

배열에 등장한 횟수가 많을수록, 스타 수열의 길이가 길어질 수 있기 때문.

 

예컨대 입출력 예시 #3을 보면

[0,3,3,0,7,0,2,0] 배열에서 0은 4번, 3은 2번 존재한다.

0이 4개 있으므로, 생성할 수 있는 스타수열의 최대 길이는 [0,3,3,0,7,0,2,0]로 8까지 가능하지만

3은 2개뿐이므로, 2개인 3을 전부 사용한다 해도 [0,3,3,0]로 4까지만 가능하기 때문.

 

따라서, 배열의 원소가

• 이미 찾아낸 스타수열의 최대 길이 ( = 배열에서 해당 원소가 등장한 횟수)보다 작을 경우
  탐색할 필요가 없다. 최댓값 갱신이 불가능하기 때문

 

이곳의 해설을 참고했다.

yabmoons.tistory.com/610

[ 프로그래머스 [ 월간코드챌린지 ] 스타 수열 ] (C++)

 

 

	from collections import Counter
	def solution(a):
	# a 배열 element 각 원소의 등장횟수를 센다.
	elements = Counter(a)
	answer = -1
	# a에 있는 각 원소 k를 기준으로
	# k값을 기준으로 스타수열을 만들 수 있는지 검증한다.
	for k in elements.keys():
	# k의 등장횟수가 스타수열에 사용된 공통인자 횟수보다 작거나 같으면
	# 더 계산할 필요가 없다.
	if elements[k] <= answer:
	continue
	common_cnt = 0
	idx = 0
	while idx < len(a)-1:
	# 조건에 만족하지 않을 경우, 다음 idx로 넘어간다.
	# - a[idx]와 a[idx+1] 둘 다 k가 없는 경우: 공통값 k가 없음
	# - a[idx] == a[idx+1]인 경우: 조건에 위배
	if (a[idx] != k and a[idx+1] != k) \
	or (a[idx] == a[idx+1]):
	idx += 1
	continue
	# 스타수열 원소로 추가할 수 있는 경우, k 원소가 사용된 횟수를 1 증가시킨다
	common_cnt += 1
	# 다음 배열 탐색을 위해서는, idx를 2 증가시켜야 한다.
	idx += 2
	# 스타수열 완성을 위해 공통원소 k가 사용된 횟수 최댓값을 구한다.
	answer = max(common_cnt, answer)
	if answer == -1:
	return 0
	else:
	# 공통원소가 answer만큼 사용됐으면, 실제 배열의 길이는 2배.
	return answer * 2

view raw [프로그래머스] 스타 수열.py hosted with ❤ by GitHub