백준 1874 - 스택수열

스택에 오름차순으로 숫자를 하나씩 집어넣고, 입력된 숫자들을 만든다. 가령

4,3,6,8 이라면

스택에 1,2,3,4까지 넣고 4 pop(), 다음 3 pop(), 다시 5,6 push()하고 6 pop(), 7,8 push() ,8 pop()

++++--++-++-로 4,3,6,8을 만드는 것이다.

다음의 경우에는 만들 수 없는 수열이다.

1,2,5,3,4

스택에 1 push -> 1pop() -> 2push() ->2 pop() , 3,4,5 push() -> 5 pop() 이때 3을 꺼내려면 4를 먼저 pop()해야하므로 

만들 수 없는 수열이다. 

 

입력:

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력:

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

해결방법

- 처음 들어온 input이 스택에 담겨있는 value보다 크다면(혹은 빈 스택이라면), 스택에 value를 차례대로 집어넣는다.

- input과 value가 같거나 input이 작다면, 스택에서 값을 pop()한다. 이때 input과 pop()값이 같지 않다면, 만들 수 없는 수열이다.

 

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    int t = Integer.valueOf(br.readLine());
    Stack Sstack = new Stack<>();
    int input;
    int value =1;


    while(t -- >0){
        input = Integer.valueOf(br.readLine());
        //스택에 수열 넣기
        if(Sstack.empty()||(int)Sstack.peek()<input){
            while(input >= value){
                Sstack.push(value++);
                sb.append("+\n");
            }
        }
        if((int)Sstack.peek() == input){
            sb.append("-\n");
            Sstack.pop();
        }else{
            sb = new StringBuilder();
            sb.append("NO\n");
            break;
        }

    }
    bw.write(sb.toString());
    bw.flush();
    bw.close();

}

 

-배운점 

스택 이용하기

 

아래는 문제를 풀고 나중에 참고한 코드이다.

 public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.valueOf(br.readLine());
        Stack Sstack = new Stack<>();
        int input;
        int value =0;


        while(t -- >0){
            input = Integer.valueOf(br.readLine());
            //스택에 수열 넣기
            if(input > value){
                for(int i= value+1; i<=input;i++){ //value+1씩 넣어야함 중요
                    Sstack.push(i);
                    sb.append("+\n");
                }
                value = input; //input과 value 맞춰주기
            }
            else if((int)Sstack.peek() != input){
                System.out.println("NO");
                return;
            }

            Sstack.pop();
            sb.append("-\n");


        }
        System.out.println(sb);

 

- 원하는 내용을 출력하고 바로 return갈기는 것 

- 바로 종료할 코드만 else if문으로 묶고, 특별한 상황이 아니면 반복할 코드는 따로 빼두는 것이 훨  간결 

- 연습 더 하자 불불

- 반복문 

while( a > b) b ++ --> b == a 종료 안에선 a-1까지, while( a>= b) a<b일때 안에서 a==b까지 하고 종료

반복문이나 for문에서 위 조건 가끔 생각안하고 했다가 고치는 경우가 있다 처음부터 조심해라아!