백준 17298번 바로가기

📌스택(Stack)

Last In First Out

스택이란 가장 마지막에 들어온 데이터가 가장 먼저 빠져나가는 형태의 자료구조 이다.

• 단순히 넣고(Push) 빼는(Pop) 기능밖에 없다.
• Push와 Pop 모두 시간복잡도가 O(1) 즉, 상수시간밖에 안걸린다.

👉스택 내에서 특정 데이터를 탐색하려면 O(N) 시간이 필요하다.

Python에서는 List로 구현한다.

stack = [] #stack이라는 이름의 list 선언
stack.append(Value) #Value를 삽입 (Push)
stack.pop() #가장 마지막에 Push된 값 삭제 (Pop)

---

📌큐(Queue)

First In First Out

큐란 가장 처음 들어온 데이터가 가장 먼저 빠져나가는 형태의 자료구조 이다.

• 스택과는 반대의 개념이다.
• 스택과 똑같은 시간복잡도를 가진다.

Python에서는 collections 라이브러리에서 deque를 import하여 사용한다.

👉사실 deque가 큐와 스택의 기능을 모두 포함하는 자료구조이긴 하지만, 스택만 쓸꺼면 대부분 리스트로 구현한다.

from collections import deque

queue = deque([]) #queue라는 이름의 deque 선언
queue.append(Value) #Value를 삽입 (Push)
queue.popleft() #먼저 들어온 값 삭제 (Pop)

👉위에서 말했듯 deque가 앞에서도 뺄 수 있고, 뒤에서도 뺄 수 있기때문에, pop()과 popleft()로 어디서 뺄지 구분해준다.

---

📌백준 17298 오큰수

수열의 크기와 수열이 주어진다.
이때, 수열의 각 원소 중 원소보다 오른쪽에 있고, 해당 원소보다 큰 수중에서도 제일 왼쪽에 있는 수가 오큰수이다.
이런 수가 없을 경우 오큰수는 -1이 될때, 오큰수들을 구하는 문제이다.

처음엔 시간초과를 생각하지 않고, 큐를 이용해서 접근해보았다.

# queue 사용한 코드
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())

arr = list(map(int, input().split()))

def nge(s):
    que = deque([])
    for i in range(s, n):
        if arr[s] < arr[i]:
            que.append(arr[i])

    if que:
        return que.popleft()
    else:
        return -1

for i in range(n):
    print(nge(i), end=' ')

시간초과가 발생한다.

👉for문 안에서 for문을 사용하는 nge함수를 호출했기 때문에, 시간복잡도가 O(n^2)만큼 걸린다.

결국 for문을 줄이는 방법을 찾아야했다.

stack을 이용해서 거꾸로 오큰수를 찾아나간다.

# stack 사용한 코드
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())

stack = list(map(int, input().split()))
NGE = deque([-1])
top = stack[-1]

for i in range(n-1):
    temp = stack.pop()
    if temp > stack[-1]:
        NGE.appendleft(temp)
    elif top > stack[-1]:
        NGE.appendleft(top)
    else:
        NGE.appendleft(-1)
        top = stack[-1]

for i in NGE:
    print(i, end=' ')

이 코드는 오답이다. 맞왜틀?

👉로직이 잘못되었다. 가장 큰 값이 먼저 스택에 들어가버리면 top값을 초기화를 안해주기 때문이다.

완전히 새로운 로직으로 다시풀었다.

전체코드

import sys
input = sys.stdin.readline

n = int(input())

arr = list(map(int, input().split()))
NGE = [-1 for i in range(n)]
stack = [0]

for i in range(1, n):
    while stack and arr[stack[-1]] < arr[i]:
        NGE[stack.pop()] = arr[i]
    stack.append(i)

print(NGE)

처리가 안된 원소만 탐색하는 코드이다.

스택에 처리가 안된 원소를 넣고, 오큰수를 찾고 나면 처리해주는 로직이다.

---

📌고찰

• 시간복잡도를 항상 염두에 두고 로직을 결정해 나가야한다.
• insert() 함수는 그 뒤에 있는 모든 원소를 한칸씩 미루는 연산을 해야하므로, 시간복잡도에서 매우 불리하다.

---