백준 2806 - DNA 발견 (JavaScript, 다른 풀이)

• 2806번: DNA 발견

생각의 흐름

• 매 상태에서 2가지 돌연변이가 가능하다. (변이 X, Y는 임의로 붙인 이름이다.)
  • 변이 X: 임의의 1글자의 AB 전환
  • 변이 Y: 앞 K글자의 AB 전환
• 앞에서부터 K글자의 AB를 전환하는 연산이 있으니, 뒤부터 A로 바꿔 나가면 되지 않을까?
• 맨 뒤를 보자.
  • 맨 뒤의 연속하는 A(/A+$/): 이미 완성된 부분이다. 바로 앞을 보자.
  • B가 연속 1개: 그것만 뒤집는 변이 X가 일어나는 쪽이 빠르다.
  • B가 연속 3개 이상: 변이 Y가 2번 일어나는 쪽이 빠르다. (예: AAABBBAAA)
    1. 마지막으로 연속되는 B가 끝나는 지점까지 변이 Y가 일어난다. ([AAABBB]AAA → [BBBAAA]AAA)
    2. 마지막으로 연속되는 B의 앞이었던 곳까지 변이 Y가 일어난다. ([BBB]AAAAAA → [AAA]AAAAAA)
  • B가 연속 2개: 변이 X, 변이 Y 어느 쪽이 2번 일어나든 똑같아 보일 수 있는데, 예제 2를 보면 다르다는 걸 알 수 있다. 변이 Y로 한번에 뒤집어 놓고 나머지는 다음 상태에서 결정하는 쪽이 낫다. (BBABB → AABAA → AAAAA)

---

구현

입력 받기

• 입력의 첫째 줄은 input.length와 동일하므로 버렸다.
• 둘째 줄의 문자열을 배열로 쪼갰는데, 그럴 필요까지는 없었다.

const input = require("fs")
  .readFileSync(0, "utf-8")
  .trim()
  .split("\n")[1]
  .split(""); // 안 해도 됨

상태

• 변이가 발생할 때마다 문자열(input)을 일일이 고치는 건 연산 낭비다.
• 변이 횟수(transCount) 및 2가지 상태를 두었다.
  • 어디부터 확인할 차례인지(right): 오른쪽부터 확인할 것이므로, 오른쪽 끝 인덱스로 초기화하고 진행에 따라 왼쪽으로 옮겨 갔다.
  • 현재 확인 중인 부분이 입력과 동일한지 아니면 AB가 전환된 상태인지(DNA): 객체 2개(의 참조)를 사용했다. 이 객체는 AB가 전환된 상태를 헷갈리지 않게 하기 위해, AB 전환 상태에 따른 분기 처리를 줄이기 위해서도 사용했다.
    • (변이 횟수) % 2로는 판별할 수 없다. 변이 X 때문에 일치하지 않을 수 있다.

const AB = { A: "A", B: "B" };
const BA = { A: "B", B: "A" };
let DNA = AB;

let right = input.length - 1;
let transCount = 0;

while (right >= 0) {
  // ...
}

console.log(transCount);

• 나중에 변이 Y가 발생할 때 DNA를 현재와 다른 객체로(예: AB였다면 BA로) 전환한다.
• AB는 문자열의 A, B가 각각 A, B임을 나타내고, BA는 문자열의 A, B가 각각 B, A임을 나타낸다.
  • 메모리상의 문자를 직접 변경하지 않고 DNA.A, DNA.B로 논리적으로 바꾸어 판단할 수 있다.

연산 및 상태 전이

마지막 B 덩어리가 끝나는 위치 찾기

• 가장 먼저, 현재 위치의(right) 문자가 A이면 right를 1 감소시키고 다음 반복으로 넘긴다. right가 (처리하지 않은) 마지막 B의 위치를 가리키게 될 때 본격적인 논리를 진행한다.

while (right >= 0) {
  if (input[right] === DNA.A) {
    right -= 1;
    continue;
  }

  // ...
}

마지막 B 덩어리의 길이 세기

• 처리하지 않은 마지막 B의 위치를 찾았다면, 그것으로 끝나는 B 덩어리의 길이(bCount)를 센다.
• right가 가리키는 B 덩어리가 시작하는 지점 left를 찾아서 right - left + 1을 구한다.

while (right >= 0) {
  // ...

  let left = right - 1;
  while (left >= 0 && input[left] === DNA.B) {
    left -= 1;
  }
  left += 1;

  const bCount = right - left + 1;

  // ...
}

B 덩어리의 길이에 따른 변이 처리

• B가 1개이면 (변이 X)
  1. 그것만 A로 바꾼다. (right의 오른쪽은 더 이상 조회하지 않으므로 이 동작은 실제로 하지 않아도 된다.)
  2. right를 1 뺀다(1칸 왼쪽으로 옮긴다).
• 아니라면 (변이 Y)
  1. DNA 상태를 뒤집는다. AB이면 BA로, 아니라면 AB로 교체한다.
  2. right를 left - 1로 바꾼다(left의 한 칸 왼쪽으로 옮긴다).
• B의 길이에 관계없이 변이가 1번 발생하므로 transCount는 무조건 1 증가한다.

while (right >= 0) {
  // ...

  if (bCount === 1) {
    input[right] = DNA.A; // 안 해도 됨
    right -= 1;
  } else {
    DNA = DNA === AB ? BA : AB;
    right = left - 1;
  }
  transCount += 1;
}

사실, 두 조건에서의 2번 항목 모두 if ... else 블록 뒤로 뺄 수 있다. 이렇게 하면 bCount === 1 블록도 지울 수 있다.

while (right >= 0) {
  // ...

  if (bCount > 1) {
    DNA = DNA === AB ? BA : AB;
  }
  right = left - 1;
  transCount += 1;
}

---

다른 풀이와의 비교

다른 사람의 풀이도 찾아보았다. 모두 2행 N열짜리 배열을 두고 점화식을 따라 앞 열부터 답을 채우고 0행 마지막 열의 값을 출력했다. 0행에는 i번째 글자까지 전부 A로 바꿀 때의 변이 횟수를, 1행에는 전부 B로 바꿀 때의 변이 횟수를 앞에서부터 채워 나가는 방식이다.

임의의 풀이를 골라 JavaScript로 재작성하고, 임의의 입력을 생성하여 내 풀이와 비교해 보았다. 출력 결과에는 차이가 없었고, 내 풀이의 실행 시간이 다른 풀이의 70% 정도로 더 빨랐다.