[우아한테크코스 5기] 프리코스 1주차 온보딩 후기

 

프리코스 1주차 미션 링크

https://github.com/woowacourse-precourse/java-onboarding

 

제가 제출한 코드 링크

https://github.com/70825/java-onboarding/tree/70825

 

이번 프리코스는 1차 코딩테스트가 없는 대신 프리코스를 4주동안 진행될 예정이라고 합니다.

그래서 숫자 야구 게임, 자동차 경주 게임 같은 미션을 4주동안 하는 줄 알았는데, 코딩테스트 문제를 프리코스 1주차로 진행하였습니다.

사실상 시간 제한이 없는 알고리즘 문제 해결이긴한데, 우아한테크코스 프리코스는 객체지향 설계 능력을 키우는 것이 주 목적이니까 백준이랑 프로그래머스에서 푸는 방식과 조금 다른 방향으로 코드를 작성하였습니다.

 

어디서 굉장히 많이 본 예제 형식

저는 자바로 알고리즘 문제를 풀어본 적이 없기 때문에 자바 명령어와 기능 분리에 익숙해질겸 기능별로 메서드를 만들었습니다.

 

나의 목표

• 자바 사용법에 적응하기
• 자바 8에 추가된 기능 사용해보기
• 자바 코드 컨벤션 지키기
• 기능 단위로 메소드를 분리하기
• 기능 단위로 커밋을 보내기
• 정규표현식 사용해보기
• 문제를 해결할 때 필요한 중요 상수를 private static final로 저장하기

 

 

1. 문제 1

---

[Validator 만들기]

미션 진행 방식에서 기능 요구 사항에 기재되지 않은 내용은 스스로 판단하여 구현하라는 내용이 나와있습니다.

올바른 입력값이 들어오는지 확인하는 것은 스스로 판단해야하는 케이스가 많았으며 저는 6가지의 조건을 확인했습니다.

• List<Integer>에 들어있는 원소의 개수는 2개인가?
• 왼쪽 페이지는 홀수인가?
• 오른쪽 페이지는 짝수인가?
• 왼쪽 페이지와 오른쪽 페이지는 연속하는 수인가?
• 왼쪽 페이지는 1페이지 ~ 400페이지중에 하나인가?
• 오른쪽 페이지는 1페이지 ~ 400페이지중에 하나인가?

 

그래서 위의 조건중에 하나라도 통과를 하지 못하면 false를 반환하고, 반대로 위의 조건을 모두 통과한다면 true를 반환하도록 하였습니다.

---

[문제 요구사항 기능 구현]

하나의 메소드가 최대한 하나의 기능을 맡을 수 있도록 분리하였고, 그 결과 메소드가 solution 포함 9개가 나왔습니다....😮

validator도 여러가지로 나눈다면 메소드가 15개 이상은 나올 것 같아서 하지 않았네요.

---

[stream, reduce 사용해보기]

올해 진행하고 있는 우아한테크코스 4기 분들의 블로그를 보니까 stream과 reduce에 대한 언급이 심심치 않게 나왔습니다. 그래서 프리코스가 시작되기 하루 전에 어떤 메소드가 있는지 확인해보고, 기능에 익숙해질겸 백준에서 문제를 풀어보았습니다.

stream과 reduce가 어디에서 대충 사용하는지 아니까 1번 문제에서 적용 가능한 것이 보였습니다.

 

- 리스트에 있는 모든 값 더해주기

Integer result = [List 변수명].stream().reduce(0, Integer::sum);

 

- 리스트에 있는 모든 값 곱해주기

Integer result = [List 변수명].stream().reduce(1, (a, b) -> a * b);

 

 

---

 

 

 

문제 2

---

문제 2의 경우에는 예외사항에 대한 언급이 전혀 없습니다. 그래서 만들지 않아도 상관이 없긴한데, 정규표현식을 사용해보고 싶어서 적용했습니다. 저는 예외가 발생하면 "-1"을 출력하도록 했습니다.

그래서 Validation은 만들었긴한데, 괜히 제가 실수로 validation을 잘못 만들어서 틀린 답이 나올 수도 있을 수도 있을 것 같아서 나중에 삭제했습니다.

 

이 문제는 정규표현식을 적용하여 간단한 코드가 나올 수 있도록 리팩토링을 진행하였습니다. 마지막 내용을 제외하면 다 삭제된 코드입니다.

