[백준알고리즘] 7568번: 덩치 -C++

[백준알고리즘] 7568번: 덩치 -C++

7568번: 덩치 (acmicpc.net)

7568번: 덩치

예전에 파이썬으로 풀고 포스팅까지 했던 문제다... 그런데 오늘은 풀면서 엄청 헤매였다....

아래는 그때 포스팅했던 글이다... 

그때 손풀기용으로 풀었다며 당당하던 나는 어디로 갔는가..

[백준알고리즘] 7568번: 덩치 -Python (tistory.com)

[백준알고리즘] 7568번: 덩치 -Python

 

아무튼 오늘은 문제를 잘못 파악해서 굉장히 헤매게 됐다. 

그냥 문제를 이해를 했지만 내 멋대로 바꿔서 해석한게 맞는 것 같기도 하고(?) 아무튼 이상하게 풀었다..!

 

결국 깨닫긴 했지만 시간을 너무 낭비한 것 같다. ㅠㅠ

 

결국 문제에 정의된 대로 rank는 나보다 몸무게도 많이 나가고 키도 커야한다!!!

여기서 말로 설명할 수 없을정도로 뭔가 단단히 오해하고 문제를 계속 풀었다. 그러고는 왜 안되냐고 이거 뭐 오류 찾은거냐고 당당했었다....

 

아무튼 문제를 이해한 뒤로는 해결한 풀이 방법은 다음과 같다.

우선, 입력된 몸무게와 키를 몸무게를 기준으로 정렬한다. 정렬을 할 때에는 내림차순으로 정렬하기 위해 sort 함수 안에 STL 중 하나인 greater<> 를 사용했다. 참고로 greater<>의 템플릿을 통한 타입추론은 C++14부터 지원된다고 한다.

이후 하나씩 몸무게가 큰 쌍부터 작은 쌍으로 순차적으로 확인하게 되는데, 이때 각각의 몸무게와 키를 기준으로 앞 쪽(정렬된 상태에서 몸무게가 큰 쪽)으로 현재 몸무게와 키보다 큰 값을 갖는 쌍이 몇 개인지 확인하도록 했다.

 

즉, 각각의 사람마다 그 사람보다 몸무게가 많이 나가고 키가 큰 사람의 수를 일일이 확인해준 것이다. 그 와중에 확인하는 경우의 수만 나름 줄이려고 한 것이고..

몸무게를 정렬했으나, 몸무게를 또 비교해준 것은 아래와 같은 경우가 있을 수 있기 때문이다.

55 185
55 177
55 180

 

위의 경우에는 3개의 값 모두 몸무게의 우위를 판단할 수 없어 같은 등수를 갖게 된다. 하지만, 몸무게를 기준으로 정렬했다고 비교를 하지 않게 된다면 각각의 등수를 정하는데 오류를 범할 수 있다.

 

아래에는 내 문제를 깨닫게 해준 반례와 C++로 짠 소스코드이다. Python으로 짠 코드는 위의 링크를 통해 들어가면 된다.

 

---

아래는 내가 참고했던 반례들이다. 사실 문제만 제대로 파악했다면 필요 없었을 반례들이지만... 너무 늦게 눈치차린 내 탓이다..

/* 반례
* 
5
9 3 
8 2
3 9
2 8
1 7
// answer : 1 2 1 2 3
*/

/* 반례
* 
5
177 75
133 16
183 75
126 156
49 24
// answer : 1 3 1 1 4
*/

/* 반례
* 
3
20 30
10 20
30 10
// answer : 1 2 1
*/

---

아래는 C++ 코드다.

#include <iostream>
#include <algorithm>
#include <vector>

void solve(void);

int main(void)
{
	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::tuple<int, int, int>> weight_height; // height, wight, idx
	for (int i = 0; i < n; i++)
	{
		int weight, height;
		std::cin >> weight >> height;
		weight_height.push_back(std::make_tuple(weight, height, i));
	}
	std::sort(weight_height.begin(), weight_height.end(), std::greater<>());

	std::vector<int> ranks(n);
	for (int i = 0; i < n; i++)
	{
		int weight, height, idx;
		std::tie(weight, height, idx) = weight_height[i];

		int rank = 1;
		for (int j = i - 1; j >= 0; j--)
		{
			int cmp_weight, cmp_height, cmp_idx;
			std::tie(cmp_weight, cmp_height, cmp_idx) = weight_height[j];

			if (height < cmp_height && weight < cmp_weight)
				rank++;
		}

		ranks[idx] = rank;
	}

	for (int r : ranks)
		std::cout << r << " ";
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다