문제 링크

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

풀이

첫 번째 시도 (메모리 초과)

  • 우선 무난하게 브루트 포스로 접근했다. 하지만 낮은 정답 비율답게 오답 처리가 되었다. 예상했던 결과였으니 더 좋은 방법을 찾아봐야 했다.
소스 코드 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] tower = new int[n];
        for (int i = 0; i < n; i++) {
            tower[i] = sc.nextInt();
        }
        
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (tower[j] >= tower[i]) {
                    result[i] = j + 1;
                    break;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int r : result) {
            sb.append(r + " ");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb.toString());
        sc.close();
    }
}

두 번째 시도 (시간 초과)

  • 첫 번째 시도와는 다르게 스택을 사용하여 접근했다. 두 개의 스택을 사용하는데, 첫 번째 원소부터 스택에 넣고 현재 요소와 스택 안의 요소를 비교하면서 현재 탑이 더 놓으면 스택에 있는 탑을 두 번째 스택에 넣고 다음 요소와 비교하는 방식을 썼다. 그리고 현재 탑에 대해 비교가 끝나면 두 번째 스택의 모든 요소를 다시 첫 번째 스택으로 옮겨 담았다.
  • 하지만 이번에는 시간 초과로 인해 오답 처리가 되었다. Scanner 대신 BufferedReader를 사용했는 데도 틀렸다면 내 풀이가 잘못된 것이다.
소스 코드 
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));
        
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> temp = new Stack<>();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= n; i++) {
            int curr = Integer.parseInt(st.nextToken());
            boolean isReceived = false;
            
            while(!stack.isEmpty()) {
                if (stack.peek() >= curr) {
                  // 이전 탑에서 수신했을 경우
                  isReceived = true;
                  break;
                } else {
                  // 수신한 탑이 없을 경우
                  temp.push(stack.pop());
                }
            }
          
          sb.append((isReceived ? stack.size() : 0) + " ");
          while(!temp.isEmpty()) stack.push(temp.pop());
          stack.push(curr);
        }
        
        sb.setLength(sb.length() - 1);
        System.out.println(sb.toString());
        br.close();
    }
}

세 번째 시도

  • 역시 내 풀이법이 잘못된 것이었다. 스택을 굳이 두 개 사용할 필요가 없었다.
  • 탑을 역순으로 순회하면서 스택이 비었으면 삽입하고, 요소가 하나라도 있으면 맨 위 요소와 비교한다. 자신보다 더 높은 탑을 찾으면 결과 배열 result에서 현재 인덱스 curr에 해당하는 값을 갱신하고 스택 연산을 계속 수행한다. 그리고 자신보다 높은 탑이 아니라면 현재 인덱스 curr를 스택에 삽입 후 루프를 계속 진행한다.
    • 여기서 스택에 삽입하는 요소는 탑의 높이가 아니라 인덱스이다.
소스 코드 
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));
        
        int n = Integer.parseInt(br.readLine());
        int[] tower = new int[n];
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < n; i++) {
            tower[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = n - 1; i >= 0; i--) {
            while(!stack.isEmpty()) {
                int curr = stack.peek();
                if (tower[i] < tower[curr]) break;
                result[curr] = i + 1;
                stack.pop();
            }
            stack.push(i);
        }
        
        for (int i = 0; i < n; i++) {
            sb.append(result[i] + " ");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb.toString());
        br.close();
    }
}