---

[정규표현식을 사용한 Validation 만들기]

• cryptogram은 길이가 1 이상 1000 이하인 문자열이다.
• cryptogram은 알파벳 소문자로만 이루어져 있다.

여기서 알파벳 소문자로 이루어져 있다는 것은 그냥 반복문 + 아스키코드를 사용하여 빠르게 구할 수 있지만, 정규표현식도 사용해볼 수 있습니다.

 

?	문자열의 시작을 의미한다.
[a-z]	알파벳 소문자의 집합을 의미한다.
+	+ 이전에 오는 문자가 1번 이상 반복된다.
$	문자열의 끝을 의미한다.

 

String str = "확인하고 싶은 문자열";
String pattern = "?[a-z]+$";
boolean result = Pattern.matches(pattern, str);

정규표현식을 적용하면 pattern은 알파벳 소문자가 1번 이상 반복되는 문자열이 맞는지 확인하는 것입니다.

---

[코드 수정 전 - 연속된 중복 문자 확인하기]

연속된 중복 문자의 경우 처음에 한 개만 발견해도 문장에 존재하는 전체적인 중복 문자를 삭제할 생각으로 만들었습니다.

 private static boolean checkDuplicateString(String inputString) {
        for(int i = 0; i < inputString.length() - 1; i++) {
            if (inputString.charAt(i) == inputString.charAt(i+1)) {
                return true;
            }
        }
        return false;
    }

 

이후엔 더 짧은 방법이 없을까하다가 reduce와 삼항연산자를 사용해서 아래 내용으로 바꾸어보았습니다.

코드 컨벤션에서는 삼항 연산자를 사용하지 말라고 했는데, 아직 객체지향으로 설계하는 프리코스는 아니라서 처음이자 마지막으로 사용해봤습니다.

private static boolean checkDuplicateString(String inputString) {
    IntStream inputIntStream = inputString.chars();
    int result = inputIntStream
             .reduce(0, (a, b) -> a == FIND_DUPLICATION ? a : (a == b) ? FIND_DUPLICATION : b);

    return result == -1;
}

코드는 만약 연속하는 중복 문자가 있으면 result는 FIND_DUPLICATION 값을 계속 가지게 됩니다. 하지만 만약 이전까지 연속하는 중복문자가 없다면 마지막 문자의 아스키코드를 가지고 있는 로직입니다.

---

[최종 코드 - 정규표현식을 적용하여 중복된 글자 삭제하기]

private static final String REGEX_FIND_DUPLICATION = "([a-z])\\1+";

public static String solution(String cryptogram) {
    String answer = "answer";
    Pattern pattern = Pattern.compile(REGEX_FIND_DUPLICATION);
    Matcher matcher = pattern.matcher(cryptogram);

    while(matcher.find()) {
        cryptogram = matcher.replaceAll("");
        matcher = pattern.matcher(cryptogram);
    }

    answer = cryptogram;

    return answer;
}

마지막에 정규표현식을 사용하여 코드 리팩토링을 진행하였습니다.

정규표현식에서 C++의 포인터와 비슷한 역참조(backreferences) 기능을 사용하여 연속으로 중복된 알파벳을 찾을 수 있도록 합니다.

• ( 내용 ) : 정규표현식에서는 괄호로 감싸져 있으면 하나의 그룹으로 판단합니다.
• \숫자 : 역참조 기능으로 숫자에 해당하는 그룹의 결과 값을 그대로 참조한다고 생각하면 됩니다.
• + : 1개 이상이 나와야 합니다.

내용을 정리해보면 ([a-z])\1+은 첫번째 그룹에서 같은 알파벳 소문자가 연속적으로 2개 이상 나오는 것을 찾는 정규표현식입니다.

ex) abcccbbazaixyyyy → abcccbbazaixyyyy, browoanoommnaon → browoanoommnaon 

저도 처음에 역참조라는 기능이 잘 이해가 안갔는데, 아래 과정을 이해하면 좀 더 이해하기 수월할 것 같습니다.

 

browoanoommnaon

