[백준] 7568번 - 덩치

문제 링크 : https://www.acmicpc.net/problem/7568

문제 탐색하기

1) 문제 분석

몸무게, 키 두 개의 값이 모두 커야 덩치가 크다고 얘기할 수 있다.
본인보다 덩치가 큰 사람의 수 + 1 값이 등수가 된다.
같은 덩치 등수를 가진 사람도 존재할 수 있다.

2) 가능한 시간복잡도

(1) 입력 처리

첫 줄에서 전체 인원 N을 받아오고, 이후 N줄에 대하여 (split(' ').map(Number)로 (몸무게, 키)쌍을 파싱하여 infos 배열을 생성한다.
한 줄 당 O(1)이며, N줄이므로 -> O(N)

(2) 등수 계산 처리

각 사람마다, 나머지 N-1명을 대상으로 "몸무게, 키가 모두 큰지" 조건을 검사한다.
한 사람의 기준으로 최대 N-1번까지 비교한다. -> O(N)
전체 N명을 다 비교하므로 -> O(N * N) = O(N의 제곱)
여기서 N <= 50이므로, 최악의 경우 O(2500)번 비교이지만, 실행에 부담이 없다.

(3) 출력 처리

등수 배열(ranks)을 join(' ')으로 문자열로 변환한 후 출력한다.
join 연산은 O(N) -> O(N)

(4) 전체 시간복잡도

입력 처리 : O(N)
등수 계산 : O(N의 제곱)
출력 처리 : O(N)-> 총합 : O(N의 제곱)

3) 알고리즘 선택 이유

이 문제는 모든 사람에 대해 "자신보다 몸무게와 키가 모두 큰 사람"의 수를 세고, 이를 기반으로 등수를 결정해야 한다.
이러한 조건은 정렬 기반의 우선순위 판단은 어렵고, 모든 쌍에 대해 조건을 체크해야 정확한 등수가 가능하다.
이러한 구조는 완전탐색(브루트포스)에 해당되며, 입력 크기(N <= 50)가 작기 때문에, O(N의 제곱) 알고리듬도 전혀 무리가 없다.-> 따라서 완전탐색 방식이 가장 자연스럽고 효율적인 선택이다.

잠깐! 브루트포스에 대한 간단한 설명, 그리고 관련 예시 문제는 여기를 참고하자.

코드 설계하기

1. 실행 구조

1) 몸무게, 키를 쌍으로 입력 받는다.

2) 해당 행을 공백 기준으로 분리하고, 숫자로 변환하여 배열로 저장한다.

3) 행의 index를 함수의 인자값으로 넘긴 뒤에, 본인 행을 제외한 값과 비교하여 등수를 구한다.

4) 구한 등수를 배열에 저장한 뒤, 모든 등수를 구하면 출력한다.

2. 고민이 되었던 부분

JavaScript

// 각 사람(index)의 덩치 등수를 계산하는 함수
function getBodyRank(index) {

    const weight = infos[index][0]; // 현재 사람의 몸무게
    const height = infos[index][1]; // 현재 사람의 키

    let rank = 1; // 기본 등수는 1

    // 덩치 등수 계산
    for (let i = 0; i < infos.length; i++){
        if (i != index) { // 본인 정보 제외
            if (infos[i][0] > weight && infos[i][1] > height) { // 덩치가 큰 경우
                rank++; // 등수 증가
            }
        }
    }
    return rank;

}

위는 각 사람의 덩치 등수를 계산하는 함수의 초안 코드이다. 이 코드에서는 infos[index][0], infos[i][0]처럼 배열을 직접 참조하여 비교를 수행하고 있다. 이러한 방식은 코드의 길이를 줄일 수 있다는 장점이 있지만, 잘못된 인덱스 참조나 오타로 인한 오류 발생 가능성도 크다고 생각했다. 따라서 비교에 필요한 값을 미리 변수로 분리하여 사용하는 것이 가독성과 안정성 측면에서 더 안전한 방법이라고 판단했다.

