[백준 - Java] 17298번 : 오큰수

문제

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. 배열 루프

 

for문으로 수열이 저장된 배열의 모든 인덱스를 순회하며

인덱스의 값과 인덱스 바로 뒤의 값을 비교해서 오큰수를 찾으면 되겠다고 생각해서 아래와 같이 구현했다.

그리고 마지막은 무조건 -1이고, 오큰수를 찾지 못한다면 -1 이니까 배열을 -1로 초기화해주었다.

 

+ Scanner 또는 syso로 인해 시간초과가 나나?라고 생각해서 입출력 Buffer로 바꾸고 제출했지만

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.stream.Stream;

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));
		
		int N = Integer.parseInt(br.readLine());
		String str = br.readLine();
		
		int[] arr = Stream.of(str.split(" ")).mapToInt(Integer::parseInt).toArray();
		int[] answer = new int[N];
		Arrays.fill(answer, -1);
		
		for(int i = 0; i < arr.length-1; i++) {
			int cnt = i;
			while(cnt != arr.length-1) {
				if(arr[cnt+1] > arr[i]) {
					answer[i] = arr[cnt+1];
					break;
				}
				cnt++;
			}
			cnt = i;
		}
		
		for(int i = 0; i < answer.length; i++) {
			bw.write(answer[i] + " ");
		}
		
		bw.flush();
		bw.close();
	}

}

결과 - 시간초과

2. 스택 이용

스택을 사용해서 시간 초과를 해결하고자 했다.

수열의 오큰수를 검사하기 위한 스택과 정답을 저장할 스택 두개를 만들고 시작.

 

Top - Down 방식 사용

예를들어 수열이 3 5 2 7 이면 7부터 시작해서 3까지 내려오면서 오큰수를 확인하는 방식이다.

//왜? 예를 들어 9 5 4 8 의 경우 첫번째 9를 스택에 집어 넣고 앞으로 들어올 5 4 8 을 검사하면 다들 9보다 작기 때문에 당최 스택에 이것

//들을 집어넣을 수도 없고 뭐 어떻게 해야할지 방법이 생각나지 않았기 때문에 뒤에서 부터 시작했다.

//뒤부터 시작하는 경우는 아래에서 설명하겠다.

 

가장 먼저 7의 경우 수열의 가장 맨 뒤의 수이기 때문에 -1이다.

그래서 정답 스택에 -1을 넣고 검사 스택에는 7을 넣는다.

 

그리고 맨 뒤에서 두번째 n-1번째 부터 for문으로 가장 첫번째 수까지를 검사하며 본격적으로 오큰수를 찾아내보자.

스택의 가장 상단에 있는 값인 peek값이 스택에 들어올 n이라는 값보다 크다면 n의 오큰수는 peek이기 때문에 정답 스택에 peek값을 넣어주고 4 역시 검사 스택에 넣어준다.

 

예를들어 9 5 4 8의 경우

가장 처음 검사스택에 8 / 정답스택에 -1이 들어있다.

그리고 이제 for문이 처음 시작되고 n = 4의 오큰수를 검사해야한다.

검사스택의 peek값인 8은 4보다 크기 때문에 4의 오큰수는 8이다.

그렇기 때문에 정답스택에 peek 값인 8을 넣어주고 검사스택에는 4를 넣어준다.

현재 검사스택 8 4 / 정답스택 -1 8

 

근데 만약 peek보다 n의 값이 크다면?

while문을 통해 검사스택을 pop() 해주면서 n보다 큰 peek값을 찾는다.

만약 스택이 비기 전에 큰 peek값을 찾는다면 그 값이 n의 오큰수이기 때문에 그 값을 정답 스택에 저장해주고 n을 검사스택에 넣어준다.

하지만 큰 값을 못찾고 결국 스택이 비게 된다면? n의 오큰수는 없기 때문에 정답스택에 -1을 넣고, 검사스택에 n을 넣어준다.

 

예를들어

현재 검사스택 8 4 / 정답스택 -1 8 인 경우에

n = 5가 들어오게 된다.

현재 검사스택의 peek값은 4이고 5보다 작다. 5보다 큰 값인 오큰수를 찾을때까지 검사스택을 pop() 해준다.