[0] b → ([a-z])\1+ → bb+ → false
[1] r → ([a-z])\1+ → rr+ → false
[2] o → ([a-z])\1+ → oo+ → false
[3] w → ([a-z])\1+ → ww+ → false
[4] o → ([a-z])\1+ → oo+ → false
[5] a → ([a-z])\1+ → aa+ → false
[6] n → ([a-z])\1+ → nn+ → false
[7] o → ([a-z])\1+ → oo+ → true
[8] o → ([a-z])\1+ → oo+ → false
[9] m → ([a-z])\1+ → mm+ → true
[10] m → ([a-z])\1+ → mm+ → false
[11] n → ([a-z])\1+ → nn+ → false
[12] a → ([a-z])\1+ → aa+ → false
[13] o → ([a-z])\1+ → oo+ → false
[14] n → ([a-z])\1+ → nn+ → false

이렇게 중복된 글자를 찾은 후에 matcher.replaceAll("")을 통해 찾은 중복된 글자를 전부 삭제해줍니다.

이 과정을 반복하여 더 이상 삭제할 중복 알파벳이 없는 경우 answer에 저장할 수 있도록 합니다.

 

굉장히 깔끔한 코드가 나왔네요.

---

 

 

 

문제 3

---

3, 6, 9에서 1부터 number까지 박수를 치는 횟수는 범위가 작아서 단순 for문으로도 충분히 가능해서 바로 풀고 넘어갔습니다.

---

 

 

 

문제 4

---

[문자 변환하기]

아래 내용을 배열로 선언해서 풀어도 되긴 합니다.

A - Z, B - Y, C - X, D - W, E - V, F - U, G - T, H - S, I - R, ....

 

그런데 이걸 숫자로 변환해서 확인해보면 특정 규칙이 보이게 됩니다.

1 - 26, 2 - 25, 3 - 24, 4 - 23, 5 - 22, 6 - 21, ...

 

둘의 합은 27이고, 27 - (알파벳의 번호) = (나머지 알파벳의 번호)가 나오게 됩니다.

그래서 이것을 토대로 메소드를 대문자, 소문자 각각 하나씩 만들었습니다.

    public static char convertUppercase(int intValue) {
        char result = (char) ('Z' - intValue + 'A');

        return result;
    }

    public static char convertLowercase(int intValue) {
        char result = (char) ('z' - intValue + 'a');

        return result;
    }

---

[문자들을 문자열로 만들기]

저는 문자를 변환한 뒤 ArrayList에 하나씩 넣어줬습니다. 이후 stream을 사용하여 문자들을 문자열로 바꿨습니다.

ArrayList.stream()
	.map(String::valueOf)
	.collect(Collectors.joining());

---

 

 

 

문제 5

---

돈을 50000원, 10000원, 5000원, 1000원, 500원, 100원, 50원, 10원, 1원 순으로 돈을 환전해서 얻을 수 있는 지폐/동전의 수를 출력하라고 합니다.

 

(처음) 기능 분리를 해야하니까 각 지폐/동전마다 메소드를 새로 만들까?

↓

(코드 작성 도중) 메소드가 너무 많아지니까 파라미터에 환전할 금액을 넣어 메소드를 재사용하자

↓

(마지막) 비슷한 코드 묶음이 8개나 나오니까 원래 문제 풀던대로 환전하는 금액을 배열에 저장해두고, for문을 사용하자.

 

이런 생각 순서대로 코드를 구현하고 수정했습니다.

---

 

 

 

문제 6

---

크루의 수는 최대 10,000명, 닉네임은 최대 19글자라서 시간복잡도 계산을 해봐야 합니다.

한 크루에게 얻을 수 있는 연속된 두 글자 단어는 18개니까 N = 10,000 * 18개의 단어를 확인해야 했습니다.

단순 for문으로 문제를 해결하려고 하면 4중 for문이 나올텐데 O(N^2)이므로 약 324초 정도가 걸리는 연산량이 나옵니다. 그래서 최소 O(NlogN)의 풀이가 필요합니다.

---

[HashMap? TreeMap?]

인터넷 블로그 글을 보면 HashMap의 get() 시간 복잡도가 아무런 설명없이 O(1)이라는 글이 많이 나옵니다.

HashMap은 이름 그대로 해시를 사용하기 때문에 평균적으로 O(1)의 시간이 걸립니다. 하지만 해시 테이블을 저격하는 데이터만 잘 만든다면 입력값을 넣을 때마다 계속 충돌을 일으켜서 O(1)을 O(N)이 걸리게하는 마법을 보여줄 수도 있습니다.

