백준 17298 <오큰수> Python

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

17298번: 오큰수

---

단순하게 모든 경우를 순회하게 되면 최악의 경우 N^2 의 시간 복잡도가 형성되어 큰 인풋에서는 시간초과가 생기게 됩니다. 따라서 순회를 최대한 줄이며 풀어야 하기 때문에 스택을 사용해 데이터 리스트 자체를 변경하며 풀었습니다.

 

[ a, b, c ] 의 데이터가 주어졌을 때 경우의 수를 생각해보겠습니다.

a>b, b>c 일 경우에는 a>c 이므로 리스트를 순회하지 않아도 됩니다.

a>b, b<c 일 경우에는 a 와 c 는 비교할 수 없으므로 다시 비교해줍니다.

 

[ 9 1 2 8 5 ] 라는 데이터를 가지고 시연을 해보겠습니다.

우선 스택은 [ 0 ] 입니다. 스택 안에 들어가는 수는 인덱스 정보입니다.

---

# stack = [ 0 ]

# now_idx, now_num = [ 0, 9 ]

# next_idx, next_num = [ 1, 1 ]

 

now_num >= next_num (9 >= 1) 이므로 다음 인덱스를 스택에 추가하고 종료합니다.

---

# stack = [ 0, 1 ]

# now_idx, now_num = [ 1, 1 ]

# next_idx, next_num = [ 2, 2 ]

 

 

now_num < next_num (1 < 2) 이므로 데이터를 변경해줍니다.

data_list[ now_idx ] = next_num  >> data_list = [ 9, 1->2, 2, 8, 5 ]

 

stack[-1] >= next_num (9 >= 2) 이므로 다음 인덱스를 스택에 추가하고 종료합니다.

---

# stack = [ 0, 2 ]

# now_idx, now_num = [ 2, 2 ]

# next_idx, next_num = [ 3, 8 ]

 

now_num < next_num (2 < 8) 이므로 데이터를 변경해줍니다.

data_list[ now_idx ] = next_num  >> data_list = [ 9, 2, 2->8, 8, 5 ]

 

stack[-1] >= next_num (9 >= 8) 이므로 다음 인덱스를 스택에 추가하고 종료합니다.

---

# stack = [ 0, 3 ]

# now_idx, now_num = [ 3, 8 ]

# next_idx, next_num = [ 4, 5 ]

 

now_num >= next_num (8 >= 5) 이므로 다음 인덱스를 스택에 추가하고 종료합니다.

---

# stack = [ 0, 3, 4 ]

# now_idx, now_num = [ 4, 5 ]

 

stack[-1] == N-1 이므로 스택안에 있는 인덱스에 해당하는 데이터를 모두 -1 로 바꿔줍니다.

data_list = [ -1, 2, 8, -1, -1 ] 이 되고 이를 출력해주면 됩니다.

---

def solution(N, data_list):

    # 스택

    stack = [0]

    # 데이터 순회

    while True:

        # 모든 데이터를 순회하면

        if stack[-1] == N-1:

            # 스택에 있는 인덱스는 모두 오큰수 -1

            for num in stack:

                data_list[num] = -1

            print(*data_list)

            return

        # 다음 수

        next_idx = stack[-1]+1

        next_num = data_list[next_idx]

        # 스택을 순회하며 더 크면 앞선 수들과 비교 후 오큰수 갱신

        while True:

            # 스택이 비거나 작거나 같으면

            if not stack or (data_list[stack[-1]] >= next_num):

                # 다음 인덱스 스택에 추가 후 종료

                stack.append(next_idx)

                break

            # 앞의 데이터들 비교 후 변경

            elif data_list[stack[-1]] < next_num:

                data_list[stack.pop()] = next_num

N = int(sys.stdin.readline().strip())

data_list = list(map(int, sys.stdin.readline().strip().split()))

solution(N, data_list)