정렬


2750번 (수 정렬하기)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split('\n').map(Number);
input.shift();
input.sort(function(a, b) {
return a - b;
});
for (let i = 0; i < input.length; i++) {
console.log(input[i]);
}
  • \n을 기준으로 배열로 잘라 담았을 때, 맨 앞 인덱스의 값은 input의 길이이므로 shift()로 없애주었다.
  • 이후 .sort() 메소드를 이용하여 정렬하였다.
  • for문을 통해 출력하였다.
  • 2587번 (대표값2)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split('\n').map(Number);
    let average = 0;
    input.sort(function(a, b) {
    return a - b;
    });
    input.forEach((el) => {
    average += el;
    });
    average = average / 5;
    console.log(average);
    console.log(input[2]);
  • sort()를 이용하여 배열로 받은 input을 정렬해준다.
  • forEach문을 이용하여 배열 안 모든 값들을 average에 더해준다.
  • average를 5로 나눈 값이 평균이므로 이를 5로 나누어 다시 average에 담는다.
  • average를 출력한다.
  • input 배열이 정렬되었으므로 5개 요소 중 3번째 인덱스가 중앙값이므로 input[2]를 출력해준다.
  • 25305번 (커트라인)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split('\n');
    const [N, k] = input[0].split(' ').map(Number);
    const scoreArr = input[1].split(' ').map(Number);
    scoreArr.sort((a, b) => b - a);
    console.log(scoreArr[k-1]);
  • 첫째 줄의 학생 수와 수상자 수는 각각 N과 k로 받았다.
  • 둘째 줄의 점수 리스트는 scoreArr 배열로 받았다.
  • scoreArr 배열을 sort()를 이용하여 내림차순으로 정렬하였다. (b - a 이용)
  • scoreArr[k-1] 값을 출력하였다.
  • 2751번 (수 정렬하기 2)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split('\n').map(Number);
    input.shift();
    input.sort((a, b) => a - b);
    console.log(input.join('\n'));
  • for문으로 출력하니 시간초과가 됐다.
  • 처음에는 출력 쪽 문제가 아닌 정렬 알고리즘 문제라고 생각해서 퀵 정렬 알고리즘을 적용하여 돌려봤으나 다시 한번 시간초과가 됐다.
  • 문제는 출력 쪽 이었고 join(’\n’)을 통해 하나로 합쳐서 출력하니 sort()로도 시간초과 없이 통과되었다.
  • 2108번 (통계학)

    const fs = require("fs");
    const input = fs
    .readFileSync("./input.txt")
    .toString()
    .trim()
    .split("\n")
    .map(Number);
    let average = 0;
    let median = 0;
    let mode = 0;
    let range = 0;
    input.shift();
    input.sort((a, b) => a - b);
    for (let i = 0; i < input.length; i++) {
    average += input[i];
    }
    average = Math.round(average / input.length);
    median = input[Math.floor(input.length / 2)];
    range = input[input.length - 1] - input[0];
    const map = new Map(); // Map 객체 생성
    let max = 1;
    for (let num of input) { // input의 길이만큼 for문 실행. num은 각 element를 의미
    if (map.has(num)) { // map이 num을 가지고 있는지 boolean 형태로 얻음
    max = Math.max(max, map.get(num) + 1); // 현재 max와 map에 저장되어있는 num의 값+1 중 더 큰 것이 max가 된다.
    map.set(num, map.get(num) + 1); // num의 값을 +1 해준다.
    } else map.set(num, 1); // 새로 해당 num에 해당하는 요소를 만든다.
    }
    const maxArr = []; // 최빈값(들)을 담을 배열
    for (let [key, val] of map) { // for...of문은 Map 객체에서 이처럼 쓸 수 있다.
    if (val === max) maxArr.push(key); // max값과 해당 num의 값이 같다면 해당 키를 push
    }
    mode += maxArr.length === 1 ? maxArr[0] : maxArr[1]; // 삼항연산자
    console.log(average + "\n" + median + "\n" + mode + "\n" + range);
  • 처음엔 실버3 치고 쉬운 것 같다 생각했는데 함정은 최빈값이었다.
  • 사실 처음에는 Map 객체에 대해 몰라서 다른 방법들을 시도하다 포기했다.
  • 검색해보니 Map객체를 이용한 풀이가 대부분이어서 Map 문법에 대해 찾아본 후 풀었다.
  • 우선 sort()로 정렬을 먼저 하고 시작했다.
  • 산술평균
  • 중앙값
  • 범위
  • 최빈값
  • 1427번 (소트인사이드)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("").map(Number);
    input.sort((a, b) => b - a);
    const answer = input.join('');
    console.log(answer);
  • 자바스크립트에서는 split과 join이 존재해서 쉬운 문제였던 것 같다.
  • 11650번 (좌표 정렬하기)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const N = input.shift();
    let arr = [];
    for (let i = 0; i < N; i++) {
    arr.push(input[i].split(" ").map(Number));
    }
    arr.sort(function(a, b) {
    if (a[0] == b[0]) {
    return a[1] - b[1];
    } else {
    return a[0] - b[0];
    }
    });
    for (let i = 0; i < N; i++) {
    arr[i] = arr[i].join(' ');
    }
    console.log(arr.join('\n'));
  • N은 input 좌표의 개수이다.
  • arr에 input을 이중배열 형태로 push한다.
  • 이를 이용하여 sort()를 하는데, 만약 x좌표가 같다면(a[0] == b[0]) y축을 기준으로 정렬한 값(a[1] - b[1])을 리턴하고, 그렇지 않으면 x 축을 기준으로 정렬한 값(a[0] - b[0])을 리턴한다.
  • 결과값을 join하여 출력한다.
  • 11651번 (좌표 정렬하기 2)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const N = input.shift();
    let arr = [];
    for (let i = 0; i < N; i++) {
    arr.push(input[i].split(" ").map(Number));
    }
    arr.sort(function(a, b) {
    if (a[1] == b[1]) {
    return a[0] - b[0];
    } else {
    return a[1] - b[1];
    }
    });
    for (let i = 0; i < N; i++) {
    arr[i] = arr[i].join(' ');
    }
    console.log(arr.join('\n'));
  • 11650번 문제와 같다. 1과 0만 바꾸어 출력해주었다.
  • 1181번 (단어 정렬)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const N = input.shift();
    let answer = [];
    input.sort();
    input.sort((a, b) => a.length - b.length);
    answer = [...new Set(input)];
    for (word of answer) {
    console.log(word);
    }
  • 이 문제도 자바스크립트로는 풀기 편한 문제이다.
  • sort()를 이용해 우선 알파벳 순으로 정렬을 한다.
  • 이후 단어의 length를 기준으로 다시 정렬해준다.
  • 이렇게 해도 문제에서 요구하는 정렬이 가능한 이유는 sort()가 안정한 정렬을 제공하기 때문이다.
  • 중복 제거를 위해 Set객체를 이용하여 answer 배열에 중복을 제거한 값을 담는다.
  • 요소를 하나씩 출력한다.
  • 10814번 (나이순 정렬)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const N = input.shift();
    let members = [];
    for (let i = 0; i < N; i++) {
    members.push(input[i].split(' '));
    members[i][0] = parseInt(members[i][0]);
    }
    members.sort((a, b) => a[0] - b[0]);
    members.sort((a, b) => a[1] - b[1]);
    for (member of members) {
    console.log(member.join(' '));
    }
  • 이중배열로 입력을 받아 안정한 정렬(sort())을 이용하여 두번 정렬했다.
  • 18870번 (좌표 압축)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const inputArr = input[1].split(' ').map(Number);
    const setArr = [...new Set(inputArr)].sort((a, b) => a - b);
    const map = new Map();
    let answer = '';
    setArr.forEach((el, idx) => map.set(el, idx));
    for (num of inputArr) {
    answer += map.get(num) + " ";
    }
    console.log(answer.trim());
  • 문제 이해 자체가 어렵다. 입력의 2번째 줄을 배열로 받았을 때, 해당 요소 숫자보다 작은 수가 몇개 있는지가 해당 요소의 좌표 압축이 된다.
  • 예를 들어, 2 4 -10 4 -9 에서 2보다 작은 수는 -10과 -9 2개이므로 0번 인덱스의 출력은 2가 되어야 한다. 이에 따라 출력은 2 3 0 3 1 이 되는 것이다. (중복은 두번 세지 않음)
  • 처음에는 Set 객체를 이용하여 중복을 제거한 후 이중 for문을 통해 본인보다 작은 숫자가 있으면 count를 1씩 증가하는 식으로 문제를 풀이했다. (첫 번째 시간초과)
  • 이후에는 정렬을 이용해야 하는 것을 깨닫고 중복제거, 정렬 후 for문 안에 .indexOf() 메소드를 이용하여 inputArr[i]가 setArr의 몇번 인덱스인지를 이용하여 해결하려고 하였다. (두 번째 시간초과)
  • 마지막 방법으로 indexOf() 대신 forEach와 Map을 이용하여 Map객체 안에 요소의 값과 요소의 인덱스를 담아 세팅했다. 이후 for문과 Map.get()을 이용하여 정답을 가져왔다. (성공)
  • 시간복잡도를 잘 해결해야 하는 문제였다.