백준 17298 - 파이썬 힌트 및 풀이과정

백준 문제 중 자료구조 알고리즘의 골드단계 문제 위주로 뽑아서 풀어보고자 한다.

정답률은 45% 이하인 친구들로 랜덤 선택. 코테 푸는 수준은 여전히 허접이다.

 

 

백준 17298.

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

문제 자체는 간단해보이는데 간단한 만큼 그 생각 그대로 풀어쓴다면 (이중포문)

이중 포문으로 돌아야 하다보니 최악의 경우의 수가 1,000,000 * 1,000,000 정도이다.

당연히 틀릴 걸 알았지만 일단 떠오른 대로 써보기라도 하자 해서 써본 코드다.

 

시간초과 틀린답 O(N^2)

def num17298():
    N = int(input())
    arr = list(map(int, input().split()))
    arr.insert(0,0)
    res = []
    for i in range(1, N):
        chk = False
        for j in range(i, N+1):
            if arr[i] < arr[j]:
                res.append(arr[j])
                chk = True
                break
        if not chk:
            res.append(-1)
    res.append(-1)

    print(*res)

 

반례로 조심해야하는 부분은 아래와 같다.

#INPUT
7
4 3 2 1 2 3 4 

#OUTPUT
-1 4 3 2 3 4 -1

 

다시 머리를 좀 잘 굴려보자. 이미 힌트를 봤지만 - 스택 - 그래도 어떻게 해야하나 고민을 했다.

그리고 코드를 보니까 뭔소린지는 알겠는데 그렇게 머리굴리는건 여전히 어렵다.

 

 

 

17298 문제풀이 힌트

---

감이 아예 안오는 나같은 사람을 위해서 좀 더 힌트와 조심해야 하는 사실을 알려보자면

-arr[i:] 같은 경우는 arr를 통으로 복사해서 slicing하는 거라 시간복잡도 상으로 좋지 않다.

 

-그리고 '값이 큰 오른쪽 배열들 중 가장 왼쪽'을 구해야 하는 것이 포인트 인데 해당 특징 때문에 배열을 뒤집어서 stack 작업을 하는 것이 좋다.

 

-stack의 특징은 LIFO다. 그런만큼 값의 대체가 일어나는 조건과 함께 pop을 시행해줘야한다.

이 부분은 반례의 경우와 함께 보는 것이 작업하기 수월하다. 일단 뒤집을건데 똑같아서 헷갈릴 수 있긴 함

 

-예시로 설명

4 3 2 1 2 3 4 의 경우 stack 제일 처음에는 4 -> 3 순으로 담기고

i=3 인 2라는 숫자에 도달했을 때, 실제로 토해내야 하는 값은 "4가 아닌 3" 이다. 여기까지만 봐도 헷갈림.

 

쭉 넘겨서 stack에 4 -> 3 -> 2 -> 1 까지 담겼다고 가정하자. 그리고 다음 2라는 숫자로 넘어가게 된다.

i=5 인 2라는 숫자에 도달했고 stack은 [4,3,2,1] 이다.

 

이제 여기서 stack의 제일 뒤에 담긴 숫자와 현재 2라는 숫자와 비교를 하고 1 <= 2 ? Y then pop()

2 <= 2? Y then pop(). 3 <= 2? N then stack의 가장 마지막 수 출력.

이런 흐름으로 문제를 풀어야 한다.

 

답을 알고보면 쉬운데 이렇게 떠올리는게 난 정말 쉽지 않다고 생각한다..

 

 

 

최종 코드

---

def num17298():
    N = int(input())
    arr = list(map(int, input().split()))
    res = []
    stk = []

    arr.reverse()

    for i in range(N):

        while stk and stk[-1] <= arr[i]:
            stk.pop()

        if not stk:
            res.append(-1)
        else:
            res.append(stk[-1])
        
        stk.append(arr[i])

    res.reverse()
    print(*res)