[백준] 17298번 오큰수 (파이썬)

< 백준 17298번 오큰수 - 파이썬 풀이 >

• 해당문제 링크

목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 문제에서 원하는 것은 각 인덱스마다 오큰수를 찾아서 출력하는 것이다.
  • 오큰수 = 해당 인덱스보다 더 큰 값과 인덱스를 가지는 수중 가장 왼쪽 인덱스에 위치한 수이다.
• 먼저 이진탐색을 이용하여 upper bound과 같은 방법을 사용하는 것을 생각할 수 있다. 하지만 이진탐색은 정렬이 되었을 때 사용가능하고 해당 문제에서 정렬을 한다면 값의 위치가 바뀌어서 원하는 답을 도출할 수 없다.
• 그렇다면 DP를 이용할 수 있을까? 관찰해본 결과, 이는 어려울 것 같다. 그 이유는 subsolution이 도출이 되어야하는데 중복되는 연산이 없다. 각 인덱스의 값에 따라 너무 상이한 결과를 도출하기 때문에 optical subsolution을 찾을 수 없다.
• 그래서 브루트 포스 알고리즘으로 시간 복잡도를 낮출 수 있는 방법을 생각하여 구현해야할 것 같다.
• 구현을 위해서 먼저 문제의 동작 경우를 생각해보자.
  1. [7,5,4,3, 9] -> 이런식으로 내림차순으로 쭉 내려가다가 이전 모든 수보다 더 큰 값이 나오는 경우
  2. [7,5,4,3, 4] -> 이렇게 하나의 인덱스만 더 큰 값이 나오는 경우
  3. [7,5,4,3, 6] -> 이렇게 일부의 인덱스들만 더 큰 값이 나오는 경우
• 위의 동작 경우들을 해결할 수 있는 방법을 생각해보자.
  1. 9가 나왔을때, [7,5,4,3]에게 9를 삽입한다.
  2. 4가 나왔을때, [3]에게 4를 삽입한다.
  3. 6이 나왔을때 [5,4,3]에게 6을 삽입한다.
• 즉, 값을 저장하면서 가다가 마지막으로 저장된 값보다 더 큰 값이 나오면 그 값을 삽입하고 마지막 저장된 값을 지우고 그 다음이랑 비교해보고 더 크면 똑같은 행위를 하고 그렇지 않다면 해당 값을 넣고 다시 다음 인덱스들을 찾으면 된다.
• 위의 기능은 익숙한 기능인 것 같다. 마지막에 들어온 놈이 젤 먼저 비교되고 마지막에 값을 삽입한다. 이는 스택 자료구조를 이용하면 수월하게 구현할 수 있다.

구현코드

def search_rightBiggerNumber():
  result = [-1]*N
  # 오큰수가 없다면 -1을 넣어야하기에 -1로 초기화하고 스택을 이용해서 append를 이용해서 값을 넣으면 순서에 맞지 않게 들어가기에 미리 크기를 할당하고 이를 이용
  stack = [0] # result 인덱스에 값을 넣어야하기에 index를 저장.
  for i in range(1, N):
      while len(stack) > 0: # sequence[i]보다 작은거를 전부다 값을 넣기 위함
          if sequence[stack[-1]] < sequence[i]:
              result[stack.pop()] = sequence[i]
          else: break # 더 크지 않으면 break
      stack.append(i) # 해당 인덱스도 오큰수를 찾기 위해 append

  for r in result:
      print(r, end=" ")

if __name__ == "__main__":
    N = int(input())
    sequence = list(map(int, input().split()))
    search_rightBiggerNumber()