문제 링크

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

문제 설명

• 서로 다른 숫자 리스트가 주어짐

• 임의의 인접한 숫자 중 큰 숫자만 지울 수 있음

• 한 번만 작은 숫자를 지울 수 있음

• 마지막으로 남길 수 있는 숫자의 개수 리턴

틀린 풀이

• 모든 숫자를 돌면서

• 왼쪽의 큰 숫자들을 모두 제거

• 오른쪽의 큰 숫자들을 모두 제거

• 왼쪽 < 가운데 > 오른쪽이면 불가능

• 나머지 가능

• O(N^2) 이라 시간 초과

맞은 풀이

• 어차피 모두 서로 다른 수이기 때문에 모두 제거 가능

• 모두 제거하면 최솟값만 남음

• 왼쪽의 최솟값 < 현재 값 > 오른쪽의 최솟값 이면 안 됨

• 모든 수를 돌면서 최솟값을 갱신 & 가능한지 체크

• 한 번에는 DP가 안 되고 왼쪽, 오른쪽 나눠서 해야 됨

• 왼쪽, 오른쪽 중 하나라도 True 이면 가능

느낀 점

• 시간 초과가 났을 때 어떻게 시도해야 할지 감은 오는 것 같다

틀린 코드

from collections import deque


def solution(numbers):
    if len(numbers) < 3:
        return len(numbers)
    answer = 0
    for i in range(len(numbers)):
        if possible(numbers, i):
            answer += 1
    return answer


def possible(numbers, i):
    if i == 0 or i == len(numbers)-1:
        return True
    curr = numbers[i]
    q = deque(numbers)
    # left
    while True:
        n1 = q.popleft()
        n2 = q.popleft()
        if n2 == curr:
            q.appendleft(n2)
            q.appendleft(n1)
            break
        if n1 < n2:
            q.appendleft(n1)
        else:
            q.appendleft(n2)
    # right
    while True:
        n2 = q.pop()
        n1 = q.pop()
        if n1 == curr:
            q.append(n1)
            q.append(n2)
            break
        if n1 < n2:
            q.append(n1)
        else:
            q.append(n2)
    if q[0] < q[1] > q[2]:
        return False
    return True

맞은 코드

def solution(numbers):
    # left
    min_value = float('inf')
    left = [True] * len(numbers)
    for i in range(len(numbers)):
        if numbers[i] > min_value:
            left[i] = False
        else:
            min_value = numbers[i]

    # right
    min_value = float('inf')
    right = [True] * len(numbers)
    for i in range(len(numbers)-1, -1, -1):
        if numbers[i] > min_value:
            right[i] = False
        else:
            min_value = numbers[i]

    answer = 0
    for i in range(len(numbers)):
        if left[i] or right[i]:
            answer += 1
    return answer