백준 - 2493번 탑 (골드 5)

나는 앞에서부터 하지 않고 거꾸로 풀려고 했다.

그러나 계속해서 출력초과가 뜨면서 실패했다. 

예제는 맞았지만 잘못된 부분이 있는 듯하다.

논리적 오류인 듯 하지만 못 찾겠어서 다른 풀이를 보았다.

 

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

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());
        Stack <Integer> stack =new Stack<>();
        String[] str=br.readLine().split(" ");

        for(int i=0;i<N;i++){
            stack.push(Integer.parseInt(str[i]));
        }
        int cnt=1;
        int num=0;
        StringBuilder sb=new StringBuilder();
        Stack<Integer> result=new Stack<>();
        while(stack.size()>1){
            num=stack.pop();
            if(num<=stack.peek()){
                while(cnt>0){
                    result.push(stack.size());
                    cnt--;
                }
                cnt=1; //초기화
            }
            else{
                cnt++;
            }
        }

        while(cnt>0){
            result.push(0);
            cnt--;
        }

        while(!result.isEmpty()){
            System.out.print(result.pop()+" ");
        }
    }
}

 

 

---

다른 사람들은 다들 앞에서부터 순서대로 풀고 있었다.

 

풀이

1. 탑의 height, index를 포함할 수 있는 클래스를 선언한다.
2. top이 세워지는 순서대로 담을 수 있는 스택을 선언한다, 배열하나 만들어서 입력값들 보관
3. 세워지는 탑이 신호를 보냈을 때, 받을 수 있는 탑이 나올 때까지 top을 pop 한다.
4. pop을 하다 보니 stack이 비었다면  0을 저장
5. 방금 세워진 탑의 신호를 받을 수 있는 탑이 나온다면 stack.peek(). index를 저장

 

 

다른 사람들의 풀이를 참고하여 나만의 코드로 만들어보았다.

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

class Pair {
    int index;
    int height;

    public Pair(int index, int height) {
        this.index = index;
        this.height = height;
    }
}

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());
        String[] str = br.readLine().split(" ");
        Stack<Pair> stack = new Stack<>();
        int[] result = new int[N];
        Arrays.fill(result,-1);

        for (int i = 0; i < N; i++) {
            int height = Integer.parseInt(str[i]);

            if(stack.isEmpty())
                result[i]=0;
            else if(stack.peek().height<height){
                while(stack.peek().height<height){
                    stack.pop();
                    if(stack.isEmpty()){
                        result[i]=0;
                        break;
                    }     
                }
                if(result[i]==-1)
                    result[i]=stack.peek().index;
            }
            else if(stack.peek().height>=height){
                result[i]=stack.peek().index;
            }

            stack.push(new Pair(i+1, height));
        }

       

        for (int i = 0; i < N; i++) {
            bw.write(result[i] + " ");
        }

        bw.flush();
        bw.close();
    }
}

 

타워의 인덱스가 필요해서 새로운 클래스 Pair을 만든다는 아이디어가 필요하다. 

이 인덱스를 어떻게 처리할지 모를 땐 클래스를 만들어서 높이와 함께 담아버리자.