[js, node.js]백준 7568:덩치

문제 요약

백준 7568:덩치

• 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다.
  단, 각 덩치 등수는 공백문자로 분리되어야 한다.

입력

5
55 185
58 183
88 186
60 175
46 155

출력

2 2 1 2 5

문제 분석

• 브루트 포스로 접근해야 각 자리의 값을 비교해서 덩치의 결과를 비교할 수 있을것이다.
• 몸무게와 키가 모두 크면 덩치가 크다고 할 수 있다.
• 비교시 문자열을 숫자로 바꾸자(혹시 모를 사이드 이펙트를 위해)
• 변수를 적게 사용해보자. (변수로 분리를 해서 쪼갠 데이터를 배열에 넣고하는 작업을 줄여보자)

문제 설계

const fs = require('fs');
const line = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [n, ...arr] = line;
const men = arr.map((v, i) => ({
  weight: parseInt(v.split(' ')[0]),
  height: parseInt(v.split(' ')[1]),
  rank: 1,
}));

for (let i = 0; i < men.length; i++) {
  for (let j = 0; j < men.length; j++) {
    if (
      i !== j &&
      men[i].weight < men[j].weight &&
      men[i].height < men[j].height
    ) {
      men[i].rank++;
    }
  }
}
console.log(men.map((i) => i.rank).join(' '));

정보 생성 arr.map() split()

• arr 배열의 각 요소를 split하여 몸무게(weight)와 키(height)를 나누고, 기본적으로 등수(rank)를 1로 설정한 객체로 변환한다.

덩치 비교를 통한 등수 계산 for

• 2중 반복문으로 모든 사람 men[i]에 대해 나머지 모든 사람 men[j]와 비교한다.
• 비교 조건
  • i !== j : 자신과는 비교하지 않는다.
  • men[i].weight < men[j].weight && men[i].height < men[j].height: 상대방의 몸무게와 키가 모두 더 큰 경우 등수를 증가시킨다

결론

• 주요 작업인 등수 계산이 $O(n^2)$이므로 전체 시간 복잡도는 $O(n^2)$
• 갑자기 궁금해서 배열 변환의 종류와 속도를 찾아봤는데, 스프레드 연산자로 쓰길 잘한 것 같다. 참고