[백준] 1021번 - 회전하는 큐

문제 링크 : https://www.acmicpc.net/problem/1021

 

 

 

| 문제 탐색하기

1) 문제 분석

(1) 입력값

• N : 큐의 크기 (50보다 작거나 같읕 자연수)
• M : 뽑아내고자 하는 수의 개수  (N보다 작거나 같은 자연수)
• arr : 뽑아내려고 하는 수의 위치 (1보다 크거나 같고, N보다 작거나 같은 자연수)

(2) 연산

• 첫 번째 원소 뽑기 
• 왼쪽으로 한칸 이동하기 (첫 번째 요소는 마지막으로)
• 오른쪽으로 한칸 이동하기 (마지막 요소는 첫 번째로)

(3) 목표

: 지민이가 뽑아내려고 하는 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

(4) 예시

 

2) 기능 명세서

(1) 값 입력받기

(2) N, M, arr로 분리하기

(3) 1부터 N까지의 배열 만들기

(4) M번 반복하기

• 현재 idx 값이 대상과 같은지 비교하기
  
  • 같지 않으면, 현재 idx에서 대상까지 왼쪽과 오른쪽으로의 이동 횟수 구하기
  • 더 작은 횟수를 총 이동거리에 더하기
• idx를 대상 다음 위치의 값으로 이동하기
• 대상을 배열에서 지우기

(5) 총 이동거리 출력하기

 

 

 

| 처음 코드 & 개선이 필요한 점

function printResult(input) {
  const N = input.N;
  const M = input.M;
  const arr = input.arr;

  let totalCount = 0;
  let idx = 1;

  let numbers = Array.from({ length: N }).map((_, i) => i + 1);

  for (let i = 0; i < M; i++) {
    const target = arr[i]; // 대상

    // 현재 idx 값이 대상과 같은지 비교하기
    if (idx !== target) {
      // 같지 않으면, 현재 idx에서 대상까지 왼쪽과 오른쪽으로의 이동 횟수 구하기
      let leftCount = 0;
      let rightCount = 0;
      let indexIdx = numbers.indexOf(idx);
      let indexTarget = numbers.indexOf(target);

      if (indexIdx < indexTarget) {
        rightCount = indexTarget - indexIdx;
        leftCount = numbers.length - rightCount;
      } else {
        leftCount = indexIdx - indexTarget;
        rightCount = numbers.length - leftCount;
      }

      // 더 작은 횟수를 총 이동거리에 더하기
      const size = leftCount > rightCount ? rightCount : leftCount;
      totalCount += size;
    }

    // idx를 다음 대상 위치로 이동하기
    const targetIndex = numbers.indexOf(target);
    idx = numbers[(targetIndex + 1) % numbers.length];

    // 대상을 배열에서 지우기
    numbers.splice(targetIndex, 1);
  }

  return totalCount;
}

function main() {
  const fs = require("fs");
  const input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((data) => data.split(" ").map(Number));

  const inputObj = {
    N: input[0][0],
    M: input[0][1],
    arr: input[1],
  };

  const output = printResult(inputObj);
  console.log(output);
}

if (require.main === module) {
  main();
}

module.exports = {
  printResult,
};

 

1) idx라는 상태를 만들지 말아야 했다.

(1) 원본 코드의 핵심 문제

: numbers 배열이 이미 현재 큐 상태를 전부 표현하고 있는데, idx로 현재 위치를 중복 관리했다. 쉽게 말하면, 큐를 실제로 돌려서 queue의 특성을 사용하여 numbers[0] 자체로 현재 삭제해야 할 값을 구할 수 있었을텐데, queue의 특성을 사용하지 않고 오직 순수 배열을 사용해서 구현하려고 했던 점이 개선점이었다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- target : 2
1) 기존 방식 : 2를 배열에서 제거하기 위해 idx의 index를 알고 있어야 했고, 해당 위치를 삭제했다.
- 결과 : [1, 3, 4, 5, 6, 7, 8, 9, 10]
2) 개선 방식 : 2를 배열에서 제거하기 위해 큐를 돌려서 삭제했다.
- [2, 3, 4, 5, 6, 7, 8, 9, 10] + [1] => [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]에서 numbers[0]을 삭제
- 결과 : [3, 4, 5, 6, 7, 8, 9, 10, 1]

 

