[소프티어] - 우물 안 개구리 (C++)

eunssP·2023년 5월 12일
0

Algorithm

목록 보기
1/1
post-thumbnail

문제

헬스장에서 N명의 회원이 운동을 하고 있다. 각 회원은 1에서 N사이의 번호가 부여되어 있고, i번 회원이 들 수 있는 역기의 무게는 Wi이다. 회원들 사이에는 M개의 친분관계 (Aj, Bj)가 있다. (Aj, Bj)는 Aj번 회원과 Bj번 회원이 친분 관계가 있다는 것을 의미한다. i번 회원은 자신과 친분 관계가 있는 다른 회원보다 들 수 있는 역기의 무게가 무거우면 자신이 최고라고 생각한다. 단, 누구와도 친분이 없는 멤버는 본인이 최고라고 생각한다.

이 헬스장에서 자신이 최고라고 생각하는 회원은 몇 명인가?

제약조건

2 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ Wi ≤ 109
1 ≤ Aj, Bj ≤ N
Aj ≠ Bj

입력형식

첫 번째 줄에 두 정수 N, M이 주어진다.
두 번째 줄에 N개의 정수 W1, W2, ... , WN 이 주어진다.

다음 M개의 줄의 j번째 줄에는 두 정수 Aj, Bj 가 주어진다.

출력형식

첫 번째 줄에 자신이 최고라고 생각하는 회원 수를 출력한다.

문제풀이

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

using namespace std;

int m, n, imBest;

int main()
{
	cin >> n >> m;
	
	int weight[n] = {};		// 회원 별 최대 무게
	vector<int> pair [n];	// 회원 본인의 무게 및 본인과 짝을 이루는 타 회원들의 무게

	for (int i=0; i<n; i++){
		cin >> weight[i];
		pair[i].push_back(weight[i]);	// 본인 무게 저장
	}

	for (int i=0; i<m; i++){
		int user1, user2;
		cin >> user1 >> user2;
        
		// 타 회원 무게 저장
		pair[user1-1].push_back(weight[user2-1]);
		pair[user2-1].push_back(weight[user1-1]);
	}

	for (int i=0; i<n; i++){
    	// 짝이 없는 경우 = pair에 본인밖에 없는 경우
		if (pair[i].size() == 1) imBest++;
	
		else {
        	// 내림차순 정렬
			sort(pair[i].begin(), pair[i].end(), greater<>());
			
            // 최대값을 가지는 사람이 둘 이상일 때
			if (pair[i][0] == pair[i][1]) continue;
			
            // 최대값을 가지는 사람이 한사람이고, 그사람이 회원 본인일 때
			else if (weight[i] == pair[i][0])
				imBest ++;
		}
	}

	cout << imBest;
	return 0;
}
profile
배고파용

0개의 댓글