Programming Challenges #31

 

여틀왕은 그의 거북이 왕관을 재배치해서 가장 계급이 높은 귀족과 가장 가까운 측근들을 더 위쪽으로 올리고 싶어한다. 쌓여있는 거북이들이 순서를 바꾸는 방법은 거북이 한말리가 원래 자기 위치에서 빠져 나와서 맨 위로 올라가서 자리를 잡는 방법밖에 없다. 거북이 스택의 원래 순서와 새로 만들어져야 할 스택의 순서가 주어졌을때 최소한의 이동 횟수만으로 원래 스택을 새로운 스택으로 재배치할 수 있는 순서를 찾아야 한다.

입력

입력의 첫번째 줄에는 테스트 케이스의 개수를 나타내는 K라는 정수 하나만 들어있다. 각 테스트 케이스는 스택에 들어있는 거북이의 개수를 나타내는 n이라는 정수로 시작되며 그 밑으로 n개의 줄에 걸쳐서 거북이 스택의 원래 배치가 기술된다. 각 줄에는 거북이의 이름이 들어있으며, 맨 윗줄에는 스택 맨 위에 있는 거북이의 이름이 있고 위에서 아래로 순서대로 거북이의 이름이 나열된다. 각 거북이한테는 그 거북이만의 이름이 주어지며 각 이름은 80글자를 넘지 않는 문자열이고, 알파벳, 숫자, 스페이스 문자, 점('.')만 쓰인다. 그 밑으로는 n개의 줄에 걸쳐서 새로운 스택이 기술되며 여기에서도 위에 있는 거북이부터 아래 있는 거북이 순으로 이름이 열거된다. 각 테스트 케이스는 정확하게 2n+1개의 줄로 구성된다. 거북이의 수(n)는 200 이하로 제한된다. 

 

결과

function findMinimumMoves(testCases) {
  let results = [];

  for (let i = 0; i < testCases.length; i++) {
    let testCase = testCases[i];
    let n = parseInt(testCase[0]);
    let originalStack = testCase.slice(1, n + 1);
    let newStack = testCase.slice(n + 1);

    let moves = 0;
    let currentPosition = 0;

    for (let j = 0; j < originalStack.length; j++) {
      let turtle = originalStack[j];

      // Find the position of the turtle in the new stack
      let newPosition = newStack.indexOf(turtle);

      // Calculate the number of moves needed to bring the turtle to the top
      moves += Math.abs(newPosition - currentPosition);

      // Update the current position
      currentPosition++;

      // Remove the turtle from the new stack
      newStack.splice(newPosition, 1);
    }

    results.push(newStack);
  }

  return results;
}

let testCases = [
  [3, 'Yertle', 'Duke of Earl', 'Sir Lancelot', 'Duke of Earl', 'Yertle', 'Sir Lancelot'],
  [9, 'Yertle', 'Duke of Earl', 'Sir Lancelot', 'Elizabeth Windsor', 'Michael Eisner', 'Richard M. Nixon', 'Mr. Rogers', 'Ford Perfect', 'Mack', 'Yertle', 'Richard M. Nixon', 'Sir Lancelot', 'Duke of Earl', 'Elizabeth Windsor', 'Michael Eisner', 'Mr. Rogers', 'Ford Perfect', 'Mack']
];

let results = findMinimumMoves(testCases);

for (let i = 0; i < results.length; i++) {

예시:

2 3 Yertle Duke of Earl Sir Lancelot Duke of Earl Yertle Sir Lancelot 9 Yertle Duke of Earl Sir Lancelot Elizabeth Windsor Michael Eisner Richard M. Nixon Mr. Rogers Ford Perfect Mack Yertle Richard M. Nixon Sir Lancelot Duke of Earl Elizabeth Windsor Michael Eisner Mr. Rogers Ford Perfect Mack

 

설명

해당 문제는 스택을 재배치하여 원래 스택을 새로운 스택으로 바꾸는 과정에서 최소한의 이동 횟수를 구하는 문제입니다. 먼저, 입력값에 대한 설명입니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 K가 주어지며, 각 테스트 케이스는 2n+1개의 줄로 구성됩니다. 첫 번째 줄은 스택에 들어있는 거북이의 개수를 나타내는 정수 n이며, 다음 n개의 줄에는 원래 스택의 거북이 배치가 기술되고, 다음 n개의 줄에는 새로운 스택의 거북이 배치가 기술됩니다. 이제 알고리즘을 설명하겠습니다. 주어진 테스트 케이스의 개수에 대해 반복하면서 각 테스트 케이스마다 최소 이동 횟수로 스택을 재배치하는 과정을 수행합니다. 먼저, 원래 스택과 새로운 스택을 비교하여 원래 스택의 거북이를 순서대로 탐색합니다. 각 거북이에 대해서 다음을 수행합니다. 새로운 스택에서 해당 거북이의 위치를 찾습니다. 현재 위치와 새로운 위치의 차이를 이동 횟수에 더합니다. 현재 위치를 업데이트합니다. 새로운 스택에서 해당 거북이를 제거합니다. 모든 거북이에 대한 탐색을 마치면 최종적으로 재배치된 스택이 나오게 됩니다. 이를 결과 리스트에 저장하고, 모든 테스트 케이스에 대해 반복합니다. 마지막으로, 결과 리스트에 저장된 재배치된 스택을 순서대로 출력합니다. 위의 알고리즘을 코드로 구현하였습니다. 주어진 테스트 케이스에 대해 실행하면, 첫 번째 테스트 케이스에서는 "Duke of Earl", "Sir Lancelot"이 최소 이동 횟수로 재배치된 스택이 되고, 두 번째 테스트 케이스에서는 "Richard M. Nixon", "Yertle"이 최소 이동 횟수로 재배치된 스택이 됩니다. 출력된 결과는 최소 이동 횟수로 재배치된 스택의 거북이들의 순서를 나타냅니다.