[BOJ] 11650번 : 좌표 정렬하기

백준 11650번 : 좌표 정렬하기

🔗 문제 링크

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

11650번: 좌표 정렬하기

 

---

💬 문제

 정렬 알고리즘 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 1번째 줄에 좌표의 개수 N이 주어진다.
2. 2번째 줄부터 각 좌표의 x값과 y값이 공백으로 구분되어 나열되어 있다.
3. 좌표를 x값이 증가하는 순으로 정렬하고, x값이 같을 경우 y값이 증가하는 순으로 정렬한다.
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서 1번째 줄에 N을 주고, 그 다음줄부터 x좌표와 y좌표를 공백 기준으로 주어진다.

줄바꿈을 기준으로 N과 좌표 정보가 담긴 배열 arr로 나눠주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

🔑 풀이1 : sort() 및 split() 메서드

• 입력값 input을 좌표의 개수 N과 좌표 정보가 담긴 배열 arr로 나눠준다.
• 각 좌표의 정보를 a와 b로 받아와 비교를 해준다.
• split(' ')[0] (x값)이 같이 않을 경우에는 x값을 오름차순으로 정렬해준다.
• 그 다음으로 x값이 같은 경우에 split(' ')[1] (y값)을 오름차순으로 정렬해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
[N, ...arr] = input;

console.log(solution(arr).join('\n'));

function solution(arr) {
  return arr
    .sort((a, b) => {
      if (a.split(' ')[0] !== b.split(' ')[0]) {   // 유니코드로 문자열 숫자 비교
        return a.split(' ')[0] - b.split(' ')[0];  // x좌표 오름차순 정렬
      }
      return a.split(' ')[1] - b.split(' ')[1];    // x좌표가 같을때, y좌표 오름차순 정렬
    });
}

 

시간은 다음과 같이 걸렸다.

split()으로 매번 새로운 배열을 만들고 인덱스값을 부여해서 시간이 오래 걸린 것 같다.

 

 

🎯 풀이를 위한 개념 설명

 유니코드(Unicode) 에 대해 생소할 수 있다.

간단하게 설명하자면, 모든 문자에 특정 번호를 매겨 정리해둔 기준이다. 아래표처럼 특정 문자에 문자순으로 숫자값을 매겨뒀기에 문자도 숫자로 바꿔 정렬할 수 있는 것이다.

 

출처 : https://www.dazhuanlan.com/gustave2454/topics/1744099

 

---

🔑 풀이2 : sort() 메서드 및 parseInt() 메서드로 정수화

• 입력값 input을 좌표의 개수 N과 좌표 정보가 담긴 배열 arr로 나눠준다.
• split(' ')으로 시간이 꽤 오래 걸렸기에, 미리 각 좌표 값을 정수화해줬다.
  - [ [ 3, 4 ], [ 1, 1 ], [ 1, -1 ], [ 2, 2 ], [ 3, 3 ] ]
• x값이 같이 않을 경우에는 x값을 오름차순으로 정렬해준다.
• 그 다음으로 x값이 같은 경우에 y값을 오름차순으로 정렬해준다.
• 출력을 위해 x값과 y값을 다시 문자열로 전환해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
[N, ...arr] = input;
// 정수화
arr = arr.map(line => line.split(' ').map(num => parseInt(num)));

console.log(solution(arr).join('\n'));

function solution(arr) {
  return arr
    .sort((a, b) => {
      if (a[0] !== b[0]) {
        return a[0] - b[0];  // x좌표 오름차순 정렬
      }
      return a[1] - b[1];    // x좌표가 같을때, y좌표 오름차순 정렬
    })
    .map(num => `${num[0]} ${num[1]}`);  // x좌표, y좌표를 다시 문자열로 전환
}

 

시간 효율은 꽤 좋아졌다.

 

 

---

🔑 풀이3 : 객체 배열

• 입력값 input을 좌표의 개수 N과 좌표 정보가 담긴 배열 arr로 나눠준다.
• arr의 x값과 y값을 나누고 정수화 하여, 각각을 프로퍼티(property)로 가지는 객체를 생성해준다.
• 프로퍼티 x로 각 객체에 접근해 x값이 다를 경우 x값을 오름차순으로 정렬해준다.
• x값이 다를 경우, 프로퍼티 y로 각 객체에 접근해 y값을 오름차순으로 정렬해준다.
• 출력을 위해 x값과 y값을 다시 문자열로 전환해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
[N, ...arr] = input;

console.log(solution(arr).join('\n'));

function solution(arr) {
  return arr
    // x좌표와 y좌표를 프로퍼티로 가진 객체로 전환
    .map(line => ({ x: parseInt(line.split(' ')[0]), y: parseInt(line.split(' ')[1]) }))
    .sort((a, b) => {
      if (a.x !== b.x) {
        return a.x - b.x;  // x좌표 오름차순 정렬
      }
      return a.y - b.y;    // x좌표가 같을때, y좌표 오름차순 정렬
    })
    .map(num => `${num.x} ${num.y}`);  // x좌표, y좌표를 다시 문자열로 전환
}

 

이 역시 객체를 만들 때만 split(' ')으로 인덱스값을 부여했으므로, 1번째 방법보다 시간 효율이 나아졌다.