[Python] 31235번 올라올라

 

 

 

 

https://www.acmicpc.net/problem/31235

31235번: 올라올라

---

 

24/03/19

 

 

두 가지 방법으로 풀 수 있는 좋은 문제다.

 

그리디 + 스택으로도 풀 수 있고, 슬라이딩 윈도우+이분 탐색으로도 풀 수 있다.

 

개인적으로 전자가 더 쉽게 떠올릴 수 있다고 생각하지만 구현하는 데에 조금 실수가 생길 수 있고, 후자는 조금 더 어렵지만 구현하는 것이 그다지 어렵지 않아서, 어느 쪽으로 푸나 난이도는 비슷하다고 생각한다.

 

---

 

첫 번째 문제 접근 방식:

 

 

처음 접근했던 방식은 슬라이딩 윈도우+이분 탐색이었다.

 

문제에서 요구하고 있는 것은 수열 $B$가 감소하지 않는 수열이 되도록 만드는 최소한의 $k$값을 구하는 것이다.

 

수열 $B$의 $i$번째 원소 $B_i$는 $A_i$부터 $A_{i+k-1}$의 값 중에서 최댓값을 취한 것이다.

 

다시 말해, $A_i$를 포함하여 다음 $k$개의 원소들 중 최댓값이 $B_i$의 원소가 된다.

 

즉, $k$는 $B_i$를 결정짓는 구간 길이인 것이다.

 

직관적으로 생각해볼 수 있는 것은, 조건을 만족하도록 구간 길이를 최소로 잡는다면, 그보다 큰 구간 길이들은 모두 수열이 감소하지 않도록 만든다는 점이다.

 

예를 들어, $5$가 조건을 만족하도록 하는 구간 길이의 최솟값이라고 하자.

 

그러면 $A_1$부터 $A_5$까지의 최댓값이 $B_1$이 될 것이고, $A_2$부터 $A_6$까지의 최댓값이 $B_2$가 될 것이고, 마찬가지로 $A_{N-4}$부터 $A_N$까지의 최댓값이 $B_{N-4}$가 될 것이다.

 

구간 길이를 더 늘려서 $6$을 가져왔다고 해보자. 이를 사용해 만들어진 수열을 $C$라고 하자. 

 

그러면 $A_1$부터 $A_6$까지의 최댓값이 $C_1$이 될 것이다.  

 

이 $C_1$은 이전의 $B_1$보다 크면 컸지, 작지는 않을 것이다. 만약 이전의 $B_1$보다 크다면 $A_6$때문에 커진 것이고, 그러면 $C_1$은 $B_2$와 같은 값이 될 것이다.

 

마찬가지로, $A_2$부터 $A_7$까지의 최댓값이 $C_2$가 될 것이다.

 

$C_2$도 이전의 $B_2$보다 크면 컸지, 작지는 않을 것이다. 만약 이전의 $B_2$보다 크다면 $A_7$때문에 커진 것이고, 그러면 $C_2$는 $B_3$와 같은 값이 될 것이다.

 

이를 계속 반복하면, 수열 $C$도 수열 $B$처럼 감소하지 않는 수열이라고 알 수 있다.

 

조건을 만족하도록 구간 길이를 최소로 잡으면, 그보다 큰 구간 길이들은 모두 조건을 만족한다는 점은 이분 탐색을 사용할 수 있는 좋은 조건이 된다.

 

또한, 우리가 직접 구간을 한 칸씩 움직이며 기존 최댓값을 활용해 새로운 구간의 최댓값을 골라내는 행위를 하므로 슬라이딩 윈도우로 접근할 수 있다.

 

따라서 시간 복잡도는 $\mathcal{O}(N\log N)$이 될 것이라고 예상할 수 있다.

 

구현의 경우, 구간의 길이 $k$가 주어지면 만들어지는 $B$가 정말 감소하지 않는 수열인지 판단하는 is_B_not_decreasing 함수를 구현했다.

 

이 함수는 $B$가 감소하지 않는 수열이라면 True를, 아니라면 False를 반환하는 함수다.

 

