손가락놀이터

문제 후기

1. 문제를 보고 이전에 프로그래머스에서 풀어본 풍선 터뜨리기와 비슷한 문제라고 생각을 했습니다. 아래에 링크를 남기겠습니다.
2. 풍선 터뜨리기 처럼 가장 큰 값을 이용해서 풀려고 했으나 반례가 있어서 다른 방법으로 풀어야했습니다.
3. 최악의 경우를 고려해봤을때 단순히 모든 배열을 탐색해도 된다 판단하여 모든 배열을 기준으로 찾기로 했습니다.
4. 각 인덱스 값을 기준으로 왼쪽부분과 오른쪽부분으로 나눠 스택과 이분탐색을 활용하여 스택을 만들었습니다.
5. 문제의 예시를 들면, 1 5 2 1 4 3 4 5 2 1이고 굵은 5가 기준이면 왼쪽 배열은 아래와 같은 순서로 이뤄집니다.
   1. [1]   비어있는 배열에 1 추가
   2. [1,2]   스택의 맨 위의 값 1보다 크므로 스택에 2 추가
   3. [1,2]   스택의 맨 위의 값 2보다 작으므로 이분탐색하여 1->1 교체 (이분탐색하면 idx가 0)
   4. [1,2,4] 스택의 맨 위의 값 2보다 크므로 스택에 4 추가
   5. [1,2,3] 스택의 맨 위의 값 4보다 작으므로 이분탐색하여 4->3 교체 (이분탐색하면 idx가 2)
   6. [1,2,3,4] 스택의 맨 위의 값 3보다 크므로 스택에 4 추가

문제링크

from sys import stdin
from bisect import bisect_left

N = int(stdin.readline())

arr = list(map(int, stdin.readline().split()))

# 만약 배열 크기가 1이면 1출력하고 종료
if len(arr) == 1:
    print("1")
else:

    answer = 0  # 결과값
    # 모든 인덱스 탐색
    for idx in range(len(arr)):
        # 왼쪽 부분과 오른쪽 부분 나눠서 실행
        # 값 부분은 stack으로 숫자 입력
        left_stack, right_stack = [], []
        
        # 왼쪽 부분
        for i in range(idx):
            # 해당값보다 큰 경우 넘어가기
            if arr[i] >= arr[idx]:
                continue
            # 첫번째 값.
            elif left_stack == []:
                left_stack.append(arr[i])
            else:
                # 만약 stack 마지막 값보다 큰 경우는 추가
                if left_stack[-1] < arr[i]:
                    left_stack.append(arr[i])
                # 만약 stack 마지막 값보다 작은 경우
                # 이분 탐색으로 해당 값이 들어갈 위치 찾아서 교체
                else:
                    left_stack[bisect_left(left_stack, arr[i])] = arr[i]

        # 오른쪽 부분
        for i in range(len(arr) - 1, idx,-1):
            # 해당값보다 큰 경우 넘어가기
            if arr[i] >= arr[idx]:
                continue
            # 첫번째 값
            elif right_stack == []:
                right_stack.append(arr[i])
            else:
                # 만약 stack 마지막 값보다 큰 경우는 추가
                if right_stack[-1] < arr[i]:
                    right_stack.append(arr[i])
                # 만약 stack 마지막 값보다 작은 경우
                # 이분 탐색으로 해당 값이 들어갈 위치 찾아서 교체
                else:
                    right_stack[bisect_left(right_stack, arr[i])] = arr[i]

        # 만약 오른쪽 부분이 있는 경우 해당값 추가
        if right_stack:
            right_stack.append(arr[idx])
        # 없는 경우에는 왼쪽 부분에 해당값 추가
        else:
            left_stack.append(arr[idx])
        # answer와 왼쪽, 오른쪽 배열 갯수 비교하여 큰 값 저장
        answer = max(answer, len(left_stack) + len(right_stack))

    print(answer)