백준 1874번: 스택 수열

코드: https://github.com/kgh128/Problem-Solving/blob/main/src/Baekjoon/p1874.java

1. 큐에 입력 수열 저장

수열은 먼저 들어간 것이 먼저 나와야 하니까 큐(series)에 저장한다. 배열에 저장해서 인덱스 번호로 관리해도 될 것 같기는 하다.

int N = Integer.parseInt(br.readLine());
Queue<Integer> series = new LinkedList<>(); // 입력 수열 저장

for (int i = 0; i < N; i++) {
	series.add(Integer.parseInt(br.readLine()));
}

2. 스택 연산 수행

사용되는 변수는 아래와 같다.

• stack: 연산을 수행할 때 사용할 스택

• head: series(남은 수열)에서 가장 앞에 있는 수로, 지금 스택 연산을 통해 만들고자 하는 수

• num: 스택에 넣을 수 (오름차순으로 넣으므로 1씩 증가함.)

• popHeadAtStack: 현재 head를 스택 연산을 통해 만들었는지를 나타내는 변수 (만들지 못했다면(false) 현재 head를 계속 루프 안에서 사용하고, 만들었다면(true) series에서 다음 head를 뽑아서 루프 안에서 사용한다.)

처음에는 루프 밖에서 head의 초기값을 주기 위해 series.poll()로 초기화했는데, IDE에서 뭔가 boxing하지 않고 이렇게 사용하면 NullPointerException이 뜰 수 있다고 경고를 했다. NullPointerException은 실제 값이 아닌 null을 가지고 있는 객체/변수를 호출할 때 발생하는 예외이다.

큐가 비어있는 상태에서 poll()을 수행하면 null이 반환되는데, 그러면 head에 null이 들어가게 된다. 그 상태에서 루프 안에서 head를 사용하면 null이 들어있는 변수를 호출하게 돼서 이 예외가 발생할 수 있다고 하는 것 같다.

이 문제에서는 루프 밖에서 큐가 비어있을 일은 없어서 series.remove()로 초기화하였다. series.remove()는 큐가 비어있을 때 수행하면 예외가 뜨지 null이 반환되지는 않아서 head에 null이 들어갈 일은 없다.

무한 루프를 돌면서 스택 연산을 수행한다.

a) 수열을 다 만든 경우

series에 있는 모든 원소를 다 뽑았고, 스택 연산을 통해 수열을 다 만들어서 마지막 head까지 스택에서 제거했으면 원하는 목표를 달성한 것이다. 따라서 루프를 탈출한다.

if (series.isEmpty() && popHeadAtStack) {
	break;
 }

b) 스택에 push()하는 경우

스택에 오름차순으로 push()하므로, 스택에 넣을 수 있는 숫자(num)가 원하는 숫자(head)보다 작거나 같다면 head는 아직 스택에 들어가지 않았음을 의미한다. 스택에 들어있어야만 뽑아서 수열로 만들 수 있으므로 head가 스택에 들어갈 때까지 num을 1씩 증가시켜면서 스택에 push()한다.

이때는 아직 현재 head가 스택에서 제거돼서 수열로 만들어지지 않았으므로 다음 루프 때도 현재 head를 사용해야 한다. 따라서 popHeadAtStack을 false로 유지한다. 또한 스택에 push() 연산을 했으므로 출력 버퍼에 "+"를 추가한다.

if (num <= head) {
	stack.push(num++);
	bw.append("+\n");
	popHeadAtStack = false;
}

c) 스택에서 pop()하는 경우

원하는 숫자(head)가 스택 가장 위에 있으면 뽑아서 수열로 만들 수 있으므로 pop()을 한다. 그러면 이제 현재 head는 더이상 루프에서 사용될 필요가 없으므로 popHeadAtStack을 true로 바꾼다. 또한 pop() 연산을 했으므로 출력 버퍼에 "-"를 추가한다.

else if (stack.peek() == head) {
	stack.pop();
	bw.append("-\n");
	popHeadAtStack = true;
}

d) 입력 수열을 만들 수 없는 경우

스택에는 숫자가 오름차순으로 들어가므로, 스택의 가장 위에 있는 숫자가 원하는 숫자(head)보다 크면 head가 그 숫자 밑으로 깔려있다는 의미이다. 따라서 head가 스택에는 들어있지만 가장 위에 있지 않아 뽑을 수 없는 상태이므로 더이상 수열 만들기를 진행할 수 없다. 이런 경우 입력 수열을 만들 수 없으므로 출력 버퍼를 "NO"로 초기화하고 루프를 탈출한다.

else if (stack.peek() > head) {
	bw = new StringBuilder("NO");
	break;
}

처음 풀 때는 해당 숫자가 스택에 들어있는지를 저장하는 상태 배열을 만들어서 그걸로 스택에 숫자가 들어있는지 확인하고, stack.empty()를 써서 스택이 비어있는지 확인했다. 그런데 다른 사람 풀이를 보고 기본적인 변수들의 관계만으로도 저런 조건을 만들어낼 수 있는 것을 보고 수정했다. 불필요한 변수를 줄이고 코드를 간결하게 쓰는 것을 연습해야겠다.

[다른 풀이]

나는 while 루프 하나만 사용하고, 여러 개의 if문을 사용하는 방식을 사용했는데, 루프를 2개 사용해서 하는 풀이도 있었다.

입력 수열을 배열에 저장해놓고, for문으로 해당 배열을 돌고, for문 안에서 while문을 돌면서 내 풀이의 b), c), d)를 수행하는 풀이였다. 이렇게 하면 내 풀이의 a)가 for문으로 대체되므로 head나 popHeadAtStack이 필요없다.

• head
  -> for문의 iterator 사용하면 됨.

• popHeadAtStack
  -> for문에서 다음 iterator로 넘어가면 되므로 필요 없음.

조금 더 코드가 간결해지는 효과가 있는 것 같다.