정렬

2023. 03. 27.

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()을 이용하여 정답을 가져왔다. (성공)

시간복잡도를 잘 해결해야 하는 문제였다.