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

 

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

1. 풀이

알고리즘 문제는 풀면 풀수록 좌절과 함께 내가 겸손해지는 것 같다..
처음 문제를 보고 머리속에 풀이가 떠올랐지만, 코드로 바꾸는데는 어려움이 많았다. 
오늘도 알고리즘을 풀며 한번 더 겸손해진다.

우선 문제는 수를 스택을 이용해 넣었다가 뽑아 늘어놓음으로써 수열이 완성 될 수 있는가 없는가이다.

 

된다면 push와 pop의 기록을 출력하고, 안되면 NO를 출력해주면 되는 문제이다.

 

제일 포인트는 push되는 숫자가 오름차순으로 되며, 되돌릴 수 없다는 것이다.

 

즉, 아래와 같은 상황에서는 스택 수열이 될 수 없다.

 

그러므로, 이 문제에서 제일 중요한 점은 '스택에 추가되어야 하는 수'를 나타내는 변수라고 생각한다.

 

조건식을 만들어 보면 아래와 같이 된다.

 

• cnt : 스택에 추가되어야 하는 수
• cnt < input(입력값) : cnt값이 input값과 같아질 때까지 push, 같아지면 pop
• cnt > input(입력값) : stack에서 input과 같은 값이 나올 때까지 pop을 한다. 만약 찾지 못한 경우 "NO"로 반환한다.

또한, 자바에서 String문으로 결과값을 출력하고자 +연산자를 통한 코드를 짜면 메모리 초과가 발생한다.

이는 String객체가 immutable(불변)하기 때문입니다.
즉 String객체는 한번 생성되면 할당된 메모리 공간이 변하지 않고, 계속 유지됩니다.
+ 연산자나 concat연산자를 통해서 기존 String객체에 문자열을 추가하면 기존 String객체 주소에 추가되는 것이 아닌
새로운 String객체를 만들고, 새 String 객체에 연결된 문자열을 저장하고, 그 객체를 참조하도록 되있습니다.

( 알고리즘 문제를 풀면서, 새로운 것을 하나하나 배우는 것 같다. 이 내용 또한 포스팅 할 예정이다. )

---

2. 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		Stack<Integer> stack = new Stack<Integer>();
		int cnt = 0; // 스택에 추가될 수.
		StringBuilder result = new StringBuilder(); // String쓰면 메모리 초과.
		
		while(num-- > 0) {
			int input = sc.nextInt();
			
			if(cnt < input) { 
				while(cnt < input) {
					stack.push(++cnt);
					result.append("+\n");
				}
				stack.pop();
				result.append("-\n");
			} else {
				boolean check = false;
				if(!stack.isEmpty()) { // 스택이 빌때까지 탐색
					result.append("-\n");
					if(stack.pop() == input) // input값을 찾았다면 true
						check = true;
				}
				if(!check) { // input값을 탐색하지 못했다면 NO.
					result.replace(0, result.length(), "NO");
					break;
				}
			}
		}
		System.out.println(result);
		
		sc.close();
		return;
	}
}