[스택] 백준 1874번

문제

1. 수열의 개수 N 제공 ( 1 <= N <= 100,000)
2. n개의 줄에는, 1이상 n이하의 정수가 1개씩 제공 (같은 정수가 2번 나오지는 않음)
3. 해당 제공된 n개의 줄의 수열을 오름차순으로 정리 (스택 이용)
4. 오름차순 정렬이 불가능할경우, "No"반환

입력	출력
8	+
4	+
3	+
6	+
8	-
7	-
5	+
2	+
1	-
	+
	+
	-
	-
	-
	-

 

 

문제 분석

• 1부터 자연수를 증가시키면서, 입력으로 주어진 숫자와 비교하며 자연수를 스택에 추가하거나 빼는 방식으로 풀이

스택 연산 방법
1. 현재 수열 값 >= 자연수
- 현재 수열값이 큰 경우, 자연수를 증가시키며 스택에 삽입
2. 현재 수열값 == 자연수
- 스택에서 값을 빼오며, 입력버퍼에 쌓아두고, 삭제진행
- 단, 같지 않을경우 스택을 이용해서 오름차순을 만들 수 없으므로 "No" 반환

 

 

수도코드

problems = 수열개수
stack 선언
count = 자연수 (증가시킬)
출력버퍼 선언
수열 리스트 선언

for( problems 개수대로 수열 입력 ) { 리스트에 추가 }

for ( 리스트(수열) 값들로 자연수와 체크 )
{
    while ( 수열 >= 자연수 ){
         스택에 추가 및 자연수 증가
         출력버퍼 저장 ("+")
     }
     
      if ( 스택 비어있을경우 )
      { " NO " 반환 }
     
      if ( 자연수 == top위치의 값){
            스택에서 값 빼오기 (삭제)
            출력버퍼 저장 ("-")
       } else{
              NO 반환 // 오름차순대로 스택에서 빼올 수 없어서
        }
}

if ( No 반환이 안되었으면 ) { 출력버퍼 출력 }

 

 

구현 코드

• get == stack.peek() 이 부분이 존재하지 않고, 넘어간다면 오름차순으로 정렬할 수가 없음

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class App {
    public static void main(String[] args) throws Exception {
        

        Scanner sc = new Scanner(System.in);
        int problems = Integer.parseInt(sc.nextLine());
        Stack<Integer> stack = new Stack<>();
        int count = 1;
        StringBuffer buf = new StringBuffer();
        Boolean result = true;
        List<Integer> list = new ArrayList<>();


        for (int i =0; i< problems; i++){
            list.add(Integer.parseInt(sc.nextLine()));
        }

        for (int get : list){
            
            while(get >= count){
                stack.push(count);
                buf.append("+\n");
                count++;
            }

            if (stack.empty()){
                System.out.println("NO");
                result =false;
                break;
            }

            if (get == stack.peek()){
                stack.pop();
                buf.append("-\n");
            }else{
                System.out.println("NO");
                result =false;
                break;
            }

        }

        if (result) {System.out.println(buf.toString());}

        

    }
}