Cooper's devlog

오큰수 :17298번 - JAVA 본문

Algorithm/Baekjoon

오큰수 :17298번 - JAVA

cooper_dev 2020. 7. 10. 20:52

1. 문제 링크

https://www.acmicpc.net/problem/17298

 

17298번: 오큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

2. 문제 설명

 

3. 문제 접근법

 

예제1 

(1) stack이 비어있을 때, stack에 index를 추가한다.

 

(2) stack이 비어있지 않을 경우, 배열 ans에 a[0(인덱스)]의 값을 추가한다.

(3) a[1] < a[2]가 아니므로, stack에 2를 추가한다.

(4) a[1] < a[3] 이므로, a[3]을 ans[1]에 추가 

(5) stack에서 뽑은 값(인덱스)으로 비교 시, a[2] < a[3] 이므로, ans[2]에 a[3] 대입

 

(6) stack에 남아있는 나머지 값 모두 -1 대입

 

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package data_structure1_practice;
 
import java.util.*;
import java.io.*;
 
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));// 리더 생성
        int n = Integer.parseInt(bf.readLine());// 사이즈 입력
        
        int[] a = new int[n];// 배열 생성
        int[] ans = new int[n];// 정답 배열 생성
        
        String[] temp = bf.readLine().split(" ");// 임시로 받고
        for (int i = 0; i < n; i++)    a[i] = Integer.parseInt(temp[i]);// int로 변환
        
        Stack<Integer> s = new Stack<>();    // 스택 생성
        s.push(0);    // 첫번째 인덱스 저장
        
        for (int i = 1; i < n; i++) {
            if (s.isEmpty())    s.push(i);// 반복문에 들어올 때 스택이 비어있으면 인덱스 저장 
            while (!s.isEmpty() && a[s.peek()] < a[i]) {// 비어있지 않고 숫자가 인덱스 가장 위쪽 숫자보다 크면
                ans[s.pop()] = a[i];// 정답 배열 중 스택의 가장 위쪽 숫자와 같은 인덱스에 i번째 숫자를 넣는다 
            }
            s.push(i);    // 다음번에 비교할 숫자를 stack에 집어넣는다
        }
        
        while (!s.empty()) {
            // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때 까지
            ans[s.pop()] = -1;
            // stack에 쌓인 index에 -1을 넣고
        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++)    bw.write(ans[i] + " ");// 출력한다
        
        bw.write("\n");
        bw.flush();
    }
}
 
 cs

 

 

'Algorithm > Baekjoon' 카테고리의 다른 글

합분해 : 2225번 - JAVA  (0) 2020.07.13
덱 :10866번 - JAVA  (0) 2020.07.10
쇠막대기 :10799번 - JAVA  (0) 2020.07.09
단어 뒤집기 :17413번 - JAVA  (0) 2020.07.09
조세퍼스 문제 : 1158번 - JAVA  (0) 2020.07.08
'Algorithm/Baekjoon' Related Articles more
Comments