백준 7568 덩치 | 실버 5

🏖️ 문제 바로가기

이 문제는 사실 처음에 틀려서 반례를 찾아가며 문제점을 찾아 해결했다.

초반 코드

package source_code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

// 덩치: (x, y) = (몸무게, 키)
// (x,y), (p,q) => x > p and y > q => A 덩치가 B보다 크다!
// 키와 몸무게가 둘 다 크지 않다면 같은 등수가 됨

// 입력: 전체 사람 수 // 각 사람의 몸무게와 키
// 출력: 순서대로 덩치 등수 나열

public class B_S5_7568_big {
	static int higherWeight = 0;
	static int higherHeight = 0;
	static int jump = 1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int personNum = sc.nextInt();
		int[][] persons = new int[personNum][2];
		int[] result = new int[personNum];

		for (int i = 0; i < personNum; i++) {
			persons[i][0] = sc.nextInt();
			persons[i][1] = sc.nextInt();

			// result 0으로 초기화
			result[i] = 0;
		}

		// 1. 몸무게 max와 키 max를 찾아서 1등 입력
		higherWeight = 0;
		higherHeight = 0;

		for (int i = 0; i < personNum; i += jump) {
			writeRank(i + 1, result, persons, personNum, higherWeight, higherHeight);
		}

		for (int i = 0; i < personNum; i++) {
			System.out.print(result[i]);
			if (i != personNum - 1) {
				System.out.print(" ");
			}
		}

	}

	public static void writeRank(int rank, int[] result, int[][] persons, int personNum, int higherWeight,
			int higherHeight) {
		List<Integer> highPerson = new ArrayList<>();

		for (int i = 0; i < personNum; i++) {
			int currentWeight = persons[i][0];
			int currentHeight = persons[i][1];

			if (currentWeight > higherWeight && currentHeight > higherHeight && result[i] == 0) {
				highPerson.clear();
				highPerson.add(i);

				higherWeight = currentWeight;
				higherHeight = currentHeight;
			} else if ((currentWeight > higherWeight || currentHeight > higherHeight) && result[i] == 0) {
				highPerson.add(i);

				if (currentWeight >= higherWeight) {
					higherWeight = currentWeight;
				} else {
					higherHeight = currentHeight;
				}
			}
		}

		// 등수 기록
		for (int i = 0; i < highPerson.size(); i++) {
			result[highPerson.get(i)] = rank;
		}

		jump = highPerson.size();
	}
}

굉장히 길고 정신 없는 코드..에 완전 잘못 잡은 방향.
또 습관이 튀어나와서 쓸데없이 복잡하게 생각했다.

문제에서는 " 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다."라고 했는데, 이걸 그대로 하면 되는데 쓸데없이 제일 큰 값을 찾고 그걸 이용해서 등수를 매기는 형식을 취했다. 근데 이 방식은 그냥 복잡하기만 한게 아니라 틀린 방식. 반례가 있었다.

5
55 180
60 177
77 170
65 185
90 190

예상 답안

3 3 2 2 1

사람 인덱스	(몸무게, 키)	자신보다 더 큰 사람 수	등수
0	55 180	(65 185), (90 190) → 2	3
1	60 177	(65 185), (90 190) → 2	3
2	77 170	(90 190) → 1	2
3	65 185	(90 190) → 1	2
4	90 190	없음	1

-> 이 반례를 보면서 등수를 매기는 방향 자체가 틀렸음을 직감하고 문제를 다시 읽었다.
그냥 복잡하게 갈 필요없이 현재 나보다 큰 사람들 수를 체크해서 1만 더하면 되는 것이었다.

그래서 수정한 코드.

수정 코드

package source_code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

// 덩치: (x, y) = (몸무게, 키)
// (x,y), (p,q) => x > p and y > q => A 덩치가 B보다 크다!
// 키와 몸무게가 둘 다 크지 않다면 같은 등수가 됨

// 입력: 전체 사람 수 // 각 사람의 몸무게와 키
// 출력: 순서대로 덩치 등수 나열

public class B_S5_7568_big {
	static int higherWeight = 0;
	static int higherHeight = 0;
	static int jump = 1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int personNum = sc.nextInt();
		int[][] persons = new int[personNum][2];
		int[] result = new int[personNum];

		for (int i = 0; i < personNum; i++) {
			persons[i][0] = sc.nextInt();
			persons[i][1] = sc.nextInt();

			// result 0으로 초기화
			result[i] = 0;
		}

		higherWeight = 0;
		higherHeight = 0;

		for (int i = 0; i < personNum; i++) {
			int biggerNum = 0;

			if (result[i] == 0) {
				for (int j = 0; j < personNum; j++) {
					if (persons[j][0] > persons[i][0] && persons[j][1] > persons[i][1] && i != j) {
						biggerNum++;
					}
				}
			}

			// 등수 기록
			result[i] = biggerNum + 1;
		}

		for (int i = 0; i < personNum; i++) {
			System.out.print(result[i]);
			if (i != personNum - 1) {
				System.out.print(" ");
			}
		}

	}

}

처음에는 제일 큰 사람부터 등수를 매겨보자는 생각으로 접근했다. 왜냐면 정렬 기반 문제라고 착각했기 때문.
근데 이 문제는 쌍 비교를 통해서 몇 명이 나보다 더 큰가?를 세는 것이었다. 정렬이 아니라!!

추가

사람을 나는 (int, int) 배열로 저장했는데, 이를 클래스로 다루면 가독성과 확장성이 높아질 것 같다. 사실 코테에서 클래스를 사용해본 적이 없는데, 한 번 시도해 봐야겠다.

class Person {
    int weight, height;

    Person(int weight, int height) {
        this.weight = weight;
        this.height = height;
    }

    boolean isBiggerThan(Person other) {
        return this.weight > other.weight && this.height > other.height;
    }
}