우테코 온보딩 - Problem 7

우테코 온보딩 - Problem 7 문제 풀이

문제 설명

레벨 2의 팀 프로젝트 미션으로 SNS(Social Networking Service)를 만들고자 하는 팀이 있다. 팀에 속한 크루 중 평소 알고리즘에 관심이 많은 미스터코는 친구 추천 알고리즘을 구현하고자 아래와 같은 규칙을 세웠다.

- 사용자와 함께 아는 친구의 수 = 10점 
- 사용자의 타임 라인에 방문한 횟수 = 1점

사용자 아이디 user와 친구 관계 정보 friends, 사용자 타임 라인 방문 기록 visitors가 매개변수로 주어질 때, 미스터코의 친구 추천 규칙에 따라 점수가 가장 높은 순으로 정렬하여 최대 5명을 return 하도록 solution 메서드를 완성하라. 이때 추천 점수가 0점인 경우 추천하지 않으며, 추천 점수가 같은 경우는 이름순으로 정렬한다.

제한사항
- user는 길이가 1 이상 30 이하인 문자열이다.
- friends는 길이가 1 이상 10,000 이하인 리스트/배열이다.
- friends의 각 원소는 길이가 2인 리스트/배열로 [아이디 A, 아이디 B] 순으로 들어있다.
  - A와 B는 친구라는 의미이다.
  - 아이디는 길이가 1 이상 30 이하인 문자열이다.
- visitors는 길이가 0 이상 10,000 이하인 리스트/배열이다.
- 사용자 아이디는 알파벳 소문자로만 이루어져 있다.
- 동일한 친구 관계가 중복해서 주어지지 않는다.
- 추천할 친구가 없는 경우는 주어지지 않는다.

 

문제의 자세한 내용은 해당 링크를 통해 확인 : 문제 링크

 

풀이 코드

package onboarding;

import java.util.*;
import java.util.stream.Collectors;

public class Problem7 {
    private static final Map<String, Integer> friendsPointMap = new HashMap<>();

    public static List<String> solution(String user, List<List<String>> friends, List<String> visitors) {
        List<String> answer = new ArrayList<>();

        friendsPoint(user, friends);
        visitorsPoint(visitors);

        List<String> keyList = new ArrayList<>(friendsPointMap.keySet());
        
        for (String s : friendsFilter(user, friends)) {
            keyList.remove(s);
        }
        
        keyList.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int com = friendsPointMap.get(o2).compareTo(friendsPointMap.get(o1));
                if(com == 0) {
                    return o1.compareTo(o2);
                } else {
                    return com;
                }
            }
        });

        answer = keyList.subList(0, Math.min(keyList.size(), 5));

        return answer;
    }

    private static List<String> friendsFilter(String user, List<List<String>> friends) {
        return friends.stream()
                .filter(o -> o.contains(user))
                .flatMap(Collection::stream)
                .filter(o -> !o.equals(user))
                .collect(Collectors.toList());
    }

    private static void friendsPoint(String user, List<List<String>> friends) {
        List<String> friendsList = friendsFilter(user, friends);
        List<List<String>> tempList = friends.stream().filter(o -> !o.contains(user)).collect(Collectors.toList());

        for (String s : friendsList) {
            tempList.stream()
                    .filter(o -> o.contains(s))
                    .flatMap(Collection::stream)
                    .forEach(o -> {
                        if(!o.equals(s)) {
                            friendsPointMap.put(o, friendsPointMap.getOrDefault(o, 0) + 10);
                        }
                    });
        }
    }

    private static void visitorsPoint(List<String> visitors) {
        for (String k : visitors) {
            friendsPointMap.put(k, friendsPointMap.getOrDefault(k, 0) + 1);
        }
    }
}

 

문제 해결 전략

이라 쓰고 문제를 보고서 어떻게 풀면 될까?에 대한 생각을 정리한 항목

해당 문제는 다 읽고 나서 친구의 친구에 대한 점수 배정 로직은 까다로워 보이니 간단해 보이는 방문자에 대한 점수 배정 로직부터 짜야겠다고 생각

그리고 각각의 로직이 수행하는 일이 정해져 있기에 메서드로 나누어 구현

클래스 변수로 Map을 하나 구현하여 유저(Key) 별로 점수(value)를 저장하여 관리 (friendsPointMap 변수)

방문자에 대한 점수 배정은 간단하게 향상된 for문을 사용하여 friendsPointMap에 기록

친구의 친구에 대한 점수 배정은 현재 친구의 리스트(friendsList)를 먼저 구한 뒤 향상된 for문을 순회하며 친구의 친구를 찾아서 friendsPointMap에 기록

이후 friendsPointMap의 Key에서 현재 친구인 경우는 제외시킨 후 제한사항에 맞춰 정렬(점수 기준 내림차순, 점수가 동일한 경우엔 이름 기준 내림차순 정렬)하여 앞에서 부터 5개의 요소를 뽑아서 반환하여 해결, 만약 Key의 사이즈가 5보다 작다면 Key의 사이즈 만큼 요소를 뽑아서 반환

---

코드를 업로드해 둔 깃 허브