[백준] 17298번: 오큰수/ Java 11

• 실패, 정답보고 이해하고 풀이

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

오큰수

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

104892

39169

27275

35.324%

문제

크기가 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)을 공백으로 구분해 출력한다.

 

나의 답안

/*
* :::::: 문제 ::::::
* - 크기가 N인 수열이 존재
* - 각 원소에 대해 오큰수 NGE 구하기
* - 오큰수는 오른쪽에 있으면서 A보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.
* - 그런 수가 없으면 -1
\*
* :::::: 출력 ::::::
* - 총 N개의 수 NGE(1) ... 을 공백으로 구분하여 출력
\*
* :::::: 구현 ::::::
\*
* */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Stack<Integer> stack = new Stack<Integer>();

        // 수열의 개수 N개
        int T = Integer.parseInt(br.readLine());
        // T개의 배열 생성
        int[] seq = new int[T];

        // 수열 공백을 기준으로 나누기
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 수열의 개수 N 개만큼 반복
        // 이중 for 문을 사용하면 시간초과, 사용 X
        for(int i = 0; i < T; i++){
            // 각 원소를 배열에 저장
            seq[i] = Integer.parseInt(st.nextToken());
        }

        /*
        * 스택이 비어있지 않으면서 AND 현재 원소가 스택의 맨 위 원소가 가리키는 원소보다 큰 경우
        * 해당 조건을 만족할 떄까지 stack 의 원소를 pop 하면서
        * 해당 인덱스의 값을 현재 원소로 바꿔준다.*/

        for(int i = 0; i < T; i++){
            while(!stack.isEmpty() && seq[stack.peek()] < seq[i]){
                seq[stack.pop()] = seq[i];
            }

            stack.push(i);
        }

        /*
        * 스택의 모든 원소를 pop 하면서 해당 인덱스의 value 를 -1로 초기화*/
        while(!stack.isEmpty()){
            seq[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < T; i++){
            sb.append(seq[i]).append(' ');
        }


        System.out.println(sb);
    }

}

• 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미하므로, 3, 5, 2, 7에서 5를 찾는 꼴을 생각해보면..          가장 바깥에(오른쪽)에 있는 수 7부터 3과 비교를 진행하면 되고, 가장 마지막에 남는 5를 출력하면 됨
• 이러한 형태는 LIFO 마지막에 들어간 수부터 꺼내는 스택 구조가 되므로 스택으로 풀이하면 된다.

 

피드백

✅ 1. 이 문제를 왜 스택으로 풀어야 하는가? (왜 LIFO 구조를 써야 할까?) 생각해보기

✔️ 핵심: 앞에서부터 진행하면서, "이전에 본 값들"을 저장하고 빠르게 비교하기 위해서.

• 오큰수는 "현재 값의 오른쪽"에서 자기보다 큰 수 중 가장 가까운 것을 찾아야 함.
• 만약 이중 for문으로 풀면 시간복잡도는 O(N^2) → 시간초과.
• 스택을 사용하면 한 번 순회만으로 해결 가능 → O(N).

✔️ 왜 LIFO가 유리하냐?

• 우리는 최근에 본 인덱스부터 검사해야 함.
• 스택은 최근에 저장한 값을 맨 위에 쌓기 때문에,
  "최근값부터 비교 → 현재값이 더 크면 pop → 그 값의 오큰수 확정"
• 즉, 가장 최근 인덱스부터 빠르게 처리할 수 있는 자료구조가 LIFO인 스택이라 적합함.

✅ 2. 배열을 애초에 -1로 초기화하는 것, 괜찮을까?

• Arrays.fill(배열,채울값)  Arrays.fill(배열,시작인덱스,끝인덱스,채울값) 메서드
• 처음부터 Arrays.fill(seq, -1); 로 초기화해두면,
• 오큰수를 못 찾은 값은 굳이 마지막에 따로 while문으로 -1 처리 안 해도 됨.

Arrays.fill(seq, -1);

이렇게 하면 코드도 더 깔끔해지고, 가독성도 좋아짐.
💡 Tip: 코테에서는 정답 배열을 따로 만들면서 -1로 초기화하는 게 더 좋은 습관

 

✅ 3. 가급적이면 주어진 input값은 수정하지 말고 정답 배열 따로 쓰기

• 주어진 seq를 그대로 유지하고, 정답을 result[] 같은 배열에 따로 저장하면:
  • 원본 유지 → 코드 안전성, 재사용성 증가
  • 협업 시 → "데이터를 불필요하게 변경하지 말 것"이 좋은 습관

 

int[] result = new int[T];
Arrays.fill(result, -1); // 기본값 -1

// 스택 로직에서
result[stack.pop()] = seq[i];

 

✅ 4. 포인터로 풀면 시간초과 -> 이중for문이기 때문

• 포인터 두 개 (i, j → j = i+1부터 끝까지 탐색) → 이중 for문 → O(N^2)
• N이 1,000,000이라면 절대 못 씀
• 스택은 한 번의 순회 (O(N)) 로 문제 해결 가능 → 이게 핵심.

 

✅ 5. Stack 대신 ArrayDeque 쓰기