[소프티어/자바] lv3. 우물안 개구리

📍문제

https://softeer.ai/practice/6289

헬스장에서 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

5 3
1 2 3 4 5
1 3
2 4
2 5

출력예제1

3

입력예제2

5 3
7 5 7 7 1
1 2
2 3
3 4

출력예제2

2

📍틀린 정답

JAVA
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      
      st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      int[] weights = new int[N+1];

      st = new StringTokenizer(br.readLine(), " ");
      for(int i=1; i<=N; i++) weights[i] = Integer.parseInt(st.nextToken());

      //친분관계 만들기
      int[][] map = new int[N+1][N+1];
      for(int i=0; i<M; i++) {
        st = new StringTokenizer(br.readLine());
        int p1 = Integer.parseInt(st.nextToken());
        int p2 = Integer.parseInt(st.nextToken());
        map[p1][p2] = 1;
        map[p1][p2] = 1;
      }

      int result = 0;
      for(int i=1; i<=N; i++) {
        boolean flag = true;
        for(int j=1; j<=N; j++) {
          if(i==j) continue; //자기 자신이면 넘김

          if(map[i][j] == 1) {
            if(weights[i] <= weights[j]) {
              flag = false;
              break;
            }
          }
        }
        if(flag) result++;
      }
      System.out.println(result);
    }
}

• 시간복잡도 생각하자

맨 처음에 시간 복잡도 없이 풀었더니 시간초과에 걸려서 틀린 것으로 예상된다. 전체탐색으로 풀어서 N 의 범위가 n^5 인데, break 를 걸어준다 한 들, 이중 for문으로 인해 범위가 넘어가는 것으로 보인다. 그래서 이차원 배열을 사용해서 전체탐색을 하는 방법을 ArrayList<ArrayList<Integer>> list 를 이용해서 연결되어 있는 경우에만 탐색하도록 접근했다.

📍맞춘 정답

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      
      st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      int[] weights = new int[N+1];

      st = new StringTokenizer(br.readLine(), " ");
      for(int i=1; i<=N; i++) weights[i] = Integer.parseInt(st.nextToken());
      
      //친분관계 만들기
      ArrayList<ArrayList<Integer>> list = new ArrayList<>();
      for(int i=0; i<=N; i++) list.add(new ArrayList<>());
      
      for(int i=0; i<M; i++) {
        st = new StringTokenizer(br.readLine());
        int p1 = Integer.parseInt(st.nextToken());
        int p2 = Integer.parseInt(st.nextToken());
        list.get(p1).add(p2);
        list.get(p2).add(p1);
      }

      int result = 0;
      for(int i=1; i<=N; i++) {
        boolean flag = true;
        for(int j=0; j<list.get(i).size(); j++){
          int friend = list.get(i).get(j);
          if(weights[i] <= weights[friend]) {
            flag = false;
            break;
          }
        }
        if(flag) result++;
      }      
      System.out.println(result);
    }
}