그래서 HashMap을 사용해서 문제를 풀게 된다면 O(N)으로 문제를 풀 수도 있지만, 정말 운이 나쁘다면 O(N^2)의 시간으로 문제를 풀 수도 있게 됩니다.

반대로 TreeMap의 경우엔 레드블랙트리 자료구조를 사용하여 O(logN)이 보장되어 있습니다. 그래서 문제를 풀게 된다면 O(NlogN)을 보장하기 때문에 저는 TreeMap을 사용하였습니다.

---

[TreeSet 사용]

저는 Map에서 key를 두 글자 단어로, value를 해당 단어가 나온 횟수로 해서 단어가 나온 횟수가 2 이상이면 정답에 넣어주려고 했습니다. 그런데 테스트 케이스를 제작하던 중에 틀렸다는 것을 알았습니다.

@Test
void case2() {
    List<List<String>> forms = List.of(
            List.of("jm@email.com", "제이이이이이이엠"),
            List.of("jason@email.com", "제이이이이슨"),
            List.of("woniee@email.com", "워워워워니"),
            List.of("mj@email.com", "엠제이이"),
            List.of("nowm@email.com", "이제엠")
    );
    List<String> result = List.of("jason@email.com", "jm@email.com", "mj@email.com");
    assertThat(Problem6.solution(forms)).isEqualTo(result);
}

이 테스트 케이스를 확인해보면 같은 이메일이 여러 개가 들어가는 것입니다.

그래서 중복을 제거하는 자료구조인 Set을 사용하여 한 닉네임에 반복되는 연속된 글자가 있으면 답을 넣을 때 중복으로 들어가지 않도록 하였습니다.

---

 

 

 

문제 7

---

메소드 분리를 하다가 코드가 많이 길어진 문제입니다.

public static List<String> solution(String user, List<List<String>> friends, List<String> visitors) {
        List<String> answer = Collections.emptyList();

        List<String> friendOfUser = getFriendOfUser(user, friends);
        List<String> friendOfFriend = getFriendOfFriend(user, friends);

        Map<String, Integer> scoreRecommendFriend = getScoreRecommendFriend(friendOfFriend, visitors);
        Map<String, Integer> refineScoreRecommendFriend
                = getRefineScoreRecommendFriend(scoreRecommendFriend, friendOfUser);

        List<String> sortedRecommendFriend = getSortedRecommendFriend(refineScoreRecommendFriend);
        List<String> fiveRecommendFriend = getFiveRecommendFriend(sortedRecommendFriend);
        answer = fiveRecommendFriend;

        return answer;
    }

클린코드에 대해서 검색해보니까 변수 이름이 길어도 의미만 부여된다면 괜찮다고해서 최대한 변수 이름만 보고 유추할 수 있도록 만들었는데... 이게 맞는지 모르겠네요.

refineScoreRecommendFriend가 있는 줄도 코드 컨벤션에서 120자를 넘기면 줄바꿈을 하라고 해서 바꿨습니다.

---

[사용자의 친구 구하기]

이 부분은 나중에 점수 계산할 때, 사용자의 친구가 들어가는 경우가 있어서 만들어주었습니다.

    public static List<String> getFriendOfUser(String user, List<List<String>> friends) {
        List<String> result = new ArrayList<>();

        friends.forEach(friend -> {
            if (friend.get(0).equals(user)) {
                result.add(friend.get(1));
            }

            if (friend.get(1).equals(user)) {
                result.add(friend.get(0));
            }
        });

        return result;
    }

코드의 가독성을 고려한다면 위 코드보다 시간이 느리지만 아래 코드로 수정할 수 있습니다.

public static List<String> getFriendOfUser(String user, List<List<String>> friends) {
    List<String> result = new ArrayList<>();

    friends.stream()
            .filter(friend -> friend.get(0).equals(user))
            .forEach(friend -> result.add(friend.get(1)));

    friends.stream()
            .filter(friend -> friend.get(1).equals(user))
            .forEach(friend -> result.add(friend.get(0)));

    return result;
}

 

---

[사용자의 친구의 친구 구하기]

이 부분은 제가 위에서 사용자의 친구를 구했으니 다양한 방법으로 친구의 친구를 구할 수도 있습니다.

