221103 :: [프로그래머스] 콜라 문제, 옹알이(2), 두 큐 합 같게 만들기

콜라 문제

• 문제 설명

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.

정답은 아무에게도 말하지 마세요.

콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?

단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.

문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

 

• 제한사항
  • 1 ≤ b < a ≤ n ≤ 1,000,000
  • 정답은 항상 int 범위를 넘지 않게 주어집니다.

 

• 나의 답안

function solution(a, b, n) {
    let result = 0;
    while (true) {
        if (n >= a) {
            const count = n % a;
            n = Math.floor(n / a) * b;
            result += n;
            n += count;
        } else break;
    }
    return result;
}

• 빈 병인데 못 바꾸고 남은 병을 count에 선언, n과 result에 바꾼 병의 갯수를 담고 다시 n에는 count를 더하는 과정을 반복한다. 남아 있는 병이 a보다 작은 경우 while문을 빠져 나온다.

 

옹알이(2)

• 문제 설명

머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

 

• 제한사항
  • 1 ≤ babbling의 길이 ≤ 100
  • 1 ≤ babbling[i]의 길이 ≤ 30
  • 문자열은 알파벳 소문자로만 이루어져 있습니다.

 

• 나의 답안

function solution(babbling) {
    const words = ["aya", "ye", "woo", "ma"];
    let count = 0;

    for (let i = 0; i < babbling.length; i++) {
        for (let j = 0; j < words.length; j++) {
            babbling[i] = babbling[i].replaceAll(words[j], `${j}`);
            babbling[i] = babbling[i].replaceAll(`${j}${j}`, "z");
        }
    }
    for (let i = 0; i < babbling.length; i++) {
        if (isNaN(babbling[i]) == false) {
            count++;
        }
    }
    return count;
}

• 발음할 수 있는 단어인지 판별해서 j값으로 변환("ayawoo"의 경우 "02"로 변환)하고 같은 숫자가 연속하는 경우 다시 문자열인 z로 변환
• isNaN() 메서드를 통해 변환한 배열을 돌면서 값이 숫자로 판단되면(false 반환) count++

 

두 큐 합 같게 만들기

• 문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

• 제한사항
  • 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
  • 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
  • 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

• 나의 답안 (시간 초과)

function solution(queue1, queue2) {
    const arr = [...queue1, ...queue2];
    const loop = arr.length * 4;
    const findSum = (arr) => arr.reduce((pre, cur) => pre + cur);
    let getSum = findSum(arr);
    const middleNum = findSum / 2;

    if (getSum % 2 !== 0) {
        return -1;
    }

    while (arr.length) {
        let calcQueue = findSum(queue1);
        let count = 0;
        let left = 0;
        let right = queue1.length;

        while (count < loop) {
            if (calcQueue === middleNum) {
                return count;
            } else if (calcQueue > middleNum) {
                calcQueue -= arr[left];
                left++;
            } else if (calcQueue < middleNum) {
                calcQueue += arr[right];
                right++;
            }
            count++;
        }
    }
    return -1;
}

 

• 수정한 답안

function findSum(queue) {
    return queue.reduce((acc, cur) => acc + cur, 0);
}

function solution(queue1, queue2) {
    const mergedQueue = [...queue1, ...queue2];
    let left = 0;
    let right = queue1.length;
    let maxCount = 4 * mergedQueue.length;
    const tarfindSum = findSum(mergedQueue) / 2;

    let currentSum = findSum(mergedQueue.slice(left, right));
    let count = 0;

    while (count <= maxCount && !isNaN(currentSum)) {
        if (currentSum < tarfindSum) {
            currentSum += mergedQueue[right];
            right += 1;
        } else if (tarfindSum < currentSum) {
            currentSum -= mergedQueue[left];
            left += 1;
        } else {
            return count;
        }

        count++;
    }

    return -1;
}

• 한 포인터가 최대 움직일 수 있는 거리는 2n, 포인터가 두 개이므로 최대 이동 거리는 4n, 두 큐가 동일한 겂으로 나누어져야 하므로 전체 합계의 절반을 목표로 둔다.