공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

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

inspirit941 2020. 11. 13. 21:44
반응형

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

 

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

 

programmers.co.kr

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

  • {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++)

프로그래머스의 스타수열(월간코드챌린지) 문제이다. ( 기존에 이 문제에 대한 풀이로 "가장 많이 등장한 숫자를 기준으로 스타 수열을 만드는 풀이" 로 포스팅을 하였으나, 위의 방법으로는 문

yabmoons.tistory.com

 

 

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
반응형