한 번 pop()을 해주게되면

현재 검사스택 8 / 정답스택 -1 8으로 peek값은 8이고 5보다 크닌까 8은 5의 오큰수이기에 정답 스택에 8을 넣고 검사스택에 5를 넣는다.

현재 검사스택 8 5 / 정답스택 -1 8 8

 

그 다음으로 n = 9가 들어오게된다.

peek 값인 8보다 9가 크기 때문에 역시나 오큰수를 찾을때까지 검사스택을 pop() 해준다.(물론 당연히 스택이 비지 않을때까지 해야겠져?)

pop() 한 번

현재 검사스택 8 / 정답스택 -1 8 8

pop() 두 번

현재 검사스택  / 정답스택 -1 8 8

결국 9보다 큰 값을 찾지 못하고 검사스택이 비게 되었다. 9의 오큰수는 없기에 정답스택에 -1을 넣어준다.

현재 검사스택  / 정답스택 -1 8 8 -1

그리고 수열의 모든 값의 오큰수를 확인했으니 검사 끝!

 

마지막으로 첫번째 수까지 반복해 수열의 모든 오큰수들을 구했다.

정답스택을 pop()하면서 정답을 출력하면 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.stream.Stream;

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));
		
		int N = Integer.parseInt(br.readLine());
		
		String str = br.readLine();
		int[] A = Stream.of(str.split(" ")).mapToInt(Integer::parseInt).toArray();
		
		Stack<Integer> st = new Stack<Integer>();
		Stack<Integer> ans = new Stack<Integer>();
		
		st.push(A[A.length-1]);
		ans.push(-1);
		
		for(int i = A.length-2; i >= 0; i--) {
			int n = A[i];
			
			if(st.peek() > n) {
				ans.push(st.peek());
				st.push(n);
			} else {
				while(!st.isEmpty() && st.peek() <= n) {
					st.pop();
				}
			if(st.isEmpty()) {
					ans.push(-1);
					st.push(n);
				} else {
					ans.push(st.peek());
					st.push(n);
				}
			}
		}
		
		//맨 마지막은 띄어쓰기를 안해야하기에 if-else문을 사용했지만, 백준에서 테스트해 본 결과 그냥 맨 마지막에 띄어쓰기 있어도 됨 
		while(!ans.isEmpty()) {
			if(ans.size() == 1)
				bw.write(ans.pop() + "");
			else
				bw.write(ans.pop() + " ");		
		}
		
		bw.flush();
		bw.close();
	}

}

 

수정 코드

그냥 스택이 비어있으면 -1

스택의 peek값보다 n이 크면 그 값이 오큰수

작으면 큰 값 찾을때까지 pop()

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.stream.Stream;

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));
		
		int N = Integer.parseInt(br.readLine());
		
		String str = br.readLine();
		int[] A = Stream.of(str.split(" ")).mapToInt(Integer::parseInt).toArray();
		
		Stack<Integer> st = new Stack<Integer>();
		Stack<Integer> ans = new Stack<Integer>();
		
		st.push(A[A.length-1]);
		ans.push(-1);
		
		for(int i = A.length-2; i >= 0; i--) {
			int n = A[i];
			
			while(!st.isEmpty() && st.peek() <= n) {
				st.pop();
			}
			
			if(st.isEmpty()) {
				ans.push(-1);
				st.push(n);
			} else {
				ans.push(st.peek());
				st.push(n);
			}
			
			st.push(n);	
		}
		
		while(!ans.isEmpty())
			bw.write(ans.pop() + " ");		

		bw.flush();
		bw.close();
	}

}

 

3. 백준 풀이

import java.util.*;
import java.io.*;
 
public class Main2 {
    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()) {
            	System.out.println("push");
                s.push(i);
                // 반복문에 들어올 때 스택이 비어있으면 인덱스 저장 
            }
            while (!s.isEmpty() && a[s.peek()] < a[i]) {
                // 비어있지 않고 숫자가 인덱스 가장 위쪽 숫자보다 크면
                ans[s.pop()] = a[i];
                // 정답 배열 중 스택의 가장 위쪽 숫자와 같은 인덱스에 i번째 숫자를 넣는다 
            }
            System.out.println("push2");
            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();
    }
}