문제 정보
https://www.acmicpc.net/problem/17298
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
접근방법
시간초과나서 의미 없긴 하지만...
2중 for 문을 이용해서 기준이 되는 i 숫자와 i+1 의 값을 가지는 j 숫자를 비교한다.
j 가 크면 오큰수를 발견한 것이기 때문에 리스트에 j를 넣는다.
만약 0번 숫자가 가장 크면 j와 관련된 for문을 전부 끝내고 -1 을 집어 넣는다.
n-1 번째 숫자는 오큰수를 가질 수 없기 때문에 모든 for 문이 끝나면 -1 을 넣어준다.
이러면 시간초과 난다...
1차 풀이(오답)
n = int(input())
nums = list(map(int, input().split()))
# 오큰수
RB = []
for i in range(n - 1):
for j in range(i, n):
if nums[i] < nums[j]:
RB.append(nums[j])
break
else:
RB.append(-1)
else:
RB.append(-1)
print(*RB)
접근 방법 그대로 푼 코드 예제 답은 나온다. 하지만 n 과 수열의 범위가 1,000,000 이기 때문에
최악의 경우를 만나면(모든 숫자를 다 검사해야 하는 경우) 시간초과가 나서 실패한다.
단순히 deque나 readline 을 사용하면 해결할 수 있을 것이라고 생각해서 제출해 봤지만 의미는 없었다.
2차 풀이(오답)
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
RB = []
idx = []
st = []
for i in range(n - 1):
if nums[i] > nums[i + 1]:
st.append(nums[i])
idx.append(i)
else:
RB.append(nums[i + 1])
if len(st) != 0 and st[-1] < nums[i + 1]:
RB.append(nums[i + 1])
st.pop()
idx.pop()
else:
RB.append(-1)
if len(st) != 0:
for j in idx:
RB.insert(j, -1)
print(*RB)
유튜브에서 오큰수 관련 해설을 보고 제출한 코드
세개의 스택을 만들어서(답관련 스택, 값 스택, 인덱스 스택)
기준 숫자가 오른쪽 숫자보다 클때 값 스택과 인덱스 스택에 각각 해당하는 수를 넣어준다
기준 숫자가 오른쪽 숫자보다 작을때, 답 스택에 오큰수를 저장하는데, 만약 스택에 있는 숫자보다
오큰수가 더 크다면 스택 숫자의 오큰수도 될 수 있기 때문에 똑같이 답 스택에 넣어주고 스택에서 수를 빼준다.
for 문을 전부 다 돌면 답 스택의 마지막에 -1 을 넣고
아직 스택에 숫자가 남아있다면 오큰수를 만나지 못한 숫자이기 때문에 답 스택의 해당 위치에 -1을 넣어준다.
똑같이 시간 초과가 나왔는데 아무래도 내장 메서드를 이용하면서 느려졌기 때문인 것 같다.
3차 풀이(정답)
import sys;
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
st = []
for i in range(n):
while st:
if nums[i] > nums[st[-1]]:
nums[st[-1]] = nums[i]
st.pop()
else:
st.append(i)
break
if len(st) == 0:
st.append(i)
for i in st:
nums[i] = -1
print(*nums)
인덱스를 사용한다는 점에서는 동일하지만 가능하면 내장메서드를 사용하지 않게 했다.
마지막 숫자도 그냥 스택에 넣어서 마지막에 한번에 체크해 줄 수 있게 해 주었다.
택에 값이 남아있으면 인덱스를 통해 해당 위치의 숫자를 -1 로 바꿔서 오큰수를 만나지 못한 경우를 체크해 줬다.
nums 의 값을 직접 변경시켜 주니까 계속해서 append 할 필요가 없어서 시간이 훨씬 줄어드는 것 같다.
아쉬운 코드
import sys;
sys.stdin = open('sample.txt')
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
dap = [-1] * n
idx = []
st = []
for i in range(n - 1):
if nums[i] > nums[i + 1]:
st.append(nums[i])
idx.append(i)
else:
dap[i] = nums[i + 1]
if len(st) != 0 and st[-1] < nums[i + 1]:
while st and st[-1] < nums[i + 1]:
dap[idx[-1]] = nums[i + 1]
st.pop()
idx.pop()
print(*dap)
반례를 꽤나 많이 통과하는 코드인데 틀려서 좀 아쉽다
느낀점
아직 골드를 풀 정도의 실력은 아니라고 생각하는데 단계별로 풀어보기에도 있었고
bfs, dfs, 백 트래킹 이런 문제들을 풀다보면 티어가 낮아도 실버더라...
추석 연휴에 드라이브 하면서 휴대폰으로 보고 이렇게 하면 되겠다! 하고 생각했던게 1번 풀이였다.
골드치곤 쉽네 하고 음주코딩 했는데 골드는 역시 골드였다... 만만한게 아니다
그동안 애써 무시했던 시간복잡도와 공간복잡도에 대해서 생각해야 하는 시기가 다가올 것 같다
아직 구현력은 딸리고 남의 코드를 봐도 내것으로 만들지 못하는 상황인데 코테 너무 두렵다...
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 2589 보물섬 (파이썬) (0) | 2022.09.14 |
---|---|
백준 1991 트리 순회 (파이썬) (0) | 2022.09.12 |
백준 1759 암호 만들기 (파이썬) (0) | 2022.09.09 |
백준 15649 N과 M (4) (파이썬) (0) | 2022.09.07 |
백준 15649 N과 M (2) (파이썬) (0) | 2022.09.06 |