기차 재정렬 2

문제 설명

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

두 선로 중 한 선로에는 1번부터 n번까지 번호가 붙은 총 n 대의 화물 기차들이 차례로 있을 때, 1번 기차부터 측선을 지나 다른 선로로 이동할 때 특정 목표 순서에 따라 기차를 재정렬하는 방법을 찾고자 합니다. 기차를 재정렬하는 방법은 기차가 측선에 진입하는 경우 "push"를 측선에서 이탈하는 경우 "pop"을 순서대로 나열합니다.

총 기차 대수 n과 목표 순서 target이 주어졌을 때 target 순서대로 기차를 재정렬하는 방법을 반환하는 solution 함수를 작성하시오. 만약 재정렬하는 방법이 여러 개라면 아무거나 반환합니다.

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

따라서 [3,2,4,5,1] 순서대로 기차를 재정렬하는 방법은 ["push","push","push","pop","pop","push","pop","push","pop","pop"] 입니다.

제한 사항

• n은 1 이상 100,000 이하의 자연수입니다.
• target은 1부터 n까지의 모든 자연수가 단 한 번씩 등장하는 순열입니다.
• target은 기차 재정렬이 가능한 경우만 입력으로 주어집니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 아래와 같은 방법으로 5개의 기차를 재정렬할 수 있습니다.

  시작 선로	측선	도착 선로	행동
  [1,2,3,4,5]	[]	[]	-
  [2,3,4,5]	[1]	[]	"push"
  [3,4,5]	[1,2]	[]	"push"
  [4,5]	[1,2,3]	[]	"push"
  [4,5]	[1,2]	[3]	"pop"
  [4,5]	[1]	[3,2]	"pop"
  [5]	[1,4]	[3,2]	"push"
  [5]	[1]	[3,2,4]	"pop"
  []	[1,5]	[3,2,4]	"push"
  []	[1]	[3,2,4,5]	"pop"
  []	[]	[3,2,4,5,1]	"pop"

• 따라서 [3,2,4,5,1] 순서대로 기차를 재정렬하는 방법은 ["push","push","push","pop","pop","push","pop","push","pop","pop"] 입니다.

2번 테스트케이스 설명

• 아래와 같은 방법으로 3개의 기차를 재정렬할 수 있습니다.

  시작 선로	측선	도착 선로	행동
  [1,2,3]	[]	[]	-
  [2,3]	[1]	[]	"push"
  [2,3]	[]	[1]	"pop"
  [3]	[2]	[1]	"push"
  [3]	[]	[1,2]	"pop"
  []	[3]	[1,2]	"push"
  []	[]	[1,2,3]	"pop"

• 따라서 [1,2,3] 순서대로 기차를 재정렬하는 방법은 ["push","pop","push","pop","push","pop"] 입니다.

3번 테스트케이스 설명

• 아래와 같은 방법으로 4개의 기차를 재정렬할 수 있습니다.

  시작 선로	측선	도착 선로	행동
  [1,2,3,4]	[]	[]	-
  [2,3,4]	[1]	[]	"push"
  [3,4]	[1,2]	[]	"push"
  [4]	[1,2,3]	[]	"push"
  [4]	[1,2]	[3]	"pop"
  [4]	[1]	[3,2]	"pop"
  [4]	[]	[3,2,1]	"pop"

• 따라서 [3,2,1] 순서대로 기차를 재정렬하는 방법은 ["push","push","push","pop","pop","pop"] 입니다.