[java]스택 수열 - 백준1874

문제



풀이

문제 해석을 하자면,

  • 입력으로 주어지는 수열의 형태를 만들 수 있냐는 문제이다.
    • 단, 1~n 까지 수를 스택에 넣었다가 뽑아서 만들어야한다.
    • 예로 4를 만들어야 하면 1~4까지 스택에 넣어야 하니 push가 4번이고, pop 1번으로 만들 수 있다.


풀이

  • 1부터 n까지 ++할 변수 cnt 를 따로 선언한다. input 은 입력 값으로 가정한다.
  • while? cnt < input 인 경우 “cnt==input” 이 될때까지 push 를 한다. (cnt==input 인 값까지 push)
  • while? 스택top==input 인건 전부 pop 를 한다.
    • 참고) 스택이 혹시나 비어 있을 수 있으므로 !st.isEmpty() 먼저 체크



코드

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    Deque<Integer> st = new ArrayDeque<>();
    int cnt = 1; //1~n
    for (int i = 0; i < N; i++) {
        int input = Integer.parseInt(br.readLine());
        //run
        while (cnt <= input) { // input 까지 cnt++ 삽입
            st.push(cnt++);
            sb.append("+").append("\n");
        }
        // 스택이 혹시나 null 일 수 있으므로 !st.isEmpty() 먼저 체크
        while (!st.isEmpty() && st.peek() == input) { // input 과 동일한건 pop
            st.pop();
            sb.append("-").append("\n");
        }

    }
    //output
    if (!st.isEmpty())
        System.out.println("NO");
    else
        System.out.println(sb);
}



느낀점

생략

댓글남기기

참고