[STUDY] Class 4

joy0987·2023년 8월 21일

목록 보기

3/4

문제

🚀 기능 요구 사항

레벨 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 이하인 리스트/배열이다.
사용자 아이디는 알파벳 소문자로만 이루어져 있다.
동일한 친구 관계가 중복해서 주어지지 않는다.
추천할 친구가 없는 경우는 주어지지 않는다.

실행 결과 예시

user	friends	visitors	result
"mrko"	[["donut", "andole"], ["donut", "jun"], ["donut", "mrko"], ["shakevan", "andole"], ["shakevan", "jun"], ["shakevan", "mrko"]]	["bedi", "bedi", "donut", "bedi", "shakevan"]	["andole", "jun", "bedi"]

구현 전 고려한 내용

'추천할 친구가 없는 경우는 주어지지 않는다.', 'visitors는 길이가 0 이상 10,000 이하인 리스트/배열이다.' 는 제한사항
- ✅ 친구 목록은 반드시 값이 주어져야 한다.
- ✅ 방문자 목록은 값이 주어지지 않아도 된다.
  - ➡ visitors가 주어지지 않는 경우 visitors에 대한 메서드는 실행하지 않아야한다.
  - ➡ 친구 목록이 주어지지 않는 경우 예외처리를 해야한다.
동일한 친구 관계가 중복해서 주어지지 않는다.
- ✅ 친구목록에 데이터 추가시 중복 검사(이미 있는 친구인지) 진행 X
User 는 friends 와 visitors 라는 이름의 User 타입 큐를 가지고 있을 것이다.
- 인덱스 순서대로 접근할 필요성이 없기에 리스트가 아닌 큐로 구현
직관적으로 알아보기 힘든 원시값은 모두 포장하기
일급콜렉션을 적극 사용하여 필요한 로직 및 검증은 해당 클래스 안에 넣는다.

로직

User, Friends, Visitors 를 문자열로 입력받는다.
현재 사용자인 User 를 생성하고, UserList 에 추가한다.
문자열을 파싱한다.
- 친구리스트는 문자열 이차원 배열로 만든다.
- 방문자리스트는 문자열 배열로 만든다.
예외 검사를 진행한다.
방문자리스트를 반복문으로 돌면서 현재 사용자의 방문자리스트 필드에 값을 추가한다.
- 유저리스트에 존재하지 않는다면 새로 유저 객체를 생성해서 유저리스트 및 방문자리스트에 추가한다.
- 유저리스트에 이미 존재한다면 해당 유저 객체를 사용자의 방문자리스트에 추가한다.
친구리스트를 반복문으로 돌면서 서로 친구추가를 진행한다.
- 유저리스트에 존재하지 않는다면 새로 유저 객체를 생성해서 유저리스트 및 상대 유저의 친구리스트 필드에 추가한다.
- 유저리스트에 이미 존재한다면 해당 유저 객체를 상대 유저의 친구리스트 필드에 추가한다.
유저리스트를 반복문으로 돌면서 사용자를 제외한 각 유저들의 포인트를 추가한다.
- 유저마다 포인트가 부여되므로, Map 자료구조가 맞다고 생각했습니다.
- 함께 아는 친구
  - 사용자의 친구목록과 타 유저의 친구목록을 비교하여 친구가 일치하는 경우 포인트를 부여한다.
- 0 포인트인 유저는 목록에서 제외
- 사용자 본인도 목록에서 제외
결과 출력

구현 과정 및 피드백 내용

main 에서 solution 메서드를 실행한다.

public class Main {
    public static void main(String[] args) {
        new Controller().solution();
    }
}

solution 메서드에서는 순서대로 로직을 실행한다.

