-
[Java][백준 17298: 오큰수]아가개발자/자료구조,알고리즘 2021. 8. 3. 09:20
https://www.acmicpc.net/problem/17298
Problem
크기가 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이다.
Input
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
Output
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
Insight
1. 자신의 오른쪽에 위치하는 수 중 가장 가까이 있으면서 자신보다 큰 수를 찾아야 한다.
2. 오른쪽에 있는 수 중 자신보다 큰 수가 하나 있다면 그 뒤로 부터는 어떤 수가 오는지는 상관이 없다.
3. 숫자배열을 뒤에서 부터 확인하여 자신보다 큰 수가 있으면 pop, 없으면 push
<Process>
input:
4
3 5 2 7
1. 숫자배열을 7->2->5->3 순서로 확인
2. 7은 오른쪽에 숫자가 없기 때문에 7의 오큰수는 -1 저장 후 임시스택에 7 저장
3. 2는 임시스택에 peek인 7보다 작기 때문에 2의 오큰수 7 저장 후 임시스택에 2 저장
3. 5는 임시스택에 peek인 2보다 크기 때문에 임시스택에서 2삭제 후 다시 임시스택에 peek인 7보다 작기 때문에 5의 오큰수 7 저장 후 임시스택에 5 저장
4. 3은 임시스택에 peek인 5보다 작기 때문에 3의 오큰수 5 저장import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); Stack<Integer> stack = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); //임시스택 Stack<Integer> result = new Stack<>(); //결과 저장 할 스택 int N = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine(), " "); for(int i=0; i<N; i++){ stack.push(Integer.parseInt(st.nextToken())); } for(int i=0; i<N ; i++){ int k = stack.pop(); while(!stack2.empty() && stack2.peek() <= k ){ stack2.pop(); } if (stack2.empty()){ result.add(-1); stack2.push(k); } else{ result.add(stack2.peek()); stack2.push(k); } } while(!result.empty()){ bw.write(String.valueOf(result.pop())); if(!result.empty()){bw.write(" ");} } bw.flush(); bw.close(); } }
'아가개발자 > 자료구조,알고리즘' 카테고리의 다른 글
[Java][백준 1676: 팩토리얼 0의 개수] (0) 2021.08.06 [Java][백준 17299: 오등큰수] (0) 2021.08.04 [Java][백준 10799: 쇠막대기] (0) 2021.08.02 [Java][백준 17413: 단어 뒤집기 2] (0) 2021.08.01 [Java][백준 1406: 에디터] (0) 2021.07.31