[백준]1874 스택 수열 - 자바/Java

1874번: 스택 수열

🌱풀이

알고리즘

1. 1부터 1씩 증가하는 자연수 Stack 연산을 통해 입력되는 연산을 표현할 수 있는지 묻는 문제.
2. 현재 자연수가 입력 값보다 작으면 같아질 때까지 반복한다.
3. 현재 자연수가 입력 값보다 크면 stack.pop()을 통해 stack에 들어있는 값을 빼가며 확인한다.
4. 만약 현재 자연수가 입력 값보다 크면서, stack.pop()으로 나온 값이 현재 자연수보다 작으면 표현이 불가능한 순열이므로 “NO”를 출력해야한다.

현재 자연수가 입력 값보다 크면 할 수 있는 행동은 pop 메소드를 통해 stack의 값을 빼는 것(stack엔 값이 차례대로 쌓여있으므로 뺄수록 작아진다)밖에 없다. 이 때 stack에 쌓인 최상단, 즉 최고 값이 현재 자연수보다 작으면 해당 자연수를 표현할 방법은 없다.

💡 메모리 : 101280KB, 시간 852ms

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		int[] number = new int[N];
		for(int i = 0; i<N; i++) number[i] = sc.nextInt();
		Stack<Integer> stack = new Stack<>();
		int index = 1;
		boolean result = true;
		
		for(int i = 0; i<N; i++) {
			int seq = number[i];
			if(seq >= index) {
				while(seq >= index) {
					stack.push(index);
					sb.append("+\\n");
					index++;
				}
				stack.pop();
				sb.append("-\\n");
			}
			else {
				int tmp = stack.pop();
				//표현이 불가능한 조건
				if(tmp > seq) {
					System.out.println("NO");
					result = false;
					break;
				}
				else {
					sb.append("-\\n");
				}
			}
		}
		if(result) System.out.println(sb.toString());
		sc.close();
	}
}

---

🪴코드 리뷰

옛날에 풀었던 코드인데 어떻게 이런 발상을 했나싶다. 애초에 입력되는 값을 배열에 저장할 필요가 없기는 하다. if문의 조건 분기 순서를 잘 설정해서 코드가 상대적으로 간결해졌다.

과거의 나는 현재의 나보다 똑똑했던 걸로..

💡 풀이자 : 본인, 메모리 : 97128KB, 시간 844ms

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<>();

		int N = in.nextInt();
		int start = 0;
		int idx = N;
		// N 번 반복
		Loop: while (idx != 0) {
			idx--;
			int num = in.nextInt();
			if (num > start) {
				// start + 1부터 입력받은 value 까지 push를 한다.
				for (int i = start + 1; i <= num; i++) {
					stack.push(i);
					sb.append('+').append('\\n'); // + 를 저장한다.
				}
				start = num; // 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화
			}
			// top에 있는 원소가 입력받은 값과 같이 않은 경우
			else if (stack.peek() != num) {
				sb.setLength(0);
				sb.append("NO");
				break Loop;
			}
			stack.pop();
			sb.append('-').append('\\n');

		}
		System.out.println(sb);
	}
}

 

a가 현재 표현해야 하는 수열의 값, count 변수가 차례로 증가하는 현재 자연수이다. +5는 어디서 튀어나왔는지 모르겠다.

💡 풀이자 : wlxh9595 메모리 : 29216KB, 시간 340ms

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

//스택 수열(1874번)
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int count = 1;

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(br.readLine());
            while(count <= N+5){
                if(stack.empty()){
                    stack.push(count);
                    sb.append("+").append("\\n");
                    count++;
                }else{
                    if(stack.peek() < a){
                        stack.push(count);
                        sb.append("+").append("\\n");
                        count++;
                    }else if(stack.peek() > a){
                        stack.pop();
                        sb.append("-").append("\\n");
                    }else{
                        stack.pop();
                        sb.append("-").append("\\n");
                        break;
                    }
                }
            }
        }
        if(count > N+5){
            System.out.println("NO");
        }else{
            System.out.println(sb);
        }
    }
}

 

보자마자 이게 뭐지????가 육성으로 튀어나왔던 코드.. 문제 해결에만 집중하는 일반 코드에서는 볼 수 없는 메소드가 구현되어 있었다.

nextInt()메소드는 아무래도 사용자가 직접 값을 입력받고 반환하는 것 같다. Scanner나 BufferedReader를 사용하지 않고 해당 기능을 직접 구현했다. 뭐하는 사람이지

로직을 살펴보면 Stack 자료구조를 사용한게 아니라 정수형 배열을 선언해서 stack의 기능을 대신하도록 했다. 어차피 LIFO 구조니까 배열의 마지막 단만 조작하면되니, Stack은 배열로도 충분히 커버가 가능하구나.

top 변수의 역할은 stack 배열의 인덱스이다. 최종적으로 top이 -1이 되면 표현이 가능한거고, -1이 되기 전에 while문이 끝났으면 표현이 불가능한 것으로 NO를 출력한다.

stack의 최상단 인덱스를 변수로 선언하고, 이렇게 잘 맞물리게 구현했다는게 정말 대단하다. 사실 코드를 분석한 지금도 로직을 완벽히 이해하진 못했다. 그냥 이런 식으로 작동하겠구나, 정도지.

💡 풀이자 : jeuk817 메모리 : 16604KB, 시간 160ms

public class Main {

	public static void main(String[] args) throws Exception {
		int N = nextInt();
		int[] A = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = nextInt();
		}
		
		int[] stack = new int[N];
		int top = -1;
		StringBuilder sb = new StringBuilder();
		int index = 0;
		for(int i = 1; i <= N; i++) {
			while(top != -1 && stack[top] == A[index]) {
				top--;
				index++;
				sb.append("-\\n");
			}
			stack[++top] = i;
			sb.append("+\\n");
		}
		
		while(top != -1 && stack[top] == A[index]) {
			top--;
			index++;
			sb.append("-\\n");
		}
		
		System.out.println(top == -1 ? sb : "NO");
	}

	static final int SIZE = 1 << 13;
	static byte[] buffer = new byte[SIZE];
	static int index, size;
	static int nextInt() throws Exception {
		int sign = 0;
    	int n = 0;
    	byte c;
    	while ((c = read()) <= 32);
    	if(c == 45) {
    		sign = 1;
    		c = read();
    	}
    	do n = (n << 3) + (n << 1) + (c & 15);
    	while ((c = read()) > 47 && c < 58);
    	return sign == 0 ? n : ~n + 1;
    }
	static byte read() throws Exception {
        if (index == size) {
            size = System.in.read(buffer, index = 0, SIZE);
            if (size < 0) buffer[0] = -1;
        }
        return buffer[index++];
    }
}

---

Conclusion

• 스택을 활용한 문제 풀이는 아직 조금 어색하다.