kohigowild
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가지 방법이 있습니다.
- queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
- 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, 두 큐가 동일한 겂으로 나누어져야 하므로 전체 합계의 절반을 목표로 둔다.
'Algorithm' 카테고리의 다른 글
221107 :: [프로그래머스] 삼총사, 신고 결과 받기, 부족한 금액 계산하기 (0) | 2022.11.07 |
---|---|
221104 :: [프로그래머스] 푸드 파이트 대회, 소수 찾기, JadenCase 문자열 만들기 (0) | 2022.11.04 |
221028 [프로그래머스] :: 완주하지 못한 선수, 오픈채팅방, 햄버거 (1) | 2022.10.29 |
221027 [프로그래머스] :: 약수의 개수와 덧셈, 소수 만들기, 2개 이하로 다른 비트 (0) | 2022.10.27 |
221025 [프로그래머스] :: 폰켓몬, 연속 부분 수열 합의 개수, 피로도 (0) | 2022.10.26 |