-
0311_백준 알고리즘 #17298. 오큰수알고리즘 2024. 3. 11. 23:23
문제
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)을 공백으로 구분해 출력한다.
코드
1. deque로 풀이(오답!)
import sys from collections import deque N = int(input()) seq = deque(map(int, sys.stdin.readline().split())) while seq: n = seq.popleft() for num in seq: if n < num: print(num, end = ' ') break else: print(-1, end = ' ')
※ 빠르게 풀었지만 역시나 시간초과 ..ㅎ 골드 문제는 시간 초과 해결하기가 어려운 것 같당 ㅠ 38%까지 올라가서 기대했는데 까비,,
2. stack으로 풀이(정답!)
import sys N = int(input()) seq = list(map(int, sys.stdin.readline().split())) stack = [0] ans = [-1] * N for i in range(1, N): while stack and seq[stack[-1]] < seq[i]: ans[stack.pop()] = seq[i] stack.append(i) print(*ans)
※ stack이 queue보다 시간 복잡도가 낮아서 성공인 것 같다! 인덱스를 이용하기도 했고! 요즘 한 번 틀리고 나면 문제 아래에 알고리즘 분류를 보는데 오늘도 스택이 적혀있더라구 ^ 앞으론 문제 풀기 전에 보고 시작해야지 -
'알고리즘' 카테고리의 다른 글
0313_백준 알고리즘 #7983. 내일 할거야 (0) 2024.03.13 0312_백준 알고리즘 #17478. 재귀함수가 뭔가요? (0) 2024.03.12 0310_백준 알고리즘 #1260. DFS와 BFS (0) 2024.03.10 0309_백준 알고리즘 #16953. A -> B (2) 2024.03.09 0308_백준 알고리즘 #14501. 퇴사 (0) 2024.03.09