자바 백준 17298번 문제 : 오큰수

문제 출처 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

문제 :

 

풀이 :

세 가지 풀이 방식을 생각해서 풀었고, 첫 번째와 두 번째는 보기 좋게 틀렸다.

왜 틀렸는지 코드와 함께 정리해보고, 이후 정답 코드도 정리해보자

 

오답 코드 (시간 초과) :

import java.util.*;
import java.io.*;
public class Main
{
    public StringBuilder solution(int n, int[] arr) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int[] newArr = new int[n];
        stack.push(arr[n-1]);
        newArr[n-1] = -1;
        for(int i=n-2; i>=0; i--) {
            // 스택을 다 탐색할 때까지 arr[i]보다 큰 수 찾기
            boolean none = true;
            for(int j=stack.size()-1; j>=0; j--) {
                if(arr[i] < stack.get(j)) {
                    newArr[i] = stack.get(j);
                    stack.push(arr[i]);
                    none = false;
                    break;
                }
            }
            // 스택을 다 탐색했는데 arr[i]보다 큰 수가 없을 경우 -1 입력
            if (none == true) {
                newArr[i] = -1;
                stack.push(arr[i]);
            }
        }
        for(int x : newArr) {
            sb.append(x).append(" ");
        }
        return sb;
    }
	public static void main(String[] args) throws IOException{
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i=0; i<n; i++) {
	        arr[i] = Integer.parseInt(st.nextToken());
	    }
		bw.write(String.valueOf(T.solution(n, arr)));
		bw.flush();
		bw.close();
	}
}

 

for문을 뒤에서부터 돌려 스택을 담았는데,

for문을 돌면서 arr[i]보다 큰 수를 찾을 때까지 스택을 모두 스캔하게 된다.

이 방식은 시간 복잡도가 엄청나게 증가하게 된다.

 

 

오답 코드 (틀림, 예외발생) :

import java.util.*;
import java.io.*;
public class Main
{
    public StringBuilder solution(int n, int[] arr) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int[] newArr = new int[n];
		Arrays.fill(newArr, -1);
		stack.push(arr[0]);
		for(int i=1; i<n; i++) {
			// 스택에 있는 수들 탐색
			int cnt = 1;
			while(!stack.isEmpty() && arr[i] > stack.peek()) {
				newArr[i - cnt] = arr[i];
				stack.pop();
				cnt++;
			}
			stack.push(arr[i]);
		}
		newArr[n-1] = -1;
		for(int x : newArr) {
            sb.append(x).append(" ");
        }
        return sb;
    }
	public static void main(String[] args) throws IOException{
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i=0; i<n; i++) {
	        arr[i] = Integer.parseInt(st.nextToken());
	    }
		bw.write(String.valueOf(T.solution(n, arr)));
		bw.flush();
		bw.close();
	}
}

예제 코드들은 잘 작동되던데.. 하며 이상하게 생각했지만

금방 뭐가 잘못되었는지 확인할 수 있었다.

9 7 6 8 10 와 같이 입력될 경우 

10 8 8 10 -1 가 출력되어야 하는데 -1 8 10 10 -1 가 출력된다.

 

내가 잘못 작성된 코드의 그림이다.

스택에 단순히 값을 넣어버렸기 때문에 arr에서 9에 해당하는 위치를 모르기 때문에

newArr에서 해당 위치에 arr[i] (10)을 넣을 수 없고, 내가 작성된 코드에선

연속적으로 arr[i]을 넣게 작성하여서 arr[3]에 10이 들어간 것 까진 좋은데, 

이어서 애꿎은 arr[2]에 10이 들어가버린다.

그래서 -1 8 10 10 -1 라는 잘못된 정답이 출력되어버린 것이다.

 

이렇게 두 번이나 잘못된 코드를 작성한 다음에야 해결법을 찾게 되었다.

스택에 값이 아니라 위치(인덱스)를 넣어버리면 바로 찾을 수 있겠다는 생각이 떠올랐다.

 

소스코드 (정답) :

import java.util.*;
import java.io.*;
public class Main
{
    public StringBuilder solution(int n, int[] arr) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int[] newArr = new int[n];
		Arrays.fill(newArr, -1);
		stack.push(0);
		for(int i=1; i<n; i++) {
			// 스택에 있는 수들 탐색
			while(!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
				newArr[stack.pop()] = arr[i];
			}
			stack.push(i);
		}
		newArr[n-1] = -1;
		for(int x : newArr) {
            sb.append(x).append(" ");
        }
        return sb;
    }
	public static void main(String[] args) throws IOException{
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i=0; i<n; i++) {
	        arr[i] = Integer.parseInt(st.nextToken());
	    }
		System.out.println(T.solution(n, arr));
	}
}

 

풀이 :

직접 그려서 설명해보았다..

요지는 스택에 배열의 인덱스를 담아 해당 위치를 바로 찾을 수 있다는 것이다!