반응형
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까지만 가능하기 때문.
따라서, 배열의 원소가
- 이미 찾아낸 스타수열의 최대 길이 ( = 배열에서 해당 원소가 등장한 횟수)보다 작을 경우
탐색할 필요가 없다. 최댓값 갱신이 불가능하기 때문
이곳의 해설을 참고했다.
[ 프로그래머스 [ 월간코드챌린지 ] 스타 수열 ] (C++)
프로그래머스의 스타수열(월간코드챌린지) 문제이다. ( 기존에 이 문제에 대한 풀이로 "가장 많이 등장한 숫자를 기준으로 스타 수열을 만드는 풀이" 로 포스팅을 하였으나, 위의 방법으로는 문
yabmoons.tistory.com
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
[Python] 프로그래머스. 2021 카카오 recruit - 메뉴 리뉴얼 (Level 2) (0) | 2021.02.02 |
---|---|
[Python] 프로그래머스. 2021 카카오 recruit - 신규 아이디 추천 (Level 1) (0) | 2021.02.01 |
[Python] 프로그래머스. 내적 (Level 1) (0) | 2020.11.12 |
[Python] 프로그래머스. 이진 변환 반복하기 (Level 2) (0) | 2020.11.11 |
[Python] LeetCode 56. merge intervals (0) | 2020.11.06 |