[백준] Z - JavaScript 문제 풀이

💙 문제 설명

 

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

 

N = 1

 

N > 1인 경우, 배열을 크기가 2 ^ N-1 × 2 ^ N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.

 

N = 2

 

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

💛 입력

 

첫째 줄에 정수 N, r, c가 주어진다.

 

💚 출력

 

r행 c열을 몇 번째로 방문했는지 출력한다.

 

 

🚫 제한사항

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N
• 시간제한 : 0.5 s

---

❤️ 문제 풀이 방법

 

1️⃣ while 반복문

 

각 가로와 세로의 n을 2로 나누면, 4분면이 만들어진다.

이때, 4분면 기반으로 r이 2 ^ n/2보다 크면 3, 4분면에 해당한다.

c이 2 ^ n/2보다 크면, 2, 4분면에 해당한다.

 

3, 4분면인 경우에는 1, 2분면만큼 순서를 더해주면 된다. 이를 계산하는 방법은 2 ^ n * 2 ^ (n - 1).

2, 4분면인 경우에는 r에서 이미 4분면인 경우를 고려해줬기 때문에, 1분면인 경우만 더해주면 된다. (1 / 4사분면)

이를 계산하는 방법은 2 ^ (n - 1) * 2 * (n - 1).

 

n 이 1보다 크거나 같은 경우에 이 계산을 반복해가면서, n을 1씩 빼준다.

 

let fs = require("fs");
let [n, r, c] = fs
  .readFileSync(0, "utf8")
  .trim()
  .split(" ")
  .map(Number);

function solution(n, r, c) {
  let visitedCount = 0;

  while (n >= 1) {
    // 현재 n을 기준으로 4사분면을 그려 큰 경우
    if (r >= 2 ** (n - 1)) {
      visitedCount += 2 ** (2 * n - 1);
      r %= 2 ** (n - 1);
    }
    if (c >= 2 ** (n - 1)) {
      visitedCount += 2 ** (2 * n - 2);
      c %= 2 ** (n - 1);
    }

    n--;
  }

  return visitedCount;
}

console.log(solution(n, r, c));

 

시간 복잡도는 n부터 1까지 반복하게 되므로 O(n)이다.

 

2️⃣ 비트 연산자

 

2 ^ n 문제인 것을 보자마자 비트 연산으로 풀 수 있을 것이라고 생각했다.

그런데 아직 비트연산에 익숙하지 않은 이슈로 비트연산자를 공부하면서 문제를 풀었다.

 

let fs = require("fs");

// 파일에서 입력값을 읽어와 숫자로 변환 (n: 행렬 크기 지수, r: 행 인덱스, c: 열 인덱스)
let [n, r, c] = fs.readFileSync("test.txt", "utf8").trim().split(" ").map(Number);

function solution(n, r, c) {
  let order = 0; // 방문 순서를 저장하는 변수

  // 큰 행렬(2^n × 2^n)을 작은 단위(2×2)까지 쪼개면서 탐색
  for (let i = n - 1; i >= 0; i--) {
    /**
     * (r >> i) & 1 : r의 i번째 비트를 추출
     * r >> i        : r을 i비트 오른쪽으로 이동 (즉, i번째 비트가 맨 오른쪽에 위치)
     * & 1           : 맨 오른쪽 비트만 남기고 나머지는 0으로 설정 (비트 마스킹)
     */
    let rowBit = (r >> i) & 1; // r의 i번째 비트 추출 → 현재 행의 사분면 정보

    /**
     * (c >> i) & 1 : c의 i번째 비트를 추출
     * 원리는 r과 동일하며, 현재 열이 어느 사분면인지 확인하는 역할
     */
    let colBit = (c >> i) & 1; // c의 i번째 비트 추출 → 현재 열의 사분면 정보

    /**
     * 현재 사분면의 순서 계산
     * rowBit * 2 + colBit : 4개의 사분면 중 몇 번째인지 판별
     *  - (0,0) → 1사분면 (좌상) → 0
     *  - (0,1) → 2사분면 (우상) → 1
     *  - (1,0) → 3사분면 (좌하) → 2
     *  - (1,1) → 4사분면 (우하) → 3
     * 
     * (1 << (2 * i)) : 2^2i 를 계산하여 현재 행렬 크기에 맞게 이동
     *  - i = 2 → (1 << 4) = 16
     *  - i = 1 → (1 << 2) = 4
     *  - i = 0 → (1 << 0) = 1
     * 
     * 따라서 현재 사분면의 크기만큼 이동하여 order를 업데이트함.
     */
    order += (rowBit * 2 + colBit) * (1 << (2 * i));
  }

  return order; // 최종 방문 순서 반환
}

console.log(solution(n, r, c)); // 결과 출력

 

chat gpt한테 주석을 써달라고 부탁했더니 열심히 써줬다. 

문제 풀이에서 더 개선할 부분 있으면 댓글로 남겨주시면 감사하겠습니다.