기차 재정렬 1

문제 설명

어느 기차역에는 두 개의 선로와 두 선로를 잇고 기차가 임시 대기할 수 있는 측선이 있습니다. 측선에는 한 번에 한 대의 기차만 진입 또는 이탈할 수 있고 측선에서 빠질 때는 반드시 마지막으로 들어간 기차부터 빠질 수 있습니다.

두 선로 중 한 선로에는 1번부터 n번까지 번호가 붙은 총 n 대의 화물 기차들이 차례로 있을 때, 1번 기차부터 측선을 지나 다른 선로로 이동할 때 특정 목표 순서에 따라 기차를 재정렬할 수 있는지 판단하려고 합니다.

총 기차 대수 n과 목표 순서 target이 주어졌을 때, 기차를 target 순서대로 재정렬할 수 있으면 true, 불가능하면 false를 반환하는 solution 함수를 작성하시오.

예를 들어 n이 5이고, target은 [3,2,4,5,1]이라고 하면 아래와 같은 방법으로 기차를 재정렬할 수 있습니다.

제한 사항

• n은 1 이상 100,000 이하의 자연수입니다.
• target은 1부터 n까지의 모든 자연수가 단 한 번씩 등장하는 순열입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 아래와 같은 방법으로 1번부터 5번까지의 기차 재정렬이 가능합니다.

  시작 선로	측선	도착 선로
  [1,2,3,4,5]	[]	[]
  [2,3,4,5]	[1]	[]
  [3,4,5]	[1,2]	[]
  [4,5]	[1,2,3]	[]
  [4,5]	[1,2]	[3]
  [4,5]	[1]	[3,2]
  [5]	[1,4]	[3,2]
  [5]	[1]	[3,2,4]
  []	[1,5]	[3,2,4]
  []	[1]	[3,2,4,5]
  []	[]	[3,2,4,5,1]

• 따라서 true를 반환합니다.

2번 테스트케이스 설명

• 어떠한 방법으로도 [2,1,5,3,4] 순서로 기차를 재정렬할 수 없습니다.
• 따라서 false를 반환합니다.

3번 테스트케이스 설명

• 아래와 같은 방법으로 기차 재정렬이 가능합니다.

  시작 선로	측선	도착 선로
  [1,2,3]	[]	[]
  [2,3]	[1]	[]
  [2,3]	[]	[1]
  [3]	[2]	[1]
  [3]	[]	[1,2]
  []	[3]	[1,2]
  []	[]	[1,2,3]

• 따라서 true를 반환합니다.