[프로그래머스] 1. 숫자 짝꿍 (Lv1), 2. 다리를 지나는 트럭 (Lv2), 3. 주차 요금 계산 (Lv2)

Lv. 1: 숫자 짝꿍✍️

---

문제 설명

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.) 두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

첫 번째 제출❌

우선 의식의 흐름대로 첫 코드를 작성해서 제출했지만 결과는 TC 11~15번에서 시간 초과.

당연한게 includes, indexOf 같은 메서드들은 모두 O(n) 시간복잡도를 따른다. 이를 for문 안에서 사용했으니까 아래 코드의 시간 복잡도는 O(n^2)인 셈이다.

// ------ time limit exceeded ------
function solution(x,y) {
    let answer = [];
    let x1 = x.split('')
    let y1 = y.split('')

    for(let i = 0; i < 10; i++) {
        let str = i.toString();
        if(x1.includes(str) && y1.includes(str)) {
            answer.push(str);
            x1.splice(x1.indexOf(str), 1);
            y1.splice(y1.indexOf(str), 1);
            i--;
            if(x1.length === 1 && y1.length === 1) break;
        }
    }
    if(answer.length === 0) return "-1";
    
    let zeroCheck = answer; 
    if (zeroCheck.reduce((a,c) => Number(a)+Number(c)) === 0) return '0';
    
    return answer.sort((a,b) => b - a).join('');
}

나의 답안

아래 코드로 수정하고 나서 모든 TC를 통과할 수 있었다.

function solution(x, y) {
    let answer = '';
    
    x = x.split('');
    y = y.split('');
  
    for (let i = 0; i <= 9; i++) {
        let xCount = x.filter((str) => Number(str) === i).length;
        let yCount = y.filter((str) => Number(str) === i).length;

        answer += i.toString().repeat(Math.min(xCount, yCount));
    }

    if(answer.length === 0) return '-1';

    let zeroCheck = answer
    if(zeroCheck.split('').filter(num => Number(num) !== 0).length === 0) return '0';
    else return answer.split('').map(str => Number(str)).sort((a, b) => b - a).join('');
}

접근 방식:

1. 질문하기탭에서 힌트를 얻었다. 결국 모든 숫자는 0 ~ 9 사이이기 때문에, 코드를 x와 y를 기준으로 생각하지 않고 0~9를 기준으로 작성했다.

2. 0 ~ 9 까지 반복되는 for문을 통해 x, y를 순회하면서 각 숫자가 몇 개씩 있는지 확인해준다. 예를 들어 i = 5 일때 x가 보유한 5의 개수와 y가 보유한 5의 개수를 따로 계산해준다. 이후 둘 중 더 작은 숫자만큼 answer 값에 i 값을 추가해준다.

3. 누적된 answer 값의 길이가 0일때, 즉 겹치는 숫자가 하나도 없을 때는 -1을 반환한다.

4. 누적된 answer 값에서 '0'이 아닌 것만 남겼는데 길이가 0이면, 즉 answer에 0밖에 없을 때는 0을 반환한다.

5. 그 외의 경우 내림차순으로 answer를 정렬하고 숫자로 변환한 후 반환한다.

회고:

• 시간 복잡도를 무시하고 의식의 흐름대로 코드를 작성하는 것은 guilty pleasure 다.

Lv. 2: 다리를 지나는 트럭✍️

---

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

나의 답안

function solution(bridge_length, weight, truck_weights) {
    let queue = Array(bridge_length).fill(0),
        curWeight = 0,
        time = 0;
    
    time++;
    queue.shift();
    curWeight += truck_weights[0];
    queue.push(truck_weights.shift());
    
    while (curWeight > 0) {
        time++;
        curWeight -= queue.shift();

        if (curWeight + truck_weights[0] <= weight && truck_weights.length > 0) {
            curWeight += truck_weights[0];
            queue.push(truck_weights.shift());
          } else queue.push(0);
    }
    
    return time;
  }

접근 방식:

1. 매개 변수로 주어진 bridge_length 만큼의 길이를 가진 queue 배열을 만들어주고, 우선 모든 값은 0으로 채워준다.

2. 첫 번째 트럭이 다리에 못 오르는 경우는 절대 없기 때문에 while문 시작하기 전에 배열 안에 트럭을 올려준다. 트럭 올리기 = (A) queue 배열 첫 번째 값을 빼주고, (B) 트럭을 queue 뒤에 넣는다는 뜻.

   • 동시에 트럭이 움직여서 올라갔다는 것은 시간이 1초 지났다는 뜻이기 때문에 time++ 해준다.
   • 또한 현재 트럭의 무게를 다리 위 모든 트럭의 무게인 curWeight변수에 더해준다.

3. curWeight 변수가 0 이상일 때, 즉 다리에 트럭이 한 대라도 있는 동안 반복되는 while문을 만들어준다. 그리고 해당 while문이 한번 돌 때마다 1초가 지난다고 가정하고 time++를 해준다. 마찬가지로 1초가 지났다는 것은 트럭이 한 칸씩 앞으로 움직이고 있다는 뜻이니까 queue의 가장 앞에 값을 빼주고 curWeight 변수에서 해당 값을 빼준다.

   • 이때 새로운 트럭을 다리에 올려도 무게 제한을 넘지 않고, 아직 대기 중인 트럭이 남았다면 queue에 새로운 트럭을 올려준다.
   • 새로운 트럭을 못 올린다면 배열에 0을 추가해준다.

