[소프티어] 우물 안 개구리(JAVA)

문제

https://softeer.ai/practice/6289

---

풀이(15분)

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[] weight = new int[n]; // 본인이 들 수 있는 최고 무게
        // 본인의 상태를 기록
        // 1 : 한번이라도 지거나 비긴 적이 있음
        // 2 : 아직까진 이기기만 한 상태
        // 0 : 단 한번도 누군가랑 겨룬 적이 없음
        int[] best = new int[n];


        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            weight[i] = Integer.parseInt(st.nextToken()); // 무게 입력
        }

        for(int i = 0; i < m; i++){ // 친분 관계 입력
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken()) - 1;
            int second = Integer.parseInt(st.nextToken()) - 1;
            if(weight[first] > weight[second]){ // first가 second보다 무겁게 들 수 있다면
                if(best[first] != 1){ // 1은 한번이라도 진 적이 있는 것
                    best[first] = 2; // 2는 승리
                }
                best[second] = 1; // 진 기록을 확인
            }
            if(weight[second] > weight[first]){ // first가 second보다 무겁게 들 수 있다면
                if(best[second] != 1){ // 1은 한번이라도 진 적이 있는 것
                    best[second] = 2; // 2는 승리
                }
                best[first] = 1; // 진 기록을 확인
            }
            if(weight[second] == weight[first]){ // first와 second가 동일한 무게를 든다면
                best[first] = 1; // 둘 다 패배로 기록
                best[second] = 1; // 둘 다 패배로 기록
            }
        }

        int count = 0;
        for(int i : best){
            if(i == 2 || i == 0){
                count++;
            }
        }
        System.out.println(count);
    }

}

---

문제 풀이 전략

 

문제의 조건을 분석하고, 메모리를 파악하자.

n = 10^5으로 매우 큰 상태이다. 그 때 연결 관계 파악을 위해 2차원 배열을 선언한다고 해도, 물론 가능하긴 하다. 하지만 꼭 해야할까 라는 생각이 들었다.

→ 각각의 사람마다 상태를 파악하는 int 배열을 1차원으로 선언했다.

친분 관계를 입력하는 즉시 상태를 설정한다.

1. 최초 상태는 모두 0으로 정의한다.
   1. 즉, 0은 아직 누구와도 겨루지 않았음을 나타낸다.
2. 입력이 들어온 두 명의 승부를 겨룬다.
   1. 이긴 사람은 2, 진 사람은 1로 한다.
      • 만약, 이겼다 해도 이미 1이었다면(이미 한번이라도 진 적이 있다면) 1을 유지한다.
   2. 비긴 경우 모두 1로 한다.
3. 최종적으로 2(이기기만 함) 또는 0(아무랑도 겨룬 적이 없음)을 찾는다.