[Baekjoon 17298번] 오큰수 문제 (with 자바)

문제

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

17298번: 오큰수

 

 

 

풀이코드 (시간초과)

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * @Date 2022/05/28
 * @URL https://www.acmicpc.net/problem/17298
 */
public class A17298_오큰수 {
    static int N;
    static int[] arr;

    public static void main(String[] args) {
        // write your code here
        A17298_오큰수 main = new A17298_오큰수();
        main.solution();
    }

    public void solution() {
        input();
        
        for (int i = 1; i < arr.length; i++) {
            int target = arr[i];

            int answer = -1;
            for (int j = i + 1; j < arr.length; j++) {
                if (target < arr[j]) {
                    answer = arr[j];
                    break;
                }
            }

            System.out.print(answer + " ");
        }
    }

    private void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        arr = new int[N + 1];

        /* 인접행렬 생성 */
        for (int i = 1; i < N + 1; i++) {
            arr[i] = sc.nextInt();
        }
    }
}

 

스트림 사용 버전 

JAVA8 문법 공부를 위해 스트림으로도 구현해보았다.

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * @Date 2022/05/28
 * @URL https://www.acmicpc.net/problem/17298
 */
public class A17298_오큰수 {
    static int N;
    static int[] arr;

    public static void main(String[] args) {
        // write your code here
        A17298_오큰수 main = new A17298_오큰수();
        main.solution();
    }

    public void solution() {
        input();
        
        for (int i = 1; i < arr.length; i++) {
            int target = arr[i];

            int first = Arrays.stream(arr, i + 1, arr.length)
                    .filter(index -> target < index)
                    .findFirst()
                    .orElse(-1);

            System.out.print(first + " ");
        }
    }

    private void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        arr = new int[N + 1];

        /* 인접행렬 생성 */
        for (int i = 1; i < N + 1; i++) {
            arr[i] = sc.nextInt();
        }
    }
}

 

 

 

풀이코드 (Stack 사용)

(참고 : https://st-lab.tistory.com/196)

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * @Date 2022/05/28
 * @URL https://www.acmicpc.net/problem/17298
 */
public class A17298_오큰수 {
    static int N;
    static int[] arr;

    public static void main(String[] args) {
        // write your code here
        A17298_오큰수 main = new A17298_오큰수();
        main.solution();
    }

    public void solution() {
        input();

        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);

        for (int i = 2; i < arr.length; i++) {
            while (!stack.isEmpty()) {
                if (arr[stack.peek()] < arr[i]) {
                    arr[stack.pop()] = arr[i];
                } else {
                    break;
                }
            }

            stack.push(i);
        }

        while(!stack.isEmpty()) {
            arr[stack.pop()] = -1;
        }

//        IntStream.range(1, arr.length)
//                .mapToObj(i -> arr[i] + " ")
//                .forEach(System.out::print);

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < arr.length; i++) {
            sb.append(arr[i]).append(" ");
        }

        System.out.println(sb);
    }

    private void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        arr = new int[N + 1];

        /* 인접행렬 생성 */
        for (int i = 1; i < N + 1; i++) {
            arr[i] = sc.nextInt();
        }
    }
}

1) 결과를 출력하는 로직에 StringBuilder을 사용해야만 시간초과가 발생하지 않는다.

//	시간초과 발생!
//        IntStream.range(1, arr.length)
//                .mapToObj(i -> arr[i] + " ")
//                .forEach(System.out::print);

StringBuilder sb = new StringBuilder();
for(int i = 1; i < arr.length; i++) {
    sb.append(arr[i]).append(" ");
}

System.out.println(sb);

 

 

디버깅

 

아래의 예시로 디버깅해보자.

4
3 5 2 7

 

1) 반복문 수행전, Stack에 첫번재 요소인 1을 삽입한다.

Stack<Integer> stack = new Stack<Integer>();
stack.push(1);

 

2) 반복문 시작 (i는 2부터)

for (int i = 2; i < arr.length; i++) {
	...
}

 

 

3) while문 수행

while (!stack.isEmpty()) {
    if (arr[stack.peek()] < arr[i]) {
        arr[stack.pop()] = arr[i];
    } else {
        break;
    }
}

 3 < 5 이므로 아래 로직이 수행된다.

arr[stack.pop()] = arr[i];

수행 후, Stack은 비어있다. 

 

 

4) stack에 i를 push한다.

stack.push(i);

 

 

5) i = 3인 for 반복문 수행되고 while문이 수행된다.

5 < 2 는 false 이므로 break 되어 while문을 빠져나간다.

 

 

6) stack에 i를 push한다.

 

 

7) i = 4인 for 반복문 수행되고 while문이 수행된다.

 

arr[3] =2 < arr[i] = 7 이므로 아래 로직이 수행된다.

arr[stack.pop()] = arr[i];

 

stack이 아직 빈 상태가 아니므로, 계속해서 while문 로직이 수행된다.

arr[2] =5 < arr[i] = 7 이므로 아래 로직이 수행된다.

arr[stack.pop()] = arr[i];

 

 

8) stack에 i를 push한다.

for문의 수행이 끝났다.

 

 

9) stack 에 남아있는 원소를 모두 -1로 정리한다.

stack에 남아있다는 것은, 오른쪽으로 자신보다 큰 원소가 없었거나, 배열 arr의 마지막 원소인 것이다.

while (!stack.isEmpty()) {
    arr[stack.pop()] = -1;
}

 

10) 결과 출력

StringBuilder sb = new StringBuilder();
for(int i = 1; i < arr.length; i++) {
    sb.append(arr[i]).append(" ");
}

System.out.println(sb);