저는 BFS를 사용해서 사용자의 친구의 친구를 구했습니다. 이때 방문 처리는 friendVisited를 사용하고, 사용자와 유저와의 거리는 friendLevel을 사용했습니다.

그리고 인접리스트를 만드는 것은 getAdjacencyList 메소드를 만들어서 최대한 깔끔하게 보이도록 했습니다.

    private static Map<String, Integer> getFriendOfFriend(String user, List<List<String>> friends) {
        Map<String, List<String>> adjacencyList = getAdjacencyList(friends);
        Map<String, Integer> friendVisited = new TreeMap<>();
        Map<String, Integer> friendLevel = new TreeMap<>();
        Queue<String> friendQueue = new LinkedList<>();
        List<String> twoLevelFriend;
        Map<String, Integer> resultFriendOfFriend = new TreeMap<>();

        adjacencyList.putIfAbsent(user, new ArrayList<>());
        friendQueue.add(user);
        friendVisited.put(user, 1);
        friendLevel.put(user, 0);

        while(!friendQueue.isEmpty()) {
            String person = friendQueue.poll();

            for(String friend : adjacencyList.get(person)) {
                if (friendLevel.getOrDefault(person, 0) == 1
                        && friendLevel.getOrDefault(friend, 0) == 2) {
                    friendVisited.put(friend, friendVisited.get(friend) + 1);
                    continue;
                }

                if (friendVisited.getOrDefault(friend, 0) == 0) {
                    friendVisited.put(friend, 1);
                    friendLevel.put(friend, friendLevel.get(person) + 1);
                    friendQueue.add(friend);
                }
            }
        }

        twoLevelFriend = friendLevel.keySet().stream()
                .filter(friend -> friendLevel.get(friend) == 2)
                .collect(Collectors.toList());

        twoLevelFriend.forEach(friend -> {
            resultFriendOfFriend.put(friend, friendVisited.get(friend));
        });

        return resultFriendOfFriend;
}

 

일반적인 BFS에다가 사용자의 친구가 사용자의 친구의 친구를 방문하려고 할 경우 friendVistied의 값을 올려주었습니다. 이 값을 통해서 (사용자와 함께하는 친구의 수) * 10만큼의 점수를 구할 수 있습니다.

resultTwoLevelFriend = friendLevel.keySet().stream()
    .filter(friend -> friendLevel.get(friend) == 2)
    .collect(Collectors.toList());

이후 사용자의 친구의 친구를 구할 때에는 stream, filter를 사용하여 만들었습니다.

6번까지 문제를 풀었을 때에는 filter를 적용할만한 코드가 없었는데, 다행히도 이 문제에서 사용할 수 있게 되었네요.

---

[사용자의 친구의 친구 구하기 - 인접 리스트 만들기]

    private static Map<String, List<String>> getAdjacencyList(List<List<String>> friends) {
        Map<String, List<String>> resultAdjacencyList = new TreeMap<>();

        for(List<String> friend : friends) {
            String friendFirst = friend.get(0);
            String friendSecond = friend.get(1);

            if (!resultAdjacencyList.containsKey(friendFirst)) {
                resultAdjacencyList.put(friendFirst, new ArrayList<>());
            }
            resultAdjacencyList.get(friendFirst).add(friendSecond);

            if (!resultAdjacencyList.containsKey(friendSecond)) {
                resultAdjacencyList.put(friendSecond, new ArrayList<>());
            }
            resultAdjacencyList.get(friendSecond).add(friendFirst);
        }

        return resultAdjacencyList;
}

처음에는 위 코드처럼 if문을 붙이고, containsKey를 사용하여 키 값이 있는지 확인하다가 나중에 putIfAbsent를 사용하여 아래 코드로 깔끔하게 수정했습니다.

 

 

private static Map<String, List<String>> getAdjacencyList(List<List<String>> friends) {
    Map<String, List<String>> resultAdjacencyList = new TreeMap<>();

    friends.forEach(friend -> {
        String friendFirst = friend.get(0);
        String friendSecond = friend.get(1);

        resultAdjacencyList.putIfAbsent(friendFirst, new ArrayList<>());
        resultAdjacencyList.get(friendFirst).add(friendSecond);

        resultAdjacencyList.putIfAbsent(friendSecond, new ArrayList<>());
        resultAdjacencyList.get(friendSecond).add(friendFirst);
    });

    return resultAdjacencyList;
}

