[Softeer] 우물 안 개구리(Lv.3) - Day3

📋 개요 

3일차의 첫번째 문제 GBC(Lv.2)를 풀었다. 딱히 어려운 문제는 아니였고 데이터를 저장하고 저장한 데이터를 연산만하면 되는 문제였던거 같다.

2024.01.29 - [Algorithm/Problem] - [Softeer] GBC(Lv.2) - Day3

[Softeer] GBC(Lv.2) - Day3

 

3일차의 두 번째는 '우물 안 개구' 문제이다. 딱히 문제를 풀때 어려운건 없었지만, 헷갈릴만한 요소들이 몇가지 있었다.

https://softeer.ai/practice/6289

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

🧩 문제

헬스장에서 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 가 주어진다.	첫 번째 줄에 자신이 최고라고 생각하는 회원 수를 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1		3
2		2

🖥️ 내 코드

---

📖  해설 및 느낀점

두가지 버전으로 해서 풀었다.

1. 2차원 vector
2. pair<int, int>

# 풀이 - 2차원 vector 

 

2차원 백터를 생성한 후에 matrix로 표현했을때 코드가 실행되는 모습이다. 그래프 탐색과 유사한 모습을 보이게 되는데 여기서 집중해서 봐야할 것은 친구가 여러명일때 한명이라도 나랑 같거나 나보다 더 많은 무게를 들게된다면 카운팅을 하지 않는것이 중점이다.

 

i = 3일 때가 제일 적절한 예시이다. f=2일 때는 5가 7보다 크니깐 위에 코드에서는 적용되지 if문을 타지 않고 flag가 false로 변경되지 않았다. 

하지만 두번째 친구를 만났다. f= 4일때는 회원3번이 회원4번이랑 같은 무게를 쳤다. 그렇다면 flag가 flase로 바뀌면서 최종적으로 false가 나오게된다. 먼저 false가 나오면 다음차례 친구를 확인하지 않고 break문을 걸어 빠져나온다.

// 2차원 백터에 집어넣기
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        friends[a].push_back(b);
        friends[b].push_back(a);
    }
    
// 2차원 백터안에서 for문을 돌면서 false가 나오면 그냥 끝내고 다음 i를 호출
  for (int i = 1; i <= n; ++i) {
        bool flag = true;
        for (int f : friends[i]) {
            if (weights[i] <= weights[f]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            count++;
        }
}

# 풀이 - vector<pair<int,int>>

if ((f.first == i && weights[i] <= weights[f.second]) || 
                (f.second == i && weights[i] <= weights[f.first])) {
                flag = false;
                break;
}

/*
친구관계에서 왼쪽 회원과 지금 i의 값이 같고 i가 치는 무게와 친구관계에서 오른쪽에 있는 회원이
무게를 많이 치거나 친구관계에서 오른쪽 회원과 i 값이 같고 i가 치는 무게와 친구관계에서 왼쪽에 있는
회원이 더 무게를 많이친다면, i 회원보다 잘난 사람이 있다는 것이다.
*/

 

관계식을 이렇게 세우긴 했지만 최악이다. pair로 해보고 싶어서 해보았는데 차라리 2차원 배열이 더 훨씬 코드도 그렇고 풀이하기도 깔끔했다.

 

이번 문제에서는 새롭게 배운 C++ 문법은 따로 없었다. 어려웠던건 역시나 그래프 문제이기 때문에 그런거 같다. 그냥 다 계산해보고 연산해보는 다익스트라의 문제인거 같다.... 또한, 하나라도 false일때 false로 내보내는것도 구현하는데 꽤 난이도가 있을거 같다고 생각된다.

 

무사히 3일차도 마쳤다. 이제 막 시작이지만 많은 200명되는 사람들이 코테 2주 챌린지를 하고 있는거 같다!! 다들 열심히 하는거 보니 나도 으쌰으쌰 해야겠다.