JavaScript로 해결하는 2키 키보드 최소 연산 문제

다음과 같은 상황을 가정해 보겠습니다.

처음에 메모장에는 문자 'A' 하나만 존재합니다. 우리는 매 단계마다 이 메모장에 두 가지 작업 중 하나를 수행할 수 있습니다.

• 모두 복사(Copy All) − 메모장에 현재 있는 모든 문자를 복사합니다. 부분 복사는 허용되지 않습니다.

• 붙여넣기(Paste) − 마지막으로 복사한 문자들을 화면에 붙여넣습니다.

문제 정의

숫자 num을 유일한 인수로 받아, 'A'를 정확히 num번 화면에 출력하기 위해 필요한 최소 작업 횟수(모두 복사 또는 붙여넣기)를 계산해 반환하는 JavaScript 함수를 작성해야 합니다.

예를 들어, 입력이 다음과 같다면,

const num = 3;

출력은 다음과 같아야 합니다.

const output = 3;

그 이유는 다음과 같은 순서로 작업하면 세 번 만에 완성할 수 있기 때문입니다.

• 모두 복사 (결과: 'A')

• 붙여넣기 (결과: 'AA')

• 붙여넣기 (결과: 'AAA')

풀이 접근 방식

이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 핵심 규칙은 다음과 같습니다.

• 현재까지 만든 'A'의 개수를 curr, 클립보드에 저장된 개수를 copy라고 할 때, 목표 값에서 현재 개수를 뺀 나머지(num - curr)가 curr로 나누어떨어진다면 지금 복사하는 것이 유리합니다.

• 나누어떨어지지 않는다면 기존에 복사한 내용을 계속 붙여넣어 개수를 늘려갑니다.

이렇게 하면 불필요한 복사를 피하고 항상 최적의 분해 방식(약수 기반 분해)으로 도달할 수 있습니다.

예제 코드

const num = 3;
const minimumSteps = (num = 1) => {
    let [curr, copy, steps] = [1, 0, 0];
    while(curr != num){
       if((copy < curr) && ((num - curr) % curr) == 0) {
          copy = curr;
       }else{
          curr += copy;
       };
       steps += 1;
    };
    return steps;
};
console.log(minimumSteps(num));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

3

참고로, num이 1인 경우 이미 'A'가 하나 존재하므로 어떤 작업도 필요하지 않아 결과는 0이 됩니다. 이 알고리즘은 각 단계마다 조건 판단만 수행하므로 시간 복잡도는 O(log n) 수준으로 매우 효율적입니다.