About Computer

문제 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

• 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
• 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

입출력

입출력 #1

1.  코딩력 5를 늘립니다. 알고력 10, 코딩력 15가 되며 시간이 5만큼 소요됩니다.
2.  1번 문제를 5번 풉니다. 알고력 20, 코딩력 20이 되며 시간이 10만큼 소요됩니다. 15의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.

입출력 #2

1.  1번 문제를 2번 풉니다. 알고력 4, 코딩력 2가 되며 시간이 4만큼 소요됩니다.
2.  코딩력 3을 늘립니다. 알고력 4, 코딩력 5가 되며 시간이 3만큼 소요됩니다.
3.  2번 문제를 2번 풉니다. 알고력 10, 코딩력 7이 되며 시간이 4만큼 소요됩니다.
4.  4번 문제를 1번 풉니다. 알고력 10, 코딩력 11이 되며 시간이 2만큼 소요됩니다. 13의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.

제한 사항

• 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
  • 0 ≤ alp,cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
• alp_req는 문제를 푸는데 필요한 알고력입니다.
  • 0 ≤ alp_req ≤ 150
• cop_req는 문제를 푸는데 필요한 코딩력입니다.
  • 0 ≤ cop_req ≤ 150
• alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
  • 0 ≤ alp_rwd ≤ 30
• cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
  • 0 ≤ cop_rwd ≤ 30
• cost는 문제를 푸는데 드는 시간입니다.
  • 1 ≤ cost ≤ 100

정확성 테스트 케이스 제한사항

• 0 ≤ alp,cop ≤ 20
• 1 ≤ problems의 길이 ≤ 6
  • 0 ≤ alp_req,cop_req ≤ 20
  • 0 ≤ alp_rwd,cop_rwd ≤ 5
  • 1 ≤ cost ≤ 10

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

코드

function solution(alp, cop, problems) {
    var [max_alp, max_cop] = [0, 0];
    
    problems.forEach(v=> {
        var [a_req, c_req, a_rwd, c_rwd, cost] = v;
        if(max_alp < a_req) max_alp = a_req;
        if(max_cop < c_req) max_cop = c_req;
    });
    
    alp = Math.min(alp, max_alp);
    cop = Math.min(cop, max_cop);
    var dp = Array.from({length:max_alp+1}, ()=> Array(max_cop+1).fill(Infinity));
    dp[alp][cop] = 0;
    
    for(var i=alp; i<=max_alp; i++) {
        for(var j=cop; j<=max_cop; j++) {
            if(i+1<=max_alp)
                dp[i+1][j] = Math.min(dp[i][j]+1, dp[i+1][j]);
            if(j+1<=max_cop)
                dp[i][j+1] = Math.min(dp[i][j]+1, dp[i][j+1]);
            
            for(var k=0; k<problems.length; k++) {
                var [a_req, c_req, a_rwd, c_rwd, cost] = problems[k];
                if(a_req<=i && c_req<=j) {
                    var next_a = Math.min(i+a_rwd, max_alp);
                    var next_c = Math.min(j+c_rwd, max_cop);
                    dp[next_a][next_c] = Math.min(dp[i][j]+cost, dp[next_a][next_c]);
                }
            }
        }
    }
    return dp[max_alp][max_cop];
}

문제 

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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

문제 예시와 같습니다.

입출력 #2

두 큐에 담긴 모든 원소의 합은 20입니다. 따라서, 각 큐의 합을 10으로 만들어야 합니다.
queue2에서 1, 10을 순서대로 추출하여 queue1에 추가하고, queue1에서 1, 2, 1, 2와 1(queue2으로부터 받은 원소)을 순서대로 추출하여 queue2에 추가합니다.
그 결과 queue1은 [10], queue2는 [1, 2, 1, 2, 1, 2, 1]가 되며, 각 큐의 원소 합은 10으로 같습니다.
이때 작업 횟수는 7회이며, 이보다 적은 횟수로 목표를 달성하는 방법은 없습니다. 따라서 7를 return 합니다.

입출력 #3

어떤 방법을 쓰더라도 각 큐의 원소 합을 같게 만들 수 없습니다. 따라서 -1을 return 합니다.

제한 사항

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

설명

이 문제는 문제에 나와있는 내용 그대로 queue1과 queue2를 각각 shift(), push()를 하면서 코드를 작성했는데, 결과적으로 시간초과가 났다. 이를 해결하기 위해 shift()와 push() 메소드를 사용하지 않고, queue1과 queue2를 합친 queue에다가 포인터처럼 시작과 끝의 인덱스 위치를 저장했다.

처음 작성한 코드 (시간초과)