public void solution() {

        // 정보 입력받기
        String userName = inputInfo(INPUT_USER_NAME);
        String inputFriends = inputInfo(INPUT_FRIENDS_LIST);
        String inputVisitors = inputInfo(INPUT_VISITORS_LIST);

        // 사용자, 유저 리스트 생성
        User user = users.findOrCreateUser(userName);
        users.addUser(user);

        // 방문자 목록이 주어졌다면, 방문자목록 파싱 및 유저의 방문자목록에 추가
        if (inputVisitors != null && inputVisitors.length() != 0) {
            String[] visitors = parser.visitorsParsing(inputVisitors);
            users.addVisitorsToUser(user, visitors);
        }

        // 친구 목록 파싱해서 이차원배열로 만들기
        String[][] friends = parser.friendsParsing(inputFriends);

        // 아이디 A의 친구목록에 아이디 B 추가, 아이디 B의 친구목록에 아이디 A 추가
        users.addFriends(friends);

        // 추천친구 5명 선정 및 출력
        List<User> top5User = pointManager.recommendFriends(user, users);
        if (top5User == null) {
            output.message("❌ 추천할 친구가 없습니다.");
            return;
        }
        output.result(top5User);
        
    }

유저 이름의 길이와 포맷 검증
유저의 친구 목록에 친구를 추가하는 기능
유저의 방문자 목록에 방문자 유저를 추가하는 기능

이 같은 검증과 기능 로직은 User 클래스에 넣었다.
2, 3은 일급컬렉션인 Friends 와 Visitors 클래스 내부에서 실질적인 데이터 변경이 이루어진다.

User.java

public class User {

    private final String name;
    private final Friends friends;
    private final Visitors visitors;

    public User(String name, Queue<User> friends, Queue<User> visitors) {
        validateUserNameLength(name);
        validateUserNameFormat(name);
        this.name = name;
        this.friends = new Friends(friends);
        this.visitors = new Visitors(visitors);
    }

    public String getName() {
        return name;
    }

    public Queue<User> getFriends() {
        return friends.friends();
    }

    public Queue<User> getVisitors() {
        return visitors.visitors();
    }

    private void validateUserNameLength(String userName) {
        if (userName == null || userName.length() > USER_NAME_MAX_LENGTH) {
            throw new IllegalArgumentException("사용자 이름은 1자 이상 30자 이하여야 합니다.");
        }
    }

    private void validateUserNameFormat(String userName) {
        for (int i = 0; i < userName.length(); i++) {
            if (userName.charAt(i) < LOWERCASE_A || userName.charAt(i) > LOWERCASE_Z) {
                throw new IllegalArgumentException("사용자 이름은 소문자 영어로 이루어져야합니다.");
            }
        }
    }

    public void addFriend(User user) {
        friends.addFriend(user);
    }

    public void addVisitor(User user) {
        visitors.addVisitor(user);
    }


}

Friends.java

public record Friends(Queue<User> friends) {

    public Friends {
        validateSize(friends);
    }

    @Override
    public Queue<User> friends() {
        return new LinkedList<>(friends);
    }

    private void validateSize(Queue<User> friends) {
        if (friends.size() == 0) return;
        if (friends.size() > MAX) {
            throw new IllegalArgumentException("친구 목록은 1명 이상 10000명 이하여야 합니다.");
        }
    }

    public void addFriend(User user) {
        friends.add(user);
    }
}

Visitors.java

public record Visitors(Queue<User> visitors) {

    public Visitors {
        validateSize(visitors);
    }

    @Override
    public Queue<User> visitors() {
        return new LinkedList<>(visitors);
    }

    private void validateSize(Queue<User> visitors) {
        if (visitors.size() == 0) return;
        if (visitors.size() > MAX) {
            throw new IllegalArgumentException("방문자 목록은 0명 이상 10000명 이하여야 합니다.");
        }
    }

    public void addVisitor(User user) {
        visitors.add(user);
    }
}

Controller 에서는 UserList 라는 유저 리스트를 관리하는 일급컬렉션이 있다.
private 를 통해 UserList 를 다른 데에서 수정하지 못하도록 막았고, 오직 Controller 에서만 UserList 를 관리할 수 있다.

UserList 에서는 현재 존재하는(입력받은) 유저들을 반복문으로 돌면서 사용자에게 입력받은대로 방문자를 추가하고, 각 유저들의 친구 목록에 친구를 추가하는 역할을 수행한다.

// Controller 의 UserList

private final UserList users;

// UserList 클래스 내부의 컬렉션

private final List<User> users;

