[백준] 2493번 탑 / C++ Java

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

C++

#include<iostream>
#include<stack>
using namespace std;

int main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n,num;
   cin >> n;
   stack<pair<int,int>> s;
   for(int i = 1; i <= n; i++) {
       cin >> num;
       while(!s.empty()) {
           if(s.top().second > num) {
               cout << s.top().first << " ";
               break;
           }
           s.pop();
       }
       if(s.empty()) {
           cout << "0 ";
       }
       s.push({i,num});
   }
}

Java

package Study.week1;

import java.io.*;
import java.util.AbstractMap.SimpleEntry;
import java.util.Stack;

public class 탑 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        // C++ stack<pair<int,int>> s , Java Stack<SimpleEntry<Integer, Integer>>
        // Java에서 first 값은 getKey, Second 값은 getValue 사용
        Stack<SimpleEntry<Integer,Integer>> s = new Stack<>();
        String [] input = br.readLine().split(" ");
        int [] arr = new int[n+1];

        for(int i= 1; i <=n ;i++){
            arr[i] = Integer.parseInt(input[i-1]);
        }
        for (int i = 1; i <= n; i++) {
            while(!s.isEmpty()){
                if(s.peek().getValue() > arr[i]) {
                    bw.write(s.peek().getKey() + " ");
                    break;
                }
                s.pop();
            }
            if(s.isEmpty()){
                bw.write("0 ");
            }
            s.push(new SimpleEntry<>(i, arr[i]));
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

문제풀이

• 문제의 흐름이나 구조가 오큰수 문제랑 비슷했다. 값을 입력받고, 그 값보다 큰 수를 찾는다. 하지만 이 문제에서는 큰 수가 아닌 큰 수의 위치를 구하는 것이기 때문에, stack을 만들 때 가 아닌 pair<int,int>를 사용했다. second로 값을 비교하고, 크다면 first 값을 출력하기 위해서이다. 좌측에서 레이저를 쏘기 때문에, 우측부터 시작했다. (이건 뇌피셜이지만, 스택 문제에서 좌우에서 무언가를 비교하는 문제라면 반대부터 시작해야되는 것 같다.) while문 구조는 오큰수와 비슷하다. 스택이 비지 않을 때까지 반복하고, 스택의 second값과 입력한 값을 비교하여 크다면, 스택의 first 값 출력한다.

Comment

• 골드 문제를 보면 절대 풀 수 없다고 생각했는데, 차근차근 문제해석하고 풀었던 문제들을 생각하면서 푸니까 크게 어렵지 않았다. 나에게는 확실히 문제 기록하는게 중요한 것 같다.