[java] 문제 011(백준 1874)

문제

스택 수열

 

교재 풀이

import java.util.Scanner;
import java.util.Stack;
public class P1874_스택수열 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[]A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    Stack<Integer> stack = new Stack<>();
    StringBuffer bf = new StringBuffer();
    int num = 1; // 오름차순 수
    boolean result = true;
    for (int i = 0; i < A.length; i++) {
      int su = A[i]; // 현재 수열의 수
      if (su >= num) { //현재 수열 값 >= 오름차순 자연수 : 값이 같아 질 때까지 push()수행
        while (su >= num) { // push()
          stack.push(num++);
          bf.append("+\n");
        }
        stack.pop();
        bf.append("-\n");
      }
      else {  //현재 수열 값 < 오름차순 자연수: pop()을 수행하여 수열 원소를 꺼냅니다
        int n = stack.pop();
        // 스택의 가장 위의 수가 만들어야 하는 수열의 수 보다 크다면 수열 출력 불가능
        if (n > su) {
          System.out.println("NO");
          result = false;
          break;
        } //
        else {
          bf.append("-\n");
        }
      }
    }
    if (result) System.out.println(bf.toString());
  }
}

 

설명

교재 설명 읽어 보면 이해 됨

 

내 풀이 => 24.6.3 시도만 하고 틀린 풀이

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

public class Main
{
	public static void main(String[] args) throws IOException {
// 		1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열
// 		스택에 push하는 순서는 반드시 오름차순을 지키도록 한다
// 		임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다
		
// 		첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다
// 		둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다.
// 		    물론 같은 정수가 두 번 나오는 일은 없다.
		    
// 	    입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다
// 	        push연산은 +로, pop 연산은 -로 표현
// 	        불가능한 경우 NO
        
//         입력 
//             8
//             4
//             3
//             6
//             8
//             7
//             5
//             2
//             1
//                 n이 8임 -> 8개의 수, 1~8이 각각 하나씩 나옴
//         출력 
//             +
//             +
//             +
//             +
//             -
//             -
//             +
//             +
//             -
//             +
//             +
//             -
//             -
//             -
//             -
//             -
//                 1 2 3 4 푸쉬 -> 팝 팝하면 4 3 나옴 -> 5 6 푸쉬 -> 팝해서 6 -> 7 8 push -> 8 pop 7 pop -> 5 pop 
//                 어떤 조건으로 푸쉬하고 어떤 조건으로 팝해야 할까?
//                     반대로 생각하면 어떨 때  no를 출력해야 할까?
//         입력 
//             5
//             1
//             2
//             5
//             3
//             4
//                 이게 no일 때인데 왜 no를 판단할 수 있을가?
//                 stack: 1 push pop -> 2 push pop -> 3 4 5 push -> 5 pop -> 
//                 3 4 순으로 푸쉬해야 해서 푸쉬했는데, 출력은 3 4 순으로 나와야 함 
//                 그러니 안 됨 
//                 일반화하면?
                    
//         출력 
//             NO
//         접근법
//             핵심은 무조건 push를 오름차순을 지켜야 한다는 점 
//             즉 1 2 3 4 이렇게 계속 해야 한다는 점
//             pop할 때의 순서가 입력한 수열과 같아야 하니까 
            
//             모르겠고, 그냥 아무렇게나 가능성 나열해보자 
//                 그냥 1 2 3 4 이런 식으로 계속 push해준다
//                 그러다가 출력해야 하는 수(즉 수열에 해당하는 수)에 도달하면 바로 pop 
//                 위 두 개를 반복하다가 pop을 하려고 할 때, 현재 top 부분이 낮은 수일 때 혹은 높은 수일 때, 
//                 즉 수열에 해당하지 않는 수일 때 no를 출력함 
//         슈도코드
//             n을 입력받음 
//             scanner로 n번 반복해서 수열 받고 배열로 받음 
            
//             스택을 선언하고, stack<Integer>
//             핵심 로직
//                 일단 무작정 오름차순대로 순서대로 1 2 3 4 이런 식으로 ppush해준다
//                     그러다가 출력해야 하는 수열의 값에 해당하게 되면 pop을 해준다
//                     pop을 해야 할 때 top부분이 해당 수가 아닐 때 no를 출력 
//                         해당 수보다 크기가 클  때 그런건가? 아님 작을 때도 포함되는 건가? 
        
        Scanner sc=new Scanner(System.in);
        StringBuffer sb=new StringBuffer();
        int n=sc.nextInt();
        
        int[] suyeol=new int[n];
        for(int i=0;i<n;i++){
            suyeol[i]=sc.nextInt();
        }
        
        int index=0; // 수열 배열에서 출력해야 하는 값을 가리키는 포인터 
        int k=1; // 계속 오름차순으로 push해줄 때 쓰는 변수고요, 1씩 증가함, 반복마다 
        Stack<Integer> stack=new Stack<>();
        while(k<=n+1){
            // 팝 부분 
            while(!stack.isEmpty() && stack.peek()==suyeol[index]){
                if(index==suyeol.length-1){
                    stack.pop();
                    sb.append("-");    
                } else{
                    stack.pop();
                    sb.append("-\n");
                }
                
                index++;
            }
            
            //푸쉬 부분 
            stack.push(k++);
            if(k>=n+2){
                System.out.println("NO");
                break;
            }
            if(index==suyeol.length-1){
                sb.append("+");    
            } else{
                sb.append("+\n");
            }
            
            // 1 2 3 4 > 4 3 팝 -> 5 6 푸쉬 -> 6 팝 -> 7 8 푸쉬 -> 8 7 팝 => 이 케이스는 됨 
            // 1 push pop -> 2 push pop -> 3 4 5 push -> 5 pop -> 
            
        }
        
        System.out.println(sb.toString());

	}
}

 

지저분 한 것 뿐 아니라 너무 좀 그럼.

여기서 이걸 바탕으로 어거지로 되게 할 수는 있을 것 같지만

토대가 부실하고, 어거지로 하더라도 몇 시간은 해야 간신히 되거나

아님 아예 처음부터 다시 갈아엎거나 해야 할 것 같아

1시간 제한시간 끝난 후 더 이어가지 않고 답을 봄