우아한 테크코스 1주차 7번 - 정렬을 정리해보자!

HiroPark·2022년 10월 29일
0
public class Problem7 {
    public static List<String> solution(String user, List<List<String>> friends, List<String> visitors) {
        List<String> answer = new ArrayList<>();

        Map<String, Integer> scores = new HashMap<String, Integer>();
        Set<String> FriendWithUser = new HashSet<>(); // 유저의 친구 

/* 유저의 친구 set에 추가 */
        for (List<String> friend : friends) {
            if (friend.contains(user)) {
                FriendWithUser.add(friend.get(friend.indexOf(user) ^ 1));
            }
        }

/* 친구의 친구(지인) 점수 계산하여 HashMap에 넣음 */
        for (List<String> friend : friends) {
            for (String DirectFriend : FriendWithUser) {
                String acquaintance;
                if (friend.contains(DirectFriend) && (acquaintance = friend.get(friend.indexOf(DirectFriend) ^ 1)) != user && ! FriendWithUser.contains(acquaintance)) { 
                // 지인의 인덱스 값 구하기 위해XOR연산으로 0,1 뒤집음
                    scores.computeIfPresent(acquaintance, (k, v) -> v + 10);
                    scores.computeIfAbsent(acquaintance, v -> 10);
                }
            }
        }

/* 방문 점수 계산 */
        for (String visitor : visitors) {
            if (!(FriendWithUser.contains(visitor))) {
                scores.computeIfPresent(visitor, (k, v) -> v + 1);
                scores.computeIfAbsent(visitor, v -> 1);
            }
        }

        List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(scores.entrySet());
        Collections.sort(list, new ValueThenKeyComparator<String, Integer>());

/* 정렬된 list의 키값(이름) 들 answer에 넣어서 리턴 */ 
        for (Map.Entry<String, Integer> i : list) {
            answer.add(i.getKey());
        }
        
 /* list의 사이즈 제한 */
        if (answer.size() > 5) {
            answer = answer.subList(0,5);
        }

        return answer;
   }

    private static class ValueThenKeyComparator<K extends Comparable<? super K>, V extends Comparable<? super V>>
            implements Comparator<Map.Entry<K, V>> {

        public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
            int cmp1 = b.getValue().compareTo(a.getValue());
            if (cmp1 != 0) {
                return cmp1;
            } else {
                return a.getKey().compareTo(b.getKey());
            }
        }
    }
}

이 문제에서는 정렬하는 부분이 가장 어려웠습니다... 직접 Compartor를 구현하는 것이 처음이라 더욱 그랬습니다.

정렬 메커니즘을 간단하게 풀어보자면
1. HashMap의 entryset을 ArrayList에 넣는다
2. Collections.sort로 정렬을 하는데
3. 여기에 정렬기준 Comparator를 넘긴다.
4. Comparator(인터페이스)를 구현한 클래스는 원하는 정렬기준을 compare() 를 통해 구현한다

자바에서의 정렬은 아래와 같이 이루어진다

  • Comparable : 기본 정렬기준을 구현하는데 사용
  • Comparator : 기본 정렬기준 외의 다른 기준을 정렬하고자 할 때 사용

예를 들어 Integer class는 Comparable을 구현합니다다, 이 Comparable인터페이스는 CompareTo()를 메소드로 가지기에, Integer 클래스에서 이를 구현해주어야 하는 것입니다.

public final class Integer extends Number implements Comparable<Integer> {
.
.
.    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }

    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }

두 Integer 객체의 값을 비교해서, 같으면 0, 비교하는 값(anotherInteger)이 크면 -1, 본 값이 크면 1을 반환합니다.

만약 이것을 내림차순이나 ... 다른 기준으로 정렬하고 싶다면 Comparator 를 구현해주면 되는것입니다.

sort() 메서드에 Compartor 를 따로 지정해주지 않으면 객체의 Comparable에 구현된 내용에 따라 정렬되는 것입니다.

아무튼, 원래의 코드로 돌아와서, 제가 원하는 정렬 방식은
1. 점수 내림차순
2. 점수가 같으면 이름 오름차순
입니다

따라서

public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
            int cmp1 = b.getValue().compareTo(a.getValue());
            // b의 value가 더 크면 1, 같으면 0, a의 value가 더크면 -1
            if (cmp1 != 0) { 
                return cmp1;
            } else { // a와 b의 value 가 같아서 이름으로 비교, 이번엔 오름차순
                return a.getKey().compareTo(b.getKey());
            }
        }

이렇게 구현해줍니다.

근데 저

<K extends Comparable<? super K>, V extends Comparable<? super V>>

이 난해한 친구는 뭐였죠?? 분명 봤었는데 헷갈립니다. 마지막으로 이부분을 뜯어봅시다.

이거는 "지네릭스" 라고, 다룰 객체의 타입을 미리 명시해주어서 번거로운 타입체크와 형 변환을 줄여주는 아이입니다.

이 안에는 타입 매개변수나 ( < T > <K,V> .. 이렇게) , 특정 타입 자체를 지정해 줄 수 있습니다

이 제네릭 타입 매개변수에 지정 될 수 있는 타입의 종류를 제한해 줄 수 있습니다.

이때 "와일드 카드 : ? " 라는 것을 사용하는데,
이렇게 사용합니다

  • < ? extends T > : T와 T를 상속받은 자손만 가능(상한 제한)
  • < ? super T > : T와 T의 조상들만 가능 (하한 제한)
  • < ? > : 제한 없음. <? extends Object> 와 동일

여기까지 보고 다시 코드로 돌아가봅시다.
이 제네릭을 여러개 겹쳐놨더니 헷갈리는 것입니다.

  • ValueThenKeyComparator의 K,V는 Comparable을 구현한 클래스이어야 하며
    K extends Comparable

이때, 인터페이스라고 하여도 implements가 아닌 extends로 표현합니다.

  • 이 Comparable은 K또는 그것의 조상의 타입을 비교하는 Comparable이어야 합니다.
    Comparable<? super K>

만약 K가 Person의 자손인 Student이면 <? super K> 는 Student, Person, Object 모두 가능합니다.

profile
https://de-vlog.tistory.com/ 이사중입니다

1개의 댓글

comment-user-thumbnail
2022년 11월 30일

추카

답글 달기