코딩테스트 9(sort, break, slice)

문제 1. 예산
 

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다. 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다. 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.


입출력 예
각 부서에서 [1원, 3원, 2원, 5원, 4원]만큼의 금액을 신청했습니다. 만약에, 1원, 2원, 4원을 신청한 부서의 물품을 구매해주면 예산 9원에서 7원이 소비되어 2원이 남습니다. 항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다. 위 방법 외에 3개 부서를 지원해 줄 방법들은 다음과 같습니다.

 
풀이.

function solution(d, budget) {
    let sortedD = d.sort((a, b) => a - b)
    let total = 0;
    let count = 0;
    for (i = 0 ; i <= sortedD.length ; i += 1) {
        total += sortedD[i]
        if(sortedD[i] <= budget - (total - sortedD[i])) {
            count++
        } else {
            return count
        } 
    }
}

 
=> sort 함수로 배열을 오름차순으로 정렬 한 뒤, 배열을 하나씩 더해줄 total 그리고 횟수를 더해줄 count를 선언 해준 뒤, 반복문으로 남은 예산이 신청한 금액보다 작을 경우에 count를 반환하도록 하였다. 순서때문에 if 조건문에서 예산에 total만 빼주면 가장 최근의 요소를 더한 값이 들어오게 된다. 그래서 현재 해당하는 요소를 total에서 빼주었다.

 

해답.

function solution(d, budget) {
    d.sort((a, b) => a - b);
    let sum = 0;
    let count = 0;

    for (let i = 0; i < d.length; i++) {
        sum += d[i];
        if (sum > budget) break;
        count++;
    }

    return count;
}

 

=> 먼저 배열 d를 오름차순으로 정렬한다. (sort 메서드는 원본 배열을 직접 수정하므로,  이 때 따로 변수로 선언하지 않아도 된다.) sum 변수에 현재까지의 총 요청 금액을 저장하고, count 변수에 지원할 수 있는 부서의 수를 저장한다.

정렬된 배열을 반복문으로 순회하며 현재까지의 총 요청 금액이 예산을 초과하면 반복문을 종료하고, 그렇지 않으면 count를 증가시킨다. 마지막으로 반복문을 종료시키면 최종적으로 지원할 수 있는 최대 부서의 수를 반환한다.

 

 

// 함수를 써서 한다는 생각보단 일단 정렬시키고 반복문이 답일 것이라 생각했다. 근데 의외로 고득점에 놀랐다. 허나 break 를 알게 되면서 더 쉽게 풀 수 있는 방법이 있다는 것을 알았다.

(break는 주로 반복문(for, while, do-while) 내에서 특정 조건이 충족되었을 때 반복문을 즉시 종료하기 위해 사용된다. break를 사용하면 반복문을 빠져나가고, 반복문 다음에 오는 코드로 실행이 이어진다.)

나는 while 반복문에만 사용하는 줄 알았는데 for 반복문에도 사용할 수 있다는 것을 알게 되었다.

 

 

문제 2. 크기가 작은 부분 문자열
 

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.
예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.



입출력 예
각 부서에서 [1원, 3원, 2원, 5원, 4원]만큼의 금액을 신청했습니다. 만약에, 1원, 2원, 4원을 신청한 부서의 물품을 구매해주면 예산 9원에서 7원이 소비되어 2원이 남습니다. 항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다. 위 방법 외에 3개 부서를 지원해 줄 방법들은 다음과 같습니다.

 
풀이=해답.

function solution(t, p) {
    let count = 0;
    for(i = 0 ; i <= t.length - p.length ; i += 1){
        if(Number(t.slice(i,p.length+i)) <= Number(p)){
            count += 1
        }        
    }
    return count
}

 
=> slice 메서드를 활용한게 컸다. 문자열을 p의 길이만큼 t에서 slice로 꺼내준 후에, Number 메서드로 감싸준 후, 그 수를 p와 비교하는 조건문을 사용했다. 이 후, 반복문을 돌리면서 자릿수를 하나씩 늘려가도록 하며 조건이 부합하면 count에 1씩 추가했다. 마지막으로 반복문이 종료되면 count를 반환하도록 하였다.

 

// 7점을 받을 줄은 몰랐는데 해답을 보니 정석으로 풀었다. 문제를 풀 때 문자열인지 배열인지 잘 확인하고 어떤 메서드를 사용하는게 좋을지 판단하는게 중요한 거 같다.

 

 

하루 총평.

 반복문을 어떻게 사용하는지, 조건문은 어떻게 적용하는지 고민을 여러번 해본 결과가 큰 듯하다. 문자열에 관련한 문제라면 문자열 관련 메서드를 떠올리고 배열에 관련한 문제라면 배열 관련 메서드를 떠올리는 것이 중요한 거 같다. 또한 횟수를 적용해야할땐 반드시 count를 떠올릴 것.