종이를 접는 과정을 시뮬레이션하는 것이 너무 어려워서 종이접기의 결과를 어떻게 단순히 표현할 수 있을지 생각하게 되었습니다.
완벽하게 접힌 ($1$부터 $N$까지 순서대로 나열된) 종이는 위쪽에서 바라보았을 때 각 숫자마다 왼쪽, 오른쪽, 혹은 둘 모두의 접힌 면을 가지고 있습니다.
접힌 면으로 연결된 숫자들을 접힌 면의 방향을 고려하여 선으로 이으면 두 가지 규칙을 발견할 수 있습니다.
- 연속한 숫자가 같은 편의 선을 가질 수 없다.
예를 들어 1-2가 오른쪽 접힌 면을 가지고, 2-3이 다시 오른쪽으로 접힌 면을 가지는 상황은 발생할 수 없습니다. (다시 강조하자면 위쪽에서 바라보았을 때 기준입니다.)
- 선은 서로 겹칠 수 없다.
1-3이 오른쪽으로 접힌 면을 가진 동시에 2-4가 오른쪽으로 접힐 수는 없습니다.
2번 규칙을 잘 살펴보면, 올바른 괄호 문자열을 판단하되 각 괄호에 고유한 값이 부여되어 있는 문제임을 알 수 있습니다.
각 수마다 2개의 열린 괄호와 닫힌 괄호를 생성하므로 괄호의 총 개수는 $2N$개.
스택을 사용하면 이 문제를 $O(N)$ 시간에 풀 수 있습니다.
이제 초기 상태를 결과로 어떻게 바꿀 수 있을지 생각해야 합니다.
선은 접힌 면을 나타내므로 인접한 수끼리는 서로 선으로 연결되어야 합니다.
그런데 1번 규칙에 의해 선은 왼쪽과 오른쪽을 번갈아가며 그어져야 합니다.
그 다음 선과 이어진 숫자를 기준으로 정렬하면 완벽하게 접힌 상태로 변하고, 이때 괄호의 올바름을 판단하면 문제를 해결할 수 있습니다.
코드
fn check_interleave(list: &[u32]) -> bool {
let mut paren = Vec::with_capacity(list.len());
let mut ident = 0;
for i in (1..list.len()).step_by(2) {
let mut open = list[i - 1];
let mut close = list[i];
if open > close {
std::mem::swap(&mut open, &mut close);
}
paren.push((open, false, ident));
paren.push((close, true, ident));
ident += 1;
}
paren.sort_unstable();
let mut stack = Vec::with_capacity(paren.len() >> 1);
for &(_, is_close, ident) in &paren {
if is_close {
if stack.pop().map_or(true, |top| top != ident) {
return false;
}
} else {
stack.push(ident);
}
}
true
}
fn solve(paper: &[u32]) -> bool {
check_interleave(paper) && check_interleave(&paper[1..])
}