BaekJoon_11399(ATM)

문제

https://www.acmicpc.net/problem/11399

11399번: ATM

문제풀이

탐욕 알고리즘을 적용하여 풀면 문제를 해결 할 수 있다.

지금 당장 시간이 가장 적게 걸리는 사람의 순서를 앞으로 하여 기다리는 시간을 최소화 하면 총 걸리는 시간을 최소화 할 수 있다.

처음에 문제를 풀 때는 각각의 사람이 기다린 시간과 소요되는 시간을 배열에 넣어서 제일 마지막에 더하는 방법으로 풀었고,

두번째에는 다른 사람들이 푼 풀이를 보니 이중 for문으로 간략하게 풀었길래 좀 더 좋은 풀이인 거 같아 참고하여 풀어봤는데

메모리와 소요시간이 첫번째 풀이가 좀 더 효율적이었다.

아마 이중 for문을 사용하여 메모리와 시간이 좀 더 걸리는 거 같다.

내가 푼 풀이가 더 효율적일 수 있다니 좀 뿌듯하다 😃

 

코드

첫번째 풀이

const answer = ([n, arr]) => {
    const time = arr.split(' ').map(Number).sort((a, b) => a - b);

    const totalTime = [];
    let sumTime = 0;
    for (let index = 0; index < time.length; index++) {
        sumTime += time[index];
        totalTime.push(sumTime);
    }

    console.log(totalTime.reduce((a,b) => a+b,0));
}

const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        answer(input);
        process.exit();
    });

 

두번째 풀이

const answer = ([n, arr]) => {
    const time = arr.split(' ').map(Number).sort((a, b) => a - b);

     let sumTime = 0;
     for (let index = 0; index < time.length; index++) {
         for (let index2 = 0; index2 < index + 1; index2++) {
             sumTime += time[index2]
         }        
     }

     console.log(sumTime);
}

const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        answer(input);
        process.exit();
    });

 

제출 화면

 

코드는 깃헙에서도 확인 할 수 있습니다. 🤗

https://github.com/duduchi/Algorithm/tree/main/Greedy

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.