[백준] 7468번 : 덩치

덩치

---

풀이 방법

굉장히 쉬운 문제였지만, 처음 접근법을 잘못잡아서 삽질을 많이 한 문제였다..

처음엔 내가한 접근으로는

1. 덩치 순으로 내림차순 정렬
2. list를 돌면서 rank를 결정
3. 다시 원래 순서로 정렬
4. 본인 rank 출력

틀린 코드..

물론 이 방법은 틀린 방법이다.
백준에 제출을 하니 IllegalArguementException이 계속 발생했다.
그래서 문제가 뭘까하고 질문게시판을 뒤져봤는데, 나랑 접근 방법도 유사하며, 같은 문제를 겪고있던 사람이 있었다.

https://www.acmicpc.net/board/view/133178

해당 질문의 응답으로 다음과 같은 글이 있었다.

문제에서는 각 학생의 등수를 구하기 위해 비교하는 방법을 제시했을 뿐, 1등부터 n등까지 순차적으로 줄을 세워야 한다는 규칙은 없습니다. 또한 두 학생의 덩치가 '같다'는 개념에 대해 정의한 적도 없습니다. 문제에서 정의한 대로 등수를 구하기만 하면 되고, 그것이 반드시 어떤 대수적인 비교 관계를 만족해야 하는 것은 아닙니다.

즉, 정렬을 할 필요가 없으며 문제에서 정의한 대로 등수를 구하는데, 대수적인 비교 관계가 필요없다 라고 한다.

그래서 다른 방법으로 접근을 했다.
브루트포스 방법으로 모든 경우의수를 탐색하는 방법으로 이 문제에서 원래 요구하던 방법 같았다.

1. 리스트에 키, 몸무게 저장
2. 각 사람에 대해서 다른 모든 사람과 비교해서 덩치가 작은 사람이 있다면 자신의 rank를 증가시킨다.
3. 각 사람에 rank처리 이후 StringBuilder에 저장

이 방법으로 해결하니, 훨씬 코드도 간결해지고 정렬같은 부수적인 작업이 필요없게 되었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Person{
    int x;
    int y;

    public Person(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        List<Person> people = new ArrayList<>();
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            people.add(new Person(x,y));
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            int rank = 1;
            for(int j=0;j<n;j++) {
                if(i==j)
                    continue;
                // 나보다 덩치가 작은 사람이 있으면 내 rank를 증가
                if((people.get(i).x < people.get(j).x) && (people.get(i).y < people.get(j).y))
                    rank++;
            }
            sb.append(rank).append(" ");
        }

        System.out.println(sb);
    }
}

느낀점

문제를 읽고, 어떻게 접근할지 정하는 것이 가장 중요하다고 느꼈다.
이번 문제에서 사용자들간의 비교를 통해 순서를 매기는 문제였는데, 당연히 정렬을 해서 순서를 매기는게 효율적일거라 생각해서 접근했었다.

하지만, 이번 문제는 입력 순서대로 출력을해야해서 덩치순으로 정렬을해도 다시 원래순서로 정렬해줘야하는 불편함이 있었다.

물론 내가 푼 방법은 아예 틀린 풀이기에 이런 비슷한 문제는 브루트포스 먼저 생각해보길 기억하자..