$k$값을 이분 탐색 할 때 이 함수가 True라면 hi를 mid값으로 변경한다. False라면 mid값보다는 무조건 하나 커야 하므로 lo를 mid+1값으로 변경한다.

 

is_B_not_decreasing함수는 현재 구간의 최댓값과, 그 최댓값이 구간에서 몇 개 있는지를 나타내는 변수가 필요하다.

 

수열 $B$에서 감소하는 부분이 생기는 경우는, 구간을 한 칸 옮겼을 때 최댓값이 줄어든다는 말과 같다.

 

즉, 현재 구간의 최댓값이 유일하고, 구간을 오른쪽으로 한 칸 옮겼을 때 그 최댓값이 새로운 구간에 존재하지 않으며(즉, 현재 구간의 최댓값은 구간의 맨 끝에 위치해 있다), 새롭게 들어오는 원소 $A_i$가 기존 구간의 최댓값보다 더 작다면, 구간을 옮겼을 때 최댓값이 줄어들 것이다.

 

그렇지 않은 경우에는 감소하는 부분이 생기지 않는다.

 

따라서 이를 그대로 구현하면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 31235번 올라올라
# 슬라이딩 윈도우, 투 포인터, 이분 탐색
'''
접근 방법:
이분 탐색 갈기기
NlogN정도에 될 것 같다
'''
import sys
input = sys.stdin.readline

def is_B_not_decreasing(A, k):
    max_val, max_val_cnt = 0, 0
    for i in range(k):
        if A[i] > max_val:
            max_val = A[i]
            max_val_cnt = 1
        elif max_val == A[i]:
            max_val_cnt += 1
    for i in range(k, len(A)):
        if max_val == A[i-k] and max_val_cnt == 1:
            if A[i] < max_val:
                return False
            max_val = A[i]
            max_val_cnt = 1
        elif max_val == A[i-k]:
            if A[i] > max_val:
                max_val = A[i]
                max_val_cnt = 1
            elif A[i] == max_val:
                pass
            else:
                max_val_cnt -= 1
        else:
            if A[i] > max_val:
                max_val = A[i]
                max_val_cnt = 1
            elif A[i] == max_val:
                max_val_cnt += 1
    return True

def binary_search(A):
    lo, hi = 1, len(A)
    while lo < hi:
        mid = (lo+hi)//2
        if is_B_not_decreasing(A, mid):
            hi = mid
        else:
            lo = mid+1
    return lo

N = int(input())  # 수열의 길이
A = list(map(int, input().rstrip().split()))  # 수열ㅋㅋ
print(binary_search(A))

---

 

두 번째 문제 접근 방식:

 

 

두 번째 접근 방식은 그리디적 접근 방식이다.

 

우리는 수열 $B$가 감소하지 않도록 만들기 위한 것이 결국 최종 목적이다.

 

수열 $B$는 $A$의 특정 구간의 최댓값들로 정의가 된다.

 

$A = \{ 3, 1, 4, 2, 5 \}$라고 한다면, $\{3, 4, 5\}$는 $A$를 오른쪽으로 쭉 읽었을 때 최댓값이 갱신되는 수들이다.

 

$B$는 이러한 수들로 구성이 될 것이다.

 

따라서, 최댓값이 갱신되는 인덱스의 차이들 중 가장 큰 차이를 취하면 답이 된다.

 

인덱스의 차이가 곧 구간의 길이를 의미하고, $B$가 저러한 수들로만 이루어지도록 구성하려면, 구간의 길이가 충분히 길어야 하므로 인덱스의 차이들 중 최댓값을 취하면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

import sys
input = sys.stdin.readline
# stack 풀이
N = int(input())  # 수열의 길이
A = list(map(int, input().rstrip().split()))
max_val = 0
index_li = []
for i in range(N):
    if A[i] >= max_val:
        max_val = A[i]
        index_li.append(i)
index_li.append(N)
max_diff = 0
for i in range(len(index_li)-1):
    diff = index_li[i+1] - index_li[i]
    if diff > max_diff:
        max_diff = diff
print(max_diff)