Softeer Level 4 징검다리 2 Python [반례 포함]

문제 링크

https://softeer.ai/practice/6290

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
input = sys.stdin.readline
N = int(input())
stones = list(map(int, input().split()))

def dpOfLIS(stones, N):
    dp = [0 for _ in range(N)]
    def binarySearch(stack, height):
        left, right = 0, len(stack) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if stack[mid] < height:
                left = mid + 1
            else:
                right = mid - 1
        return left

    stack = []
    for idx in range(N):
        height = stones[idx]
        currentLocation = binarySearch(stack, height)
        # 위치를 계산 하기 위한 스택을 사용중
        # 현재 위치가 지금 배열중에서 제일 큰 경우 stack에 append를 해준다.
        if currentLocation == len(stack):
            stack.append(height)
        # 작은 경우에는 현재 val의 위치를 stack에 넣는다.
        else:
            stack[currentLocation] = height
        # 스택 사용은 이쯤하고 dp에 현재의 위치를 넣어준다.
        dp[idx] = currentLocation
    return dp

ascDP = dpOfLIS(stones, N)
descDP = dpOfLIS(stones[::-1], N)[::-1]
print(max([ascDP[idx] + descDP[idx] for idx in range(N)]) + 1)

반례

12 100 1 2 3 4 5 10 9 8 7 6 121 답 : 10 5 1 2 3 4 5 답 : 5 5 5 4 3 2 1 답 : 5 5 1 4 2 5 3 답 : 4 12 100 11 12 13 10 9 8 14 15 7 6 200 답 : 8

풀이 방법

1. 이진 탐색을 사용하면 쉽게? 풀 수 있는 문제
2. 순방향 리스트를 값 하나를 꺼내서 스택에서의 위치를 찾는다. 
3. 위치는 즉, 현재 값 까지의 오름차순 배열 수이면서 현재 값보다 작은 값들의 개수가 된다.
4. dp에 현재 값의 idx에 위치를 저장한다.
5. return dp
6. 역방향도 위와 같이 하는데 여기서 주의할 점은 dp를 다시 뒤집어준다.
   1. 뒤집어주지 않으면 리스트의 배열이 꼬이기 때문이다.
   2. 쉽게 말하면 배열을 뒤집었다가 다시 뒤집어서 원상복구 시킨 셈이다.
7. 뒤집어준 뒤에 최대 값을 찾고 +1을 더해준다.
   1. +1을 해주는 이유는 자기 자신을 뺀 돌들의 개수가 되기 때문에 1을 더해준다.

느낀점

• 우선 쉽지 않았고 하루 종일 걸렸다.
• 현재의 idx를 저장시키는 방식을 몰랐고 이진탐색을 해야 한다는 것을 나중에 알았다.
• LIS(최장 증가 부분 수열) 알고리즘에 대해서 알게되었고 그 변형이라고 볼 수 있다.
• 처음 소프티어 Lv. 4를 풀어봤는데 기존 알고리즘을 응용할 수 있어야 풀 수 있다.
• 다음에 LIS에 대해서 글을 쓸 예정이다.