[BOJ] 17298번 오큰수 / 사용언어 : 파이썬(python)

※ 문제링크 

17298번: 오큰수

 

해당문제는 스택을 사용하여 풀어야하는 문제였다. 처음 문제를 읽고 반복문으로도 풀 수 있을 것 같아서 시도해봤는데 역시나 시간초과가 뜨는 것을 확인하였다. 그 후 스택을 활용하여 문제를 풀어보려고 시도를 했는데 생각보다 쉽지않아 구글링을 통해 해결방법을 글로 확인한 후 이를 직접 구현해보기 위해 계속 시도를 해보았다. 스택을 활용한 문제풀이 방법과 이를 바탕으로 내가 직접 구현해본 코드는 아래와 같다.

1. 입력값으로 받은 숫자들로 리스트를 만든다.

2. 숫자 리스트의 숫자 인덱스를 넣을 리스트를 만들고 반복문을 만든다.

3. 인덱스 리스트에 값이 있으면, 그 수보다 오른쪽에 있는 숫자들과 숫자를 비교하는 반복문을 만든다.

4. 오른쪽에 있는 숫자 중 해당 수보다 큰 수가 있으면 숫자리스트의 값을 그 수로 바꾸고 인덱스리스트를 pop한다.

5. 반복문이 종료된 후 인덱스 리스트에 있는 인덱스 값들에 해당하는 위치의 숫자리스트 숫자들을 -1로 바꾼다.

 

# 반복문을 활용한 결과 : 시간초과
number_list = [1, 10, 999999, 7, 999998, 3, 1, 4, 1000000, 3, 1000000]
N = len(number_list)
result_list = []
i = 0
k = 1
while True:
    if i == N-1:
        result_list.append(-1)
        break
    if i+k == N-1:
        if number_list[i] < number_list[i+k]:
            result_list.append(number_list[i+k])
            i += 1
            k = 1
        else:
            result_list.append(-1)
            i += 1
            k = 1
    else:
        if number_list[i] < number_list[i+k]:
            result_list.append(number_list[i+k])
            i += 1
            k = 1
        else:
            k += 1
print(*result_list)

# 스택을 활용한 방법
number_list = [1, 10, 999999, 7, 999998, 3, 1, 4, 1000000, 3, 1000000]
N = len(number_list)
check_list = [] # 인덱스 번호를 담을 리스트 생성

for index in range(N):
    check_list.append(index) # 리스트의 인덱스 넘버를 스택구조로 쌓기
    if index == N-1: # 인덱스 넘버가 리스트의 길이와 같으면 -1 값부여(가장 오른쪽 값임.)
        number_list[index] = -1
    else:
        while check_list and number_list[check_list[-1]] < number_list[index+1]: 
            # 인덱스 번호를 기록한 리스트에 값이 있고, 해당 인덱스보다 오른쪽에 있는 숫자들 중 큰 수가 있으면 그 값으로
            # 숫자 리스트의 값 변경 - 조건이 만족하지 않을 때까지 해당 구조를 반복 
            # 오른쪽에 자신보다 큰 수가 있는지 확인하고 있으면 숫자리스트에서 해당 인덱스를 가진 위치에 해당 숫자를 부여
            number_list[check_list[-1]] = number_list[index+1]
            check_list.pop()
for index in check_list: # 해당조건을 만족하지 못한 인덱스 번호를 가지는 숫자리스트의 값들은 -1로 변환
    number_list[index] = -1

print(*number_list)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.