회고:

• 총 트럭 수가 한 대라도, 트럭이 다리를 다 건너려면 최소 bridge_length 만큼의 시간이 걸린다는 점을 알아야 하는 문제다.
• 진짜 다리를 상상하면서 queue를 조작하는 재미가 쏠쏠한 문제였다.

Lv. 2: 주차 요금 계산✍️

---

문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다...(전체 읽기)

제한사항

• fees의 길이 = 4
• 1 ≤ records의 길이 ≤ 1,000
• ...(전체 읽기)

나의 답안

// calculating the time difference between a car's entry and exit 
function in_n_out(i, o) {
    let time1 = new Date(2022, 10, 27, i[0], i[1], 0);
    let time2 = new Date(2022, 10, 27, o[0], o[1], 0);
    return (time2 - time1) / 1000 / 60;
}

// sorting 'records' by car numbers
function sort_2d_arr(a, b) {
    if (a[2] === b[2]) return 0;
    else return (a[2] < b[2]) ? -1 : 1;
}

// comparing time with fees array
function finalFee(fees, num) {
    return fees[1] + (Math.ceil( (num - fees[0]) / fees[2] ) ) * fees[3];
}

function solution(fees, records) {
    let splited = [],
        perCarArr = [],
        answer = [];

    for(let i = 0; i < records.length; i++) {
        splited.push(records[i].split(/ |:/));
    }
 
    splited.sort(sort_2d_arr);

    let perCar = 0;
    while(splited.length > 0) {
        if(splited.length >= 2 && splited[0][3] === 'IN' && splited[1][3] === 'OUT') {
            let inTime = [Number(splited[0][0]), Number(splited[0][1])];
            let outTime = [Number(splited[1][0]), Number(splited[1][1])];
            perCar += in_n_out(inTime, outTime);
            
            if(splited.length === 2 || splited[1][2] !== splited[2][2]) {
                perCarArr.push(perCar);
                perCar = 0;
                splited.shift();
                splited.shift();
            } else {
                splited.shift();
                splited.shift();
            }
        } else if(splited.length === 1 || splited[0][3] === 'IN' && splited[1][3] === 'IN') {
            let inTime = [Number(splited[0][0]), Number(splited[0][1])];
            let outTime = [23, 59];
            perCar += in_n_out(inTime, outTime);
            
            perCarArr.push(perCar);
            perCar = 0;
            splited.shift();
        }   
    }
    
    for(let i = 0; i < perCarArr.length; i++) {
        if(perCarArr[i] <= fees[0]) answer.push(fees[1]);
        else answer.push (finalFee(fees, perCarArr[i]));
    }

    return answer;
}

접근 방식:

1. 고려해야 할 부분이 정말 많았던 문제였다. 그래서 solution 함수에 모든 기능을 넣지 않고 여러 함수로 따로 작성해서 사용했다.

   • in_n_out : 차의 출입부터 출차까지의 시간을 계산해주는 함수
   • sort_2d_arr : 자동차 번호를 기준으로 해서 이차원배열을 오름차순으로 정렬해주는 함수
   • finalFee : fees에 주어진 값을 기준으로 실제 비용을 계산해주는 함수

2. records로 제공되는 모든 출입/출차 절차를 이차원배열로 나눠주고 차 번호를 기준으로 정렬해준다. 이렇게 정렬만 해줘도 각 차 별로 IN, OUT 순서까지 맞게 정렬된다.

3. splited 배열의 길이가 0일 때까지 반복되는 while문을 통해 각 차의 출입/출차 시간을 비교해서 있었던 총 시간을 계산한다. 이때 같은 차가 여러번 출입/출차할 수 있기 때문에, 조건이 맞을 때만 perCarArr에 계산된 perCar 값을 넣어주고 초기화했다. (같은 차가 또 들어온 경우 시간이 누적 계산될 수 있도록)

4. 또한 차가 들어왔다가 안나간 경우, 즉 IN은 있지만 OUT이 없는 경우 23:59에 출차한 걸로 가정하라고 되어 있다. 따라서 그런 경우 outTime 값은 무조건 [23, 59]로 할당해주었다.

5. 차 별로 주차장에 머물렀던 시간이 다 계산되었다면 finalFee 함수를 통해 각 차주가 지불해야 할 주차 요금을 계산해준다. 이때 차가 기본 시간보다 적게 있었으면 기본 요금만 입력해주면 된다.

회고:

• 어렵다기 보다는 고려해야할 부분이 너무 많았던 문제였다. 문제 설명에서 제공되는 끝도 없는 양의 내용만 꼼꼼하게 읽어보고, 필요한 기능을 정리해둔 다음 기능 하나하나 모듈로 찍어내듯이 구현하니까 큰 어려움 없이 풀 수 있었다. 근데 시간이 별로 안걸렸다고는 안했다