[백준][Java] 2493번 탑 (스택, 구현) #2

#2

풀긴 풀었는데 조건식을 깔끔하게 쓸 수도 있는건데 더럽게 풀었다..

깔끔한 조건문을 찾는 것은 어떤 식으로 해야하는걸까?

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        String[] str = br.readLine().split(" ");
        Stack<int[]> st = new Stack<>();
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<str.length; i++) {
            int h = stoi(str[i]);
            
            while(!st.isEmpty() && st.peek()[1]<h)
                st.pop();
            
            if(st.isEmpty()) 
                sb.append("0 ");
            else 
                sb.append(st.peek()[0]+" ");
            
            st.push(new int[] {i+1, h});
        }
        
        System.out.println(sb.toString());
        
        
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}

 

↑(조건문 수정)

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        String[] str = br.readLine().split(" ");
        Stack<int[]> st = new Stack<>();
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<str.length; i++) {
            int h = stoi(str[i]);
            
            if(st.isEmpty()) {
                sb.append("0 ");
                st.push(new int[] {i+1, h});
            }
            else {
                while(true) {
                    if(st.isEmpty()){
                        sb.append("0 ");
                        st.push(new int[] {i+1, h});
                        break;
                    }
                    
                    if(st.peek()[1]<h)
                        st.pop();
                    else {
                        int[] wall = st.peek();
                        sb.append(wall[0]+" ");
                        st.push(new int[] {i+1,h});
                        break;
                    }
                }
            }
        }
        
        System.out.println(sb.toString());
        
        
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}

 

 

 

 

 

 

 

 

완전탐색 절대 X

O(n)으로 끝내야함

Stack으로 탑의 높이와 순서를 배열로 push를 해주는데,

 

stack.peek() 해주면서

현재 탑의 높이보다 낮은 높이면 pop()해주고,

현재 탑의 높이보다 높은 높이면

그 탑이 문제에서 요구하는 레이저 신호를 수신하는 탑임 

그리고 stack에 push해주는데,

stack에 들어 있는 탑의 높이 중 가장 큰 값은 아니지만, 탑의 순서는 가장 최근이므로

문제에서 요구하는 수신하는 탑의 후보군이 될 수 있음

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        String[] inputStr = br.readLine().split(" ");
        int[] height = new int[N+1];
        for (int i=1; i<=N; i++) {
            height[i] = stoi(inputStr[i-1]);
        }
        Stack<int[]> st = new Stack<>();
        
//        bw.write("0 ");
//        st.push(new int[] {height[1],1});
        
        for(int i=1; i<=N; i++) {
            int curr = height[i];
            
            while(true) {
                if(st.isEmpty()) {
                    bw.write("0 ");
                    st.push(new int[] {curr, i});
                    break;
                }
                if(st.peek()[0]<curr)
                    st.pop();
                else {
                    bw.write(st.peek()[1]+" ");
                    st.push(new int[] {curr, i});
                    break;
                }
            }
        }
        
        
        bw.write("");
        bw.flush();
        bw.close();
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
    
}