유저리스트를 관리하는 게 조금 어려웠는데, 유저리스트에 이미 이름이 같은 유저가 존재하는 경우에는 해당 유저를 반환하고, 존재하지 않는 경우에는 새로 유저를 생성하고 유저리스트에 추가하는 방법을 선택했다.

// 유저를 반환하는 기능

 public User findOrCreateUser(String usersName) {
        for (User user : users) {
            if (user.getName().equals(usersName)) {
                return user;
            }
        }
        User newUser = new User(usersName, new LinkedList<>(), new LinkedList<>());
        users.add(newUser);
        return newUser;
    }
    
// 위를 기반으로, 친구를 추가하는 기능

public void addFriends(String[][] friends) {
        for (String[] friend : friends) {
            User userA = findOrCreateUser(friend[0]);
            User userB = findOrCreateUser(friend[1]);
            userA.addFriend(userB);
            userB.addFriend(userA);
        }
    }

친구 및 방문자를 추가하는 기능은 모두 구현되었고, 이제 포인트를 부여하는 기능을 구현하면 되었다.
서비스에서 하는 것 보다는 일급컬렉션을 통해 포인트가 함부로 수정되는 것을 막고 가독성을 향상시키는 구현 방법을 택했다.

각 유저에게 포인트를 부여하는 것이므로, Map 자료구조가 맞다고 생각했다.

Point.java

public class Point {
    private Map<User, Integer> point;

    public Point() {
        this.point = new HashMap<>();
    }

    public List<User> getTopUsersByPoint(User user, UserList users) {
        addPointByFriend(user, users);
        addPointByVisitor(user);

        List<User> topUsersByPoint = removeZeroPointUser();

        // 내림차순 정렬
        if (point.size() != 0) {
            Collections.sort(topUsersByPoint, (v1, v2) -> (point.get(v2).compareTo(point.get(v1))));
        }
        return topUsersByPoint;
    }
    
    private List<User> removeZeroPointUser() {
        List<User> users = new ArrayList<>(point.keySet());
        for (User user : users) {
            if (point.get(user) == 0) {
                users.remove(user);
            }
        }
        return users;
    }

    private void addPointByFriend(User user, UserList users) {
        for (User userFriend : user.getFriends()) {
            for (User otherUser : users.getUsers()) {
                if (otherUser == user) continue;
                if (otherUser.getFriends().contains(userFriend)) {
                    point.put(otherUser, point.getOrDefault(user, 0) + POINT_UP_BY_FRIEND);
                }
            }
        }
    }

    private void addPointByVisitor(User user) {
        for (User visitor : user.getVisitors()) {
            point.put(visitor, point.getOrDefault(visitor, 0) + POINT_UP_BY_VISITOR);
        }
    }
}

주 기능을 모두 구현했으니, 이제 서비스에서 순서대로 실행만 하면 되었다.

RecommendFriendService 를 만들어서

친구 추천
추천 리스트에서 본인 삭제
추천 리스트에서 이미 아는 친구 삭제

를 수행하는 메서드를 만들었다.

RecommendFriendService.java

public class RecommendFriendService {

    private Point point;

    public RecommendFriendService() {
        point = new Point();
    }

    public List<User> recommendFriends(User user, UserList users) {
        List<User> recommendationList = point.getTopUsersByPoint(user, users);

        recommendationList = removeMe(user, recommendationList);
        recommendationList = removeKnownFriend(user, recommendationList);

        if (recommendationList.size() > RECOMMEND_LENGTH_MAX) {
            recommendationList = recommendationList.subList(0, RECOMMEND_LENGTH_MAX);
        }
        return recommendationList;
    }

    private List<User> removeMe(User me, List<User> recommendationList) {
        for (User user : recommendationList) {
            if (user.getName().equals(me.getName())) {
                recommendationList.remove(me);
            }
        }
        return recommendationList;
    }

    private List<User> removeKnownFriend(User me, List<User> recommendationList) {
        for (User recommendationFriend : recommendationList) {
            for (User knownFriend : me.getFriends()) {
                if (recommendationFriend.getName().equals(knownFriend.getName())) {
                    recommendationList.remove(recommendationFriend);
                }
            }
        }
        return recommendationList;
    }

}