[코딩테스트][백준] 🔥 백준 17298번 "오큰수" 문제: Python과 Java로 완벽 해결하고 면접 준비까지! 🔥

🔗 문제 링크

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

🕒 Python 풀이시간: 40분

from collections import deque

n=int(input())
answer=[]
stackOrigin=list(map(int,input().split()))

stack=deque()

while stackOrigin:
    peek=stackOrigin.pop()
    if len(stack)==0:
        answer.append(-1)
        stack.append(peek)
        continue
    while stack and stack[-1]<=peek:
        stack.pop()
    if len(stack)==0:
        answer.append(-1)
    else:
        answer.append(stack[-1])
    stack.append(peek)

print(*answer[::-1])

🕒 Java 풀이시간: 40분

import java.io.*;
import java.util.*;

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());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[n];
        
        for (int i = n - 1; i >= 0; i--) {
            int current = arr[i];
            while (!stack.isEmpty() && stack.peek() <= current) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(current);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(result[i]).append(" ");
        }
        bw.write(sb.toString().trim());
        bw.newLine();
        
        bw.flush();
        bw.close();
        br.close();
    }
}

📈 효율적인 큰 수 찾기: 스택을 이용한 O(N) 접근법

특정 수에서 오른쪽에 있는 수 중에서 현재의 수보다 큰 가장 왼쪽의 있는 수를 각 정답으로 가지는 것이므로 주어진 수들에서 왼쪽부터 탐색해야겠다고 생각을 하였다. 데이터의 수는 1,000,000이기 때문에 단순탐색정도로 밖에 안된다고 생각하였다. O(N) 정도로 생각하고 진행하였을 때, 현재의 수보다 큰 수를 찾되 이번엔 현재의 수에서 오른쪽에 있는 순으로 찾아야 하므로 현재의 수는 왼쪽에서 오른쪽으로 탐색하면서 탐색된 수는 스택을 통해서 담아두고 다음수와 비교할 때는 그 스택의 위에서부터 비교하는 방식을 통해 찾아가면 된다. 이 때, 큰수이기 때문에 현재 수보다 큰수가 나올 때까지 스택을 비우면 현재 수의 오른쪽에서부터 큰수를 찾아가는 과정과 같다. 큰수를 찾으면 그 큰수를 답으로 저장하고 그 위에 현재의 수를 얹으면 된다. 그렇게 되면 다음 탐색 때, 현재의 수보다 큰 수를 탐색하면서도 다음수도 고려할 수 있게 된다.

면접 관련 질문

Q. 왜 Stack 대신 ArrayDeque를 사용하였는가?
답변 : Stack은 동기화된 클래스 이므로 단일 스레드 환경에서는 불필요한 성능저하가 발생할 수 있지만 ArrayDeque는 동기화되지 않아 단일 스레드 환경에서 성능면에서 더 빠르다.

Q. BufferedReader와 BufferedWriter를 사용한 이유는?
답변 : BufferedReader와 BufferedWriter는 버퍼를 사용하여 입출력시 최적화를 위한 클래스 이므로 성능면에서 훨씬 좋기 때문입니다.

Q. 시간복잡도는 어떻게 되나요?
답변 : 이 알고리즘의 시간 복잡도는 $O(n)$으로 배열을 한번 순회하면서 각 수에 대해 스택 연산을 수행하기 때문에 N이라고 할 수 있다.

Q. StringBuilder를 사용한 이유?
답변 : StringBuilder는 문자열을 효율적으로 조작할 수 있으며 String과 다르게 새롭게 매번 객체를 할당하는것이 아니라 성능면에서도 더 빠르기 때문이다.

Q. 다른 접근 방식은?
답변 : 이중 for문을 사용하여 모든 수를 비교해가면서 찾을 수 있지만 효율성 측면에서 문제에 제시된 시간내에 알고리즘을 동작시키려면 쓸 수 없다.

Q. 스택을 사용한 알고리즘의 장점은?
답변 : 스택을 사용하면 최근에 본 요소를 추적할 수 있어 다음 큰 수를 찾는 데 효율적이다.

Q. Deque와 ArrayDeque의 차이점은?
답변 : Deque는 인터페이스며 ArrayDeque는 이를 구현한 구현체중 하나이다.

Q. 이러한 알고리즘을 적용시킬만한 추가적인 상황은?
답변 : 주식 가격을 측정할 때, 현재의 날짜보다 바로 다음으로 높은 날짜를 찾는 상황 / CPU 작업 시간 시, 다음으로 더 긴 작업을 찾는 상황 등. 현재의 값 다음에 오는 수들 중에서 바로 다음에 오는 큰 값을 찾는 경우.

이렇게 Python과 Java로 백준의 오큰수 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