2) indexOf 호출이 많았다.

: indexOf의 시간 복잡도는 O(N)이다. 게다가 의도치 않게 indexOf를 여러 번 호출하면서 O(N^2)의 구조를 갖게 되었다.

 

 

 

 

| 최종 코드

function printResult(input) {
  const N = input.N;
  const M = input.M;
  const arr = input.arr;

  let totalCount = 0;

  let numbers = Array.from({ length: N }).map((_, i) => i + 1);

  for (let i = 0; i < M; i++) {
    // 대상 값과 index 구하기
    const target = arr[i]; // 대상
    const indexTarget = numbers.indexOf(target);

    // 2번, 3번 연산 횟수 구하기
    const leftCount = indexTarget; // 2번 연산 횟수
    const rightCount = numbers.length - leftCount; // 3번 연산 횟수

    // 총 연산 횟수에 최소 이동 횟수로 더하기
    totalCount += Math.min(leftCount, rightCount);

    // target을 맨 앞으로 오게 회전
    const rightArr = numbers.slice(indexTarget);
    const leftArr = numbers.slice(0, indexTarget);
    numbers = rightArr.concat(leftArr);

    // 맨 앞(target) 제거
    numbers.shift();
  }

  return totalCount;
}

function main() {
  const fs = require("fs");
  const input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((data) => data.split(" ").map(Number));

  const inputObj = {
    N: input[0][0],
    M: input[0][1],
    arr: input[1],
  };

  const output = printResult(inputObj);
  console.log(output);
}

if (require.main === module) {
  main();
}

module.exports = {
  printResult,
};

최종 로 직

 

 

 

| 느낀점

이번 문제에서는 Queue의 특성과 slice와 같은 배열/문자열 자르기에 대한 메소드를 배울 수 있었다. 처음에 세웠던 로직이 비효율적이었다는 것을 알게 되었고, 이를 어떻게 하면 개선할 수 있을지에 대해서 개선시킨 경험이 기억에 남는다. 사실 문제를 풀다가 안 풀려서 다음 날이 되어서 풀게 되었는데, 생각보다 어제 막혔던 부분이 잘 풀려서 다행이었다. 잘 풀리지 않을 땐, 잠시 쉬는 것도 좋을 것 같다.

 

1) slice, splice 사용법

(1) slice : 잘라서 복사 (원본 배열이 바뀌지 않는다.)

// 형태
array.slice(start, end)
/*
 start : 시작 인덱스(포함)
 end : 끝 인덱스 (미포함)
*/

//예시
const arr = [1, 2, 3, 4, 5];

// 끝 인덱스 생략
arr.slice(2) 
// [3, 4, 5]

// 범위 자르기
arr.slice(1, 4)
// [2, 3, 4]

 

(2) splice : 잘라서 수정 (원본 배열이 바뀐다.)

// 형태
array.splice(start, deleteCount, item1, item2, ...)
/*
 start : 시작 인덱스
 deleteCount : 제거할 개수
 item... : 그 자리에 넣을 값들 (선택)
*/

 

//예시
const arr = [1, 2, 3, 4, 5];

// 1개 제거
arr.splice(2, 1);
// 제거된 값 : [3]
// arr -> [1, 2, 4, 5]

// 여러 개 제거
arr.splice(1, 2);
// 제거된 값 : [2, 3]
// arr -> [1, 4, 5]

// 제거 + 추가
arr.splice(2, 1, 99);
// 제거된 값 : [3]
// arr -> [1, 2, 99, 4, 5]