[백준] 1663 - XYZ 문자열 (Javascript)

문제 설명 : https://www.acmicpc.net/problem/1663

 

문제 요약 :

1. XYZ 문자열이란 이전 문자열에 대해 특정한 규칙으로 변환되는 문자열이다.
2. X -> YZ
3. Y -> Z
4. Z -> X
5. 와 같은 규칙으로 변환된다.
6. N번째 문자열의 길이, k번째의 문자, X, Y, Z 각각의 개수를 구하라

 

문제 풀이 시간 : 1시간

문제 성공 여부 : 성공

 

 

접근 방법(성공) :

1. dp로 접근

 

제일 처음에 생각한 방식은 무작정 이전 문자열에 대해 변환을 해주는 것이다.

N이 최대 100이기에 크게 늘어나지 않을 것 같았고, 대략적인 계산을 해보았다.

 

XYZ 문자열은 Y와 Z일 경우 각각 Z, X 로 변환되어 문자의 수가 유지된다.

하지만, X는 YZ로 변환되기에 2개로 늘어난다.

 

X가 YZ로 변환되어도 결국 Y->Z, Z->X로 다음 변환 때는 필연적으로 문자가 늘어나는 구조이다.

따라서 1보다 조금 더 큰 수(2보다 작은)의 n제곱만큼의 문자열이 늘어나게 된다고 판단했다.

 

1.2의 100승만 해도 1억 가까이 되기에 해당 방법은 불가능하다고 판단하였다.

 

 

 

 

문제에 접근하기 앞서 먼저 N=10까지의 XYZ 문자열을 0,1,2로 각각 매핑하여 나열해 보았다.

0 -> 12
1 -> 2
2 -> 0

0
12 
20
012
1220  
20012 
0121220
122020012  
200120121220 
0121220122020012

 

무언가 규칙이 보이기 시작했다.

 

5번째 문자열인 1220(YZZX)은

2번째 문자열인 12(YZ) + 3번째 문자열인 20(ZX)으로 구성되어 있다.

 

6번째 문자열인 20012(ZXXYZ)는

3번째 문자열인 20(ZX) + 4번째 문자열인 012(xyz)로 구성되어 있다.

 

그렇다.

XYZ 문자열은 dp(i-3)와 dp(i-2)를 결합한 문자열이다!

 

해당 규칙을 파악하였다면 문제를 해결할 수 있다.

 

1번 - N 단계의 XYZ 문자열의 길이를 구한다.

이는 앞서 구한 dp [i-3] + dp [i-2]를 통해 구할 수 있다.

 

 

 

 

2번 - N 단계의 XYZ 문자열에서 k번째 문자가 무엇인지 구한다.

해당 부분에서 살짝 고민을 하였는데, 내가 선택한 방식은 다음과 같다.

 

n번째 문자열이 있고 k가 7이라고 가정한다.

0102012010021010 <- n번째 문자열

n번째 문자열은 n-3 문자열과 n-2 문자열의 합이므로, k가 n-3에 속하는지, n-2에 속하는지 알 수 있다.

 

만약 010201  +  2010021010 이와 같은 문자열의 합이라면,

n-2에서 k-dp [n-3] 인덱스의 문자로 좁힐 수 있게 된다.

 

이 과정을 반복하게 되면 인덱스는 점점 줄어들어 0,1,2로 줄어들게 된다.

[X, YZ, ZX] 

그럼 미리 저장해 둔 인덱스의 k번째 문자를 매핑하면 k번째 문자를 찾을 수 있게 된다!

 

 

 

3번 - N 단계의 XYZ 문자열에서 특정한 문자가 몇 번 나타나는지 구한다.

1번을 이해했다면 3번은 매우 쉽다.

 

dp [n]은 dp [n-3] + dp [n-2]를 붙인 문자열이므로,

dp [n-3]의 x, y, z 개수와 dp [n-2]의 x, y, z의 개수를 계속 더해서 저장하면 된다!

 

 

 

 

전체 코드(성공) :

const solution = () => {
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
  const input = fs.readFileSync(filePath).toString().split("\n");

  const question = Number(input[0]);
  const N = Number(input[1]);

  const arr = [1, 2, 2];
  for (let i = 3; i < N; i++) {
    let num = arr[i - 3] + arr[i - 2];
    arr[i] = num;
  }

  // 문제 1 
  if (question === 1) return arr[N - 1];

  // 문제 2
  if (question === 2) {
    const s = [["X"], ["Y", "Z"], ["Z", "X"]];
    let k = Number(input[2]) - 1;
    let sIdx = N - 1;
    while (2 < sIdx) {
      const leftCnt = arr[sIdx - 3];

      if (leftCnt <= k) {
        sIdx -= 2;
        k -= leftCnt;
      } else {
        sIdx -= 3;
      }
    }

    return s[sIdx][k];
  }

  // 문제 3
  let c = input[2];
  let cIdx = c === "X" ? 0 : c === "Y" ? 1 : 2;

  const dp = [
    [1, 0, 0],
    [0, 1, 1],
    [1, 0, 1],
  ];
  for (let i = 3; i < N; i++) {
    const X = dp[i - 3][0] + dp[i - 2][0];
    const Y = dp[i - 3][1] + dp[i - 2][1];
    const Z = dp[i - 3][2] + dp[i - 2][2];
    dp[i] = [X, Y, Z];
  }

  return dp[N - 1][cIdx];
};

const answer = solution();
console.log(answer);

 

 

골드 1 문제 치고는 생각보다 쉬운 문제였던 것 같다