알고리즘 48번 - K번째 수

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

JS

문제

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.

 

입출력 예
array                        commands                               return
[1, 5, 2, 6, 3, 7, 4]    [[2, 5, 3], [4, 4, 1], [1, 7, 3]]      [5, 6, 3]
입출력 예 설명
[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

---

계획

배열을 자르고 (i ~ i+j)

정렬

k번째 숫자를 배열에 넣기

commands길이만큼 반복

배열  반환

---

참고, 풀이

let arr = array.slice( i, i+j )

arr.short()

return arr[k]

function solution(array, commands) {
    let arrK = [];
    commands.forEach((c) => {
        let i = c[0] - 1;
        let j = c[1];
        let k = c[2] - 1;
        console.log(i, " / ", j, " / ", k);
        let arr = array.slice(i, j).sort();

        console.log(arr);
        arrK.push(arr[k]);
    });
    return arrK;
}
const a = [1, 5, 2, 6, 3, 7, 4];
const c = [
    [2, 5, 3],
    [4, 4, 1],
    [1, 7, 3],
];
// [5, 6, 3]

console.log(solution(a, c));

성공. 코드 줄이기

function solution(array, commands) {
    let arrK = [];
    commands.forEach((c) => {
        let arr = array.slice(c[0] - 1, c[1]).sort();
        arrK.push(arr[c[2] - 1]);
    });
    return arrK;
}

오류생김

배열 내 동일한 값도 처리할 수 있도록 sort 수정

---

답

function solution(array, commands) {
    let arrK = [];
    commands.forEach((c) => {
        let arr = array.slice(c[0] - 1, c[1]).sort((a, b) => a - b);
        arrK.push(arr[c[2] - 1]);
    });
    return arrK;
}

코드 간략화하기

function solution(array, commands) {
    return commands.map(c => {
        return array.slice(c[0] - 1, c[1]).sort((a, b) => a - b)[c[2] - 1];
    });
}

 처리한 commands위치의 배열을 k번째 값으로 바꿈

 

다른사람 답

function solution(array, commands) {
    return commands.map(command => {
        const [sPosition, ePosition, position] = command
        const newArray = array
            .filter((value, fIndex) => fIndex >= sPosition - 1 && fIndex <= ePosition - 1)
            .sort((a,b) => a - b)    

        return newArray[position - 1]
    })
}

배열 구조 분해 할당 (Array Destructuring Assignment)

 

function solution(array, commands) {
    return commands.map(([from, to, k]) => 
        array.slice(from - 1, to).sort((x, y) => x - y)[k - 1]
    );
}

---

참고

https://school.programmers.co.kr/learn/courses/30/lessons/42748/solution_groups?language=javascript