[5643] [Professional] 키 순서

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo 

SW Expert Academy

 

문제 해결 방법

1. 학생마다 자신보다 큰, 작은 학생을 저장하는 HashSet을 가지며 입력을 받을 때 넣어준다.
2. 입력 후 compareHeight 함수로 '1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다.' 같은 경우를 처리해준다.
3. 마지막에 학생마다 각 HashSet의 크기를 더한 값이 N-1(자신을 뺀 나머지 학생수)와 같다면 조건을 만족하는 학생이다.

++플로이드-와샬 알고리즘 으로도 구현 가능

 

 

import java.util.*;

public class Solution {

    static class Student {
        int idx;
        HashSet<Integer> tallerThan;
        HashSet<Integer> shorterThan;

        public Student(int idx) {
            this.idx = idx;
            tallerThan = new HashSet<>();
            shorterThan = new HashSet<>();
        }
    }

    static int N, M;
    static ArrayList<Student> list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int t = 1; t <= T; t++) {
            N = sc.nextInt();
            M = sc.nextInt();
            list = new ArrayList<>();
            for (int i = 1; i <= N; i++) {
                list.add(new Student(i));
            }
            for (int i = 0; i < M; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                list.get(a - 1).shorterThan.add(b);
                list.get(b - 1).tallerThan.add(a);
            }

            compareHeight();

            int cnt = 0;
            for (Student student : list) {
                if (student.shorterThan.size() + student.tallerThan.size() == N - 1) cnt++;
            }
            System.out.println("#" + t + " " + cnt);
        }
    }

    private static void compareHeight() {
        for (Student student : list) {
            for (int s : student.shorterThan) {
                for (int t : student.tallerThan) {
                    list.get(s - 1).tallerThan.add(t);
                }
            }
            for (int t : student.tallerThan) {
                for (int s : student.shorterThan) {
                    list.get(t - 1).shorterThan.add(s);
                }
            }
        }
    }
}

import java.util.*;
 
// 플로이드-와샬
public class Solution {    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        int max = N * (N * (N - 1) / 2);
        
        int[][] student = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                student[i][j] = max; 
            }
        }
        
        for(int i = 0; i < M; i++) {
            int s1 = sc.nextInt();
            int s2 = sc.nextInt();
            student[s1 - 1][s2 - 1] = 1;
        }
        
        for(int k = 0; k < N; k++) {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    if(student[i][j] > student[i][k] + student[k][j]) {
                        student[i][j] = student[i][k] + student[k][j];
                    }
                }
            }
        }
        
        int result = 0;
        for(int i = 0; i < N; i++) {
            int count = 0;
            for(int j = 0; j < N; j++) {
                if(student[i][j] < max || student[j][i] < max) count++;
            }
            if(count == N - 1) result++;
        }
        
        System.out.println(result);
    }    
}