스택수열(1874)

스택수열(1874)

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

public 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));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    Stack<Integer> stack = new Stack<>();
    
    int index = 1;
    
    for(int i = 1; i <= n; i++){
      int num = Integer.parseInt(br.readLine());
      
      while(true){
        if(stack.isEmpty() || stack.peek() != num){
          if(index <= n){
              stack.push(index);
              index++;
              sb.append("+\n");
          } else {
              break;
          }
        } else {
          stack.pop();
          sb.append("-\n");
          break;
        }
      }
    }
    
    if(!stack.isEmpty()){
      sb.setLength(0);
      sb.append("NO");
    }
    
    bw.write(sb + "");
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

1) stack이 push되는 경우와 pop이 되는 경우를 구분
2) 예제1 적용하여 올바른 값 출력
3) 예제2에 대한 코드를 추가

• 여기서 처음에는 while문 안에서 index가 n보다 크면 sb를 비우고, sb에 NO를 추가하고, break를 걸게 하였다.
• 그랬더니 예제1의 경우에도 NO가 출력되어 데이터를 하나씩 따라가다보니 예제 1의 경우에도 마지막 push가 일어난 후 index++가 되므로 index가 n보다 크게됨
• 그래서 sb를 비우고 NO를 넣는 과정을 for문 밖으로 수정
• NO가되는 경우에 while에서 무한루프 발생
• 어떻게 하면 나가게 될까 하다가 index가 n을 넘은 경우 stack에 push가 되지 않고 pop의 경우만 따지면 되기에 push되는 로직에 if절 추가
• while에 들어와서 else로 빠지지 않고 if로 들어온다하더라도 index가 n을 넘은 시점에서는 아무것도 하지않고 break 되어 for문의 횟수 하나씩 소비
• for문의 반복이 끝나면 stack의 비어있는 유무를 따져 NO로 수정

4) 성공!!

• 성공
• 메모리 : 27236 KB
• 시간 : 368 ms