풍선 터트리기

풍선 터트리기
월간 코드 챌린지 시즌1 
261명 완료

 

https://programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

Python

리스트의 양 끝 요소는 최후까지 살아남습니다. 
리스트의 끝 요소를 최소값으로 잡고 탐색합니다. 
최소값은 탐색을 진행하면서 갱신되는데,
한 번이라도 최소였던 값들은 살아남습니다. 
현재의 최소값보다 큰 값은 탈락입니다. 
양쪽에서 진행하면 됩니다. 

아래 코드는 양쪽에서 동시에 진행했습니다. 

def solution(a):
    answer = set()
    min_a1, min_a2 = a[0], a[-1]
    for a1, a2 in zip(a, a[::-1]):
        answer.update((min_a1, min_a2))
        min_a1, min_a2 = min(a1, min_a1), min(a2, min_a2)
    return len(answer)

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.72ms, 10.2MB)
테스트 4 〉	통과 (41.77ms, 14.5MB)
테스트 5 〉	통과 (209.67ms, 33MB)
테스트 6 〉	통과 (317.36ms, 44.7MB)
테스트 7 〉	통과 (444.84ms, 56.2MB)
테스트 8 〉	통과 (436.07ms, 56.2MB)
테스트 9 〉	통과 (422.12ms, 56.2MB)
테스트 10 〉	통과 (420.40ms, 57MB)
테스트 11 〉	통과 (553.34ms, 111MB)
테스트 12 〉	통과 (563.78ms, 111MB)
테스트 13 〉	통과 (494.62ms, 86.9MB)
테스트 14 〉	통과 (564.18ms, 111MB)
테스트 15 〉	통과 (541.02ms, 111MB)

index를 이용해서 양쪽에서 진행할 수도 있겠지만.. 
zip을 쓰는 게 좀 더 파이써닉한 것 같습니다.. 

def solution(a):
    answer = set()
    min_a1, min_a2 = a[0], a[-1]
    for i in range(len(a)):
        answer.update((min_a1, min_a2))
        min_a1, min_a2 = min(a[i], min_a1), min(a[-i-1], min_a2)
    return len(answer)

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.85ms, 10.2MB)
테스트 4 〉	통과 (47.70ms, 14.2MB)
테스트 5 〉	통과 (241.38ms, 31.8MB)
테스트 6 〉	통과 (356.34ms, 42.5MB)
테스트 7 〉	통과 (502.43ms, 53.4MB)
테스트 8 〉	통과 (497.90ms, 53.4MB)
테스트 9 〉	통과 (476.20ms, 53.4MB)
테스트 10 〉	통과 (491.98ms, 53.4MB)
테스트 11 〉	통과 (616.54ms, 103MB)
테스트 12 〉	통과 (592.31ms, 103MB)
테스트 13 〉	통과 (563.66ms, 79.2MB)
테스트 14 〉	통과 (609.64ms, 103MB)
테스트 15 〉	통과 (604.12ms, 103MB)