-
[JAVA] 17298번: 오큰수Algorithm/백준 알고리즘 2021. 7. 8. 17:44
문제 설명
- 크기가 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)을 공백으로 구분해 출력한다.
코드
import java.util.*; class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); Stack<Integer> stack = new Stack<>(); int[] array = new int[N]; for(int i = 0; i < N; i++){ array[i] = sc.nextInt(); } for(int i = 0; i < array.length; i++){ while(!stack.empty() && array[stack.peek()] < array[i]){ array[stack.pop()] = array[i]; } stack.push(i); } while(!stack.isEmpty()){ array[stack.pop()] = -1; } StringBuilder sb = new StringBuilder(); for(int i = 0; i < N; i++){ sb.append(array[i]).append(' '); } System.out.println(sb); } }
'Algorithm > 백준 알고리즘' 카테고리의 다른 글
[JAVA] 2069번: 최대공약수와 최소공배수 (0) 2021.07.12 [JAVA] 10430번: 나머지 (0) 2021.07.12 [JAVA] 10799번: 쇠막대기 (0) 2021.07.07 [JAVA] 17413번: 단어 뒤집기2 (0) 2021.07.07 [JAVA] 1158번: 요세푸스 문제 (0) 2021.07.06