[알고리즘 떠먹여 주는 남자] 백준 7568 - 덩치 for Node.js

Sup lads!

오늘도 어김없이 알고리즘 문제 풀이로 돌아왔습니다. 조금 피곤하기도 했고, 한 번 알고리즘 문제를 잡으면 보통 한 시간 이상 소요했기에 흠.. 고민을 했지만 그래도 도전 해 보았는데 생각보다 문제가 일찍 풀려서 다행인 것 같습니다. 그럼 바로 문제 설명과 풀이로 넘어가 보도록 하겠습니다.

 

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

7568번: 덩치

 

덩치

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

58644

32344

27654

56.227%

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

이름(몸무게, 키)덩치 등수

A	(55, 185)	2
B	(58, 183)	2
C	(88, 186)	1
D	(60, 175)	2
E	(46, 155)	5

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

출력

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

제한

• 2 ≤ N ≤ 50
• 10 ≤ x, y ≤ 200

예제 입력 1 복사

5
55 185
58 183
88 186
60 175
46 155

예제 출력 1 복사

2 2 1 2 5

 

문제 풀이

이 문제 역시 브루트포스 카테고리 안에 있는 문제입니다. 카테고리를 미리 알고 접근 방식을 생각했기 때문에 조금 더 빨리 풀 수 있었다고 생각하지만, 모든 경우의 수 를 구하는 문제가 나온다면, 브루트포스 알고리즘도 하나의 풀이 방식이 될 수 있다는 것을 기억해 주시면 좋겠습니다.

 

위의 문제를 요약 해 보면:

• 덩치를 비교 할 때 키와 몸무게 모두 비교하여 두 비교군 모두 크거나 작을 경우에만 랭크의 변동이 생긴다.

라고 할 수 있습니다. 만약 A 가 B 보다 키는 더 크지만 몸무게가 적을 경우, 두 비교군은 같은 순위에 랭크 됩니다. 문제에 제시 된 표를 보시면 이해가 더 쉬울 것입니다.

 

문제에 대한 설명은 이 정도면 충분하다고 생각 되므로 제가 작성한 코드를 공유 해 보도록 하겠습니다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const numberOfPeople = Number(input.shift());
let answer = '';

for (let sourceIdx = 0; sourceIdx < numberOfPeople; sourceIdx++) {
  const bodyMass = input[sourceIdx].split(' ').map(Number);
  const [sourceWeight, sourceHeight] = [bodyMass[0], bodyMass[1]];
  let rank = 1;
  for (let targetIdx = 0; targetIdx < numberOfPeople; targetIdx++) {
    if (sourceIdx === targetIdx) continue;
    const comparedBodyMass = input[targetIdx].split(' ').map(Number);
    const [targetWeight, targetHeight] = [comparedBodyMass[0], comparedBodyMass[1]];
    if (sourceWeight < targetWeight && sourceHeight < targetHeight) {
      rank++;
    }
  }
  answer = sourceIdx === numberOfPeople - 1 ? `${answer}${rank}` : `${answer}${rank} `;
}

console.log(answer);

저는 nested for loop 을 이용하여 두 비교군의 덩치를 비교하였습니다. 안쪽 포 문의 if (sourceIdx=== targetIdx) continue; 는 모두 예상하실 수 있듯이, 비교군이 동일한 사람을 가리키는 케이스이므로 비교 할 가치가 없기 때문에 다음 비교군으로 넘겨 준다는 코드입니다.

 

덩치를 비교하여 비교군보다 덩치가 작을 경우 랭크가 하락 (숫자는 상승) 하기 때문에 rank++; 코드를 넣어 주었구요. 다른 부분은 딱히 설명하지 않아도 (제 나름대로) 꽤 직관적으로 코드를 짰다고 생각합니다.

 

제출 결과

처음 제출은 변수명을 단순 i, j 그리고 input[0], input[1] 이런 식으로 사용한 상태로 제출했을 때이고, 두 번째 제출은 변수를 선언해서 조금 더 가독성 있는 코드를 작성했을 때의 결과값입니다. 메모리와 시간에 미묘한 차이가 있네요.. 이게 얼마나 큰 차이인지 저는 아직 사실 잘 모르겠습니다. 메모리 넘나 어려운 것..

 

그래도 무리가 가지 않는다면 저는 직관적인 코드를 더 선호하기 때문에 두 번째 방법을 택할 것 같습니다. 무분별한 변수 선언은 문제가 되지만, 불분명한 무작위 변수명은 가독성을 떨어트리기 때문에 협업 하는 동료들의 시간을 허비할 수 있고, 심지어는 코드 작성자인 저 자신조차 나중에 어떤 코드인지 까먹을 수도 있기 때문이죠.

 

마무으리

처음에 "어떻게 모든 경우의 수를 비교하지?" 를 생각하는 데에만 한 10분 정도 소요한 것 같네요. 막상 그 질문에 대한 해답을 찾고 나서는 코드를 작성하는 데에 막히는 부분은 딱히 없었습니다. 조금이나마 발전 한 제 자신을 보니 약간 뿌듯하기도 하고, 역시 노력은 심하게 배신 하지는 않는다는 생각을 하게 됩니다.

앞으로도

한 알고리즘 풀이를 지속적으로 올릴 수 있도록 노력하겠습니다 🤗 . 그러니 도움이 되셨다면 좋아요도 눌러 주시고 댓글도 달아 주시면 감사하겠습니다. 그럼 이번 포스트는 여기서 마치도록 하겠습니다. 모두 굿나잇