정수 n개로 된 수열 a₁ … aₙ이 주어진다.
각 자리 i마다, i보다 오른쪽(j > i)에 있으면서 aᵢ보다 큰(같으면 안 된다) 수 가운데 가장 가까운 것 aⱼ를 구하라.
그런 수가 없으면 -1이다.
답 n개를 자리 차례대로 빈칸으로 나눠 한 줄에 출력하라.
첫 줄에 n, 둘째 줄에 a₁ … aₙ이 빈칸으로 나뉘어 주어진다.
7 2 7 3 5 4 6 8
7 8 5 6 6 8 -1
5 4 4 1 4 9
9 9 4 9 -1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
자리마다 오른쪽을 훑으면 줄어드는 수열에서 n²/2 = 5천만 번 비교해요.
C·C++는 버티지만 크레이콘은 실행 걸음 한도(약 5천만)를 넘어 멈추고, Python도 몇 초가 걸려요.
스택에 '아직 더 큰 수를 못 만난 자리'를 쌓아 두면, 새 수 x가 올 때 맨 위의 값이 x보다 작은 동안 꺼내며 답을 x로 적고, 마지막에 x의 자리를 넣어요.
자리마다 한 번 넣고 한 번 꺼내니 모두 2n번이에요.
함정 셋: 꺼내는 조건을 <=로 쓰면 같은 수를 '큰 수'로 쳐요(문제는 <).
'첫 큰 수'는 '오른쪽에서 가장 큰 수'와 달라요(1 5 3 4에서 3의 답은 5가 아니라 4).
그리고 스택에는 값이 아니라 자리를 넣어야 답을 제자리에 적을 수 있어요.
스택 쓰는 법: Python 리스트 append()/pop()/stack[-1], JavaScript·TypeScript 배열 push()/pop()/stack[stack.length - 1](TS는 pop()이 number | undefined라 !를 붙여요), Java ArrayDeque의 push()/pop()/peek()(옛 Stack 클래스보다 권장), C# Stack<int>의 Push()/Pop()/Peek(), C++ std::stack의 top()/pop()(pop()이 값을 돌려주지 않아서 top()을 먼저 읽어요), C는 배열과 top 변수.
크레이콘은 목록 끝을 맨 위로 써서 stack[stack.개수 - 1]로 보고 stack.자리빼기(stack.개수 - 1)로 꺼내요.
n = int(input())a = list(map(int, input().split())) answer = [-1] * nstack = [] # 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for i, x in enumerate(a): while stack and a[stack[-1]] < x: # x가 그 자리들의 '오른쪽 첫 큰 수' answer[stack.pop()] = x stack.append(i)print(" ".join(map(str, answer)))const [n, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); const answer = new Array(n).fill(-1);const stack = []; // 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for (let i = 0; i < n; i++) { while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) { answer[stack.pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i);}console.log(answer.join(" "));import { readFileSync } from "node:fs";const [n, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); const answer: number[] = new Array(n).fill(-1);const stack: number[] = []; // 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for (let i = 0; i < n; i++) { while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) { answer[stack.pop()!] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i);}console.log(answer.join(" "));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); int[] answer = new int[n]; Arrays.fill(answer, -1); Deque<Integer> stack = new ArrayDeque<>(); // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && a[stack.peek()] < a[i]) { answer[stack.pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i); } StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(answer[i]); System.out.println(out); }}using System;using System.Collections.Generic;using System.Linq; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int[] answer = Enumerable.Repeat(-1, n).ToArray(); var stack = new Stack<int>(); // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (stack.Count > 0 && a[stack.Peek()] < a[i]) { answer[stack.Pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.Push(i); } Console.WriteLine(string.Join(" ", answer)); }}#include <iostream>#include <stack>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; std::vector<int> answer(n, -1); std::stack<int> st; // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (!st.empty() && a[st.top()] < a[i]) { answer[st.top()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' st.pop(); } st.push(i); } for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << answer[i]; std::cout << '\n';}#include <stdio.h> #define MAXN 10000 int main(void) { static int a[MAXN], answer[MAXN], stack[MAXN]; int n, top = 0; /* stack[0..top-1]: 아직 더 큰 수를 못 만난 자리들 */ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { answer[i] = -1; while (top > 0 && a[stack[top - 1]] < a[i]) { answer[stack[--top]] = a[i]; /* a[i]가 그 자리의 '오른쪽 첫 큰 수' */ } stack[top++] = i; } for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", answer[i]); putchar('\n'); return 0;}n = 콘솔.줄읽기().수로변환();a = 콘솔.수들읽기(); answer = 새목록(n, -1);stack = []; // 아직 더 큰 수를 못 만난 자리들. 맨 위는 stack[stack.개수 - 1]반복 (i = 0; i < n; i++){ 동안 (stack.개수 > 0 && a[stack[stack.개수 - 1]] < a[i]) { answer[stack[stack.개수 - 1]] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' stack.자리빼기(stack.개수 - 1); } stack.넣기(i);}콘솔.쓰기(answer);