백준 : 11650-javascript

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

11650번: 좌표 정렬하기

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1 복사

 

5
3 4
1 1
1 -1
2 2
3 3

예제 출력 1 복사

1 -1
1 1
2 2
3 3
3 4

 

풀이

 

간단한 정렬 문제이다.

다만 x를 먼저 정렬한 후에 y를 정렬하게 되는데, 2가지 방법이 떠올랐다.

 

1. 먼저 x를 기준으로 정렬한 후 x값이 같은 세트를 다시 y를 기준으로 정렬한다.

 

2. x값의 차이와 y값의 차이에 가중치를 달리 주고 새로운 비교 값을 만든다.

 

1번의 방법은 x값이 서로 같은 세트만 비교하면 되기 때문에 더 효율적이다.

하지만 2번은 분기점을 만들지 않아도 되서 코드가 더 간결해 보일 것이다.

 

나는 코드 짧은 걸 좋아해서 2번의 방식을 선택하였다.

 

let inputs = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let answer = "";

inputs = inputs.map((x) => x.split(" ").map(Number));
inputs.shift();

inputs= inputs
  .sort((a, b) => (a[0] - b[0]) * 200001 + a[1] - b[1])
  .forEach((x) => (answer += `${x.join(" ")}\n`));

console.log(answer);

 

sort를 보면 x의 차이에는 200001을 곱하고 y값의 차이는 그대로 사용한다.

이는 x와 y모두 가능한 최소의 차이가 200000이기 때문이다. (-100000과 100000)

따라서 x가 1 차이나고 y가 -200000이 차이나는 경우가 가장 극단적인 차이라고 볼 수 있는데, x의 1차이는 y의 기준으로 200001 차이이므로 x의 1 차이가 y의 -200000 차이보다 더 크게 인식된다.

 

또한 console.log를 forEach로 작동하면 시간초과가 나와서 forEach로 string을 더해주고 마지막에 console.log를 하는 형식으로 만들었다.