JavaScript

const ranks = []; // 등수를 담을 배열 선언

for (let i = 0; i < infos.length; i++){
    ranks.push(getBodyRank(i)); // 등수를 구하여 배열에 선언
}

const result = ranks.join(" "); // 결과를 위한 출력문 연결

또한, 등수를 담는 배열을 만드는 과정에서도 고민이 있었다. 이 방식은 배열을 선언한 뒤 push를 통해 값을 차례로 넣는 구조로, 절차적인 흐름이 명확하고 직관적이다. 그러나 push 대신 map을 활용하여 바로 값을 할당하는 방식도 존재한다. 생성과 할당을 동시에 처리하면 코드가 더 간결해진다는 장점이 있다. 반면 push 방식은 중간에 조건을 걸거나 디버깅하기에 유리하고, 흐름을 더 명확하게 보여줄 수 있다는 장점이 있다. 대신, 실수로 push를 빠뜨리는 등의 문제가 발생할 수 있다는 점은 단점으로 작용할 수 있다.

결국 이 두 가지 고민은 짧고 간단한 코드가 항상 좋은가, 혹은 명확하고 절차적인 흐름을 보여주는 코드가 더 나은가에 대한 질문으로 이어진다. 정답이 명확하게 존재하는 문제는 아니지만, 중요한 건 이런 선택지에 대해 끊임없이 고민하고, 상황에 맞는 판단을 내리는 습관을 기르는 것이라 생각했다.

정답 코드

JavaScript

// 사용 언어 : Javascript

// 각 사람(index)의 덩치 등수를 계산하는 함수
function getBodyRank(index) {
    const weight = infos[index][0];  // 현재 사람의 몸무게
    const height = infos[index][1];  // 현재 사람의 키

    let rank = 1;  // 기본 등수는 1

    for (let i = 0; i < infos.length; i++) {
        if (i === index) continue;  // 자기 자신은 비교에서 제외

        const [otherWeight, otherHeight] = infos[i];

        // 다른 사람이 몸무게, 키 모두 더 클 경우 등수 증가
        if (otherWeight > weight && otherHeight > height) {
            rank++;
        }
    }

    return rank;
}


// ⬇️ 입력 처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

input.shift();  // 첫 줄(N)은 사용하지 않으므로 제거
const infos = input.map(line => line.split(' ').map(Number));  // 숫자 배열로 변환

// ⬇️ 등수 계산
const ranks = infos.map((_, index) => getBodyRank(index));

// ⬇️ 출력
console.log(ranks.join(' '));

마무리하며

문제를 처음 접했을 때, "각 사람의 덩치를 어떻게 비교해야 할까?"라는 고민이 들었지만, 조건을 차근히 분석해보니 몸무게와 키가 모두 더 큰 경우만 '더 큰 덩치'로 간주한다는 단순한 규칙이 있다는 것을 파악할 수 있었다. 이후엔 자연스럽게 완전탐색 방식이 떠올랐고, 하나씩 비교하며 등수를 계산하는 로직을 구현하는 데 큰 어려움은 없었다.

다만 코드를 작성하면서, 배열을 직접 참조할 것인가 vs 변수로 분리할 것인가, push를 사용할 것인가 vs map으로 바로 처리할 것인가와 같은 선택의 순간들이 있었다. 이런 고민은 단순히 코드 길이나 스타일의 차이를 넘어서, 가독성, 실수 방지, 유지보수성과도 연결되는 중요한 포인트임을 다시금 느꼈다.

이번 문제를 통해 정답을 맞추는 것에만 집중하는 것이 아니라, 더 좋은 방식으로 구현하려는 고민이 문제 해결력의 일부임을 실감했다. 앞으로도 문제를 풀 때 단순히 통과하는 데 그치지 않고, 더 나은 방향을 탐색하고 선택하는 습관을 이어가고 싶다.

최근 글