function solution(queue1, queue2) {
    var answer = -1;
    var sum1 = queue1.reduce((pre, cur) => pre+cur,0);
    var sum2 = queue2.reduce((pre, cur) => pre+cur,0);
    const toMake = (sum1+sum2)/2;
    const totalLength = queue1.legnth + queue2.length;
    
    if(!Number.isInteger(toMake)) return answer; 
    if(![...queue1, ...queue2].every(v => v<=toMake)) return answer;
    if(toMake === sum1) return 0;
    
    var queue = new Array(3), sum = new Array(3);
    queue[1] = queue1;
    queue[2] = queue2;
    sum[1] = sum1;
    sum[2] = sum2;
    
    var takeOut = (which) => {
        var out = queue[which].shift();
        sum[which] -= out;
        return out;
    }

    var putTogether = (to, from) => {
        queue[to].push(from);
        sum[to] += from;
    }
    
    var count = 0, out = 0;
    while(sum[1] !== sum[2]) {
        if(count>totalLength) return answer = -1;
        var [big,small] = sum[1]>sum[2] ? [1,2] : [2,1];
        putTogether(small, takeOut(big));
        count++;
    }
    
    return count;
}

수정한 코드

function solution(queue1, queue2) {
    var answer = 0;
    var sum1 = queue1.reduce((pre, cur) => pre+cur,0);
    var sum2 = queue2.reduce((pre, cur) => pre+cur,0);
    const toMake = (sum1+sum2)/2;
    const queue = [...queue1, ...queue2];
    const maxCount = queue1.length * 3;
    var start = 0, end = queue1.length;
    
    if(!Number.isInteger(toMake)) return -1; 
    if(!queue.every(v => v<=toMake)) return -1;
    if(toMake === sum1) return answer;

    while(sum1!==toMake) {
        if(answer > maxCount) return -1;
        if(sum1>toMake) {
            sum1 -= queue[start];
            start++;
        } else if(sum1<toMake) {
            if(end>=queue.length) end = 0;
            sum1 += queue[end];
            end++;
        }
        answer++;
    }
    
    return answer;
}

프로그래머스에서 2022 KAKAO BLIND RECRUITMENT Lv3.양과 늑대 를 풀면서 겪은 문제에 대해 정리하고자 한다.

https://school.programmers.co.kr/learn/courses/30/lessons/92343

해당 문제를 풀면서 초반에 아래와 같은 코드를 작성했었다.

function solution(info, edges) {
    var answer = 0;
    var link = Array(info.length).fill([]);
    
    edges.forEach(v => {
        var [parent, child] = v;
        link[parent].push(child);
    });
    
    console.log(link);
    
    return answer;
}

입력값의 예시는 다음과 같다. 

내가 기대했던 link의 출력값은 link에서 parent에 해당하는 인덱스 위치의 배열에 child값이 push된 것이었다. 

[
[ 1, 8 ],
[ 2, 4 ],
[],
[],
[ 3, 6 ],
[],
[ 5 ],
[],
[ 7, 9 ],
[ 10, 11 ],
[],
[]
]

하지만 위의 코드는 다음과 같은 출력이 나왔다.

[
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ],
[ 1, 2, 4, 8, 7, 10, 11, 3, 5, 6, 9 ]
]

이상한 결과에 당황해서 link[parent].push(child);가 아닌 link[parent]=child;로 할당을 해보았다. 

그랬더니 전체 배열에 할당되는 것이 아니라 하나하나 잘 들어가는 것이다. 

[ 8, 4, [], [], 6, [], 5, [], 9, 11, [], []]

어떠한 이유에서 push를 하면 전체 배열에 작동하는 것인가 싶어서 구글링을 해봤지만 아쉽게도 정확하게 알아내지는 못했다.

하지만 개인적인 생각으로는 Array.fill()로 빈 배열을 할당하게 되면 동일한 주소값을 가지고 있는 배열이 할당되어, push를 하게 되면 전체적으로 적용되는 것이 아닌가 싶다. 

정확한 원인을 파악하고 싶은데 알 수 없어 답답한 심정일 뿐이다.. 

혹시 이에 대한 원인을 아시는 분은 댓글 주시면 무한한 감사드리겠습니다. 

결론적으로 Array.fill의 문제를 해결하기 위해 Array.from를 사용하여 코드를 작성하였고, 원하던 출력 결과를 얻을 수 있었다.

function solution(info, edges) {
    var answer = 0;
    var link = Array.from({length:info.length}, ()=>[]);
    
    edges.map(v => {
        var [parent, child] = v;
        link[parent].push(child);
    });
    
    return answer;
}