문제 태그

• 구현
• 연결 구조
• 배열로 링크드 리스트 흉내내기

한국어 문제 해석

카드 1부터 N까지와 카드 더미 1부터 N까지가 있다. 처음에는 i번 더미에 i번 카드만 하나 들어 있다.

각 연산에서는 카드 C와 그 위에 쌓인 카드들을 순서를 유지한 채 통째로 잘라서, 카드 P의 위에 올린다.

모든 연산이 끝난 뒤 각 더미에 카드가 몇 장 남아 있는지 구한다.

문제 요약

• 잘라낸 묶음 안의 상대 순서는 변하지 않는다.
• 매 연산에서 실제로 바뀌는 연결은 잘라낸 묶음의 맨 아래 카드 주변뿐이다.
• 마지막에는 각 더미의 바닥 카드에서 위로 따라가며 크기를 셀 수 있다.

예시 워크스루

처음에는 모든 카드가 자기 더미에 혼자 있다.

예를 들어 1번 카드를 포함한 묶음을 3번 카드 위에 올리면, 3번 더미는 아래에서부터 3, 1 순서가 된다.

그 뒤에 다시 1번 카드를 포함한 묶음을 다른 더미 위로 옮기면, 1번 카드 위에 있던 카드들은 그대로 따라간다.

여기서 변하는 것은 묶음 전체가 아니라 경계 연결이다.

• 잘라낸 묶음 아래에 있던 카드는 위쪽 연결이 끊긴다.
• 잘라낸 묶음의 맨 아래 카드는 새 목적지 카드 위에 놓인다.
• 묶음 내부의 순서는 그대로 유지된다.

아이디어

각 카드에 대해 바로 위 카드와 바로 아래 카드만 저장하면 충분하다.