[백준] 17298 : 오큰수

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

소요시간 (문제 파악 10분 + 풀이 20분)

---

문제

---

시도

 

문제의 카테고리가 스택이 아니었다면 꽤 골머리를 안고 포기했을 문제였다.

 

LIFO을 고려하여 수열을 먼저 입력받고, 뒤에서부터 요소를 꺼내면서 우측 값 중 자신보다 큰 값을 찾아 비교하였다.

 

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

// A size : 1 ~ 1,000,000
// A elem : 1 ~ 1,000,000
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int max = Integer.MIN_VALUE;
        int[] answer = new int[N];
        // 뒤에서부터 요소를 꺼내면서 우측 값 중 자신보다 큰 값을 찾아 비교
        for(int i = N-1; i >= 0; i--) {
            if(A[i] >= max) {
                answer[i] = -1;
                max = A[i];
            } else {
                for(int j = i+1; j < N; j++) {
                    if(A[i] < A[j]) {
                        answer[i] = A[j];
                        break;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.print(sb);
    }
}

 

제출하니 66% 정도 진행되다가 시간 초과로 실패했다.

 

3분에 2 정도가 성공했으면 그렇게 나쁜 로직은 아니었다 생각해 어째서 실패했는지 고려해봤다.

지금 내가 짠 로직에서 시간 초과가 날 만한 시나리오는 '자신보다 큰 값이 분명히 있지만 그 값을 찾아가는 과정이 너무 긴' 경우였다.

 

그래서 다음의 로직을 추가했다.

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

// A size : 1 ~ 1,000,000
// A elem : 1 ~ 1,000,000
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int max = Integer.MIN_VALUE;
        int[] answer = new int[N];
        // 뒤에서부터 요소를 꺼내면서 우측 값 중 자신보다 큰 값을 찾아 비교
        for(int i = N-1; i >= 0; i--) {
            if(A[i] >= max) {
                answer[i] = -1;
                max = A[i];
            } else {
                for(int j = i+1; j < N; j++) {
                    if(A[i] < A[j]) {
                        answer[i] = A[j];
                        break;
                    } else if (A[i] < answer[j]) {
                        answer[i] = answer[j];
                        break;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.print(sb);
    }
}

 

780 ms로 성공했다.

---

풀이

 

Stack의 원리를 더 잘 사용한 풀이를 찾기 위해 다른 사람의 풀이를 참고했다.

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));

        int N = Integer.parseInt(br.readLine());
        int[] seq = new int[N];
        int[] stack = new int[N];    // 스택을 위한 배열
        int top = -1;    // 스택의 맨 위 원소를 가리키는 변수

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            /*
             * 스택이 비어있지 않으면서 (= top이 -1이 아닌 경우)
             * 현재 원소가 스택의 맨 위 원소가 가리키는 원소보다 큰 경우
             * 해당 조건을 만족할 때까지 스택의 원소를 pop하면서
             * 해당 인덱스의 값을 현재 원소로 바꿔준다.
             */

            while (top != -1 && seq[stack[top]] < seq[i]) {
                seq[stack[top]] = seq[i];
                top--;
            }
            top++;
            stack[top] = i;
        }

        // 스택의 모든 원소를 pop하면서 해당 인덱스의 value를 -1로 초기화
        for (int i = top; i >= 0; i--) {
            seq[stack[i]] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for (int v : seq) {
            sb.append(v).append(' ');
        }

        System.out.print(sb);
    }
}

 

728 ms로 성공했다.

나는 스택의 LIFO을 '뒤에서부터 비교를 해가면서 답을 찾는다'로 썼는데, 이 분의 풀이는 '각 원소의 값들을 비교하면서 해당하는 인덱스들만을 스택에 저장해놓는' 방식이었다.

 

참고 출처 : https://st-lab.tistory.com/196

---

알게 된 점

 

스택을 심오하구나...