putIfAbsent(key, defaultValue)는 List에 key가 존재할 경우 넘어가지만, key가 존재하지 않을 경우 defaultValue로 설정해주는 코드입니다.

비슷한 기능으로 getOrDefault(key, defaultValue)가 있는데, 이것도 똑같이 key가 존재하면 원래 있는 value를 반환하고, 없으면 defaultValue를 반환합니다.

---

[각 유저의 점수 구하기]

private static Map<String, Integer> getScoreRecommendFriend(List<String> friendOfFriend, List<String> visitors) {
    Map<String, Integer> resultScoreRecommendFriend = new TreeMap<>();

    friendOfFriend.forEach(friend -> {
        resultScoreRecommendFriend.put(friend, 10);
    });

    visitors.forEach(visitor -> {
        resultScoreRecommendFriend.putIfAbsent(visitor, 0);
        resultScoreRecommendFriend.put(visitor, resultScoreRecommendFriend.get(visitor) + 1);
    });

    return resultScoreRecommendFriend;
}

여기서도 putIfAbsent를 사용하여 key가 없는 경우 0점을 추가하여 방문자에게 1점을 추가하도록 했습니다.

---

[유저 점수 목록에서 사용자의 친구 삭제하기]

private static Map<String, Integer> getRefineScoreRecommendFriend(
    Map<String, Integer> scoreRecommendFriend,
    List<String> friendOfUser) {
    Map<String, Integer> result = scoreRecommendFriend;

    for(String friend : friendOfUser) {
        result.remove(friend);
    }

    return result;
}

점수를 구할 때, 사용자의 친구가 visitor에 속해있으면 점수를 추가해주기 때문에 이 메소드를 통해서 사용자의 친구를 삭제할 수 있도록 하였습니다.

 

친구를 삭제하는 것도 리팩토링을 진행하여 간결하게 만들었습니다.

AS-IS
for(String friend : friendOfUser) {
    result.remove(friend);
}

TO-BE
friendOfUser.forEach(result::remove);

---

[추천할 유저들 정렬하기]

private static List<String> getSortedRecommendFriend(Map<String, Integer> scoreRecommendFriendMap) {
    List<String> result = scoreRecommendFriendMap.keySet()
            .stream()
            .sorted((user1, user2) -> {
                int user1Score = scoreRecommendFriendMap.get(user1);
                int user2Score = scoreRecommendFriendMap.get(user2);

                if (!Objects.equals(user1Score, user2Score)) {
                    return Boolean.FALSE.compareTo(user1Score > user2Score);
                } else {
                    return user1.compareTo(user2);
                }})
            .collect(Collectors.toList());

    return result;
}

여기서도 stream을 사용하여 정렬할 수 있도록 하였습니다. 이때 유저 1의 점수와 유저 2의 점수가 다르면 점수가 큰 유저가 앞으로 나오도록 했고, 점수가 같다면 사전순으로 나올 수 있도록 하였습니다.

---

 

 

문제를 풀면서 글을 작성하다보니까 시간도 오래 걸리고 내용이 엄청 길어졌네요.

자바로 알고리즘 문제를 풀어보는 것은 사실상 처음인데다가, 메소드로 기능 분리해보는 것도 오랜만이였고, 최대한 stream API를 사용하는 방향으로 코드를 작성해보니 시간이 엄청 오래 걸렸습니다.

커밋을 확인해보니 7일동안 매일 커밋을 보냈고, 총 63개의 커밋을 만들었네요 ㅋㅋ

 

다음 주부터 과제 테스트와 비슷한 프리코스가 진행될 것 같은데, 미리미리 컨벤션도 최대한 지켜보고, stream을 사용해보니까 좀 더 깔끔한 코드가 나올 수 있을 것 같다는 생각이 듭니다.

 

https://steady-coding.tistory.com/598

[Java] Java 8 vs Java 11

이 글을 살펴보면 자바 8에서 추가된 기능과 자바 11에서 추가된 기능을 볼 수 있는데, 나머지 내용들도 프리코스에서 적용할 수 있다면 직접 적용하는 것도 좋을 것 같습니다.