우테코 온보딩 - Problem 6

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

문제 설명

우아한테크코스에서는 교육생(이하 크루) 간 소통 시 닉네임을 사용한다. 간혹 비슷한 닉네임을 정하는 경우가 있는데, 이러할 경우 소통할 때 혼란을 불러일으킬 수 있다.

혼란을 막기 위해 크루들의 닉네임 중 **같은 글자가 연속적으로 포함** 될 경우 해당 닉네임 사용을 제한하려 한다. 이를 위해 같은 글자가 연속적으로 포함되는 닉네임을 신청한 크루들에게 알려주는 시스템을 만들려고 한다.

신청받은 닉네임 중 **같은 글자가 연속적으로 포함** 되는 닉네임을 작성한 지원자의 이메일 목록을 return 하도록 solution 메서드를 완성하라.

제한사항
- 두 글자 이상의 문자가 연속적으로 순서에 맞추어 포함되어 있는 경우 중복으로 간주한다.
- 크루는 1명 이상 10,000명 이하이다.
- 이메일은 이메일 형식에 부합하며, 전체 길이는 11자 이상 20자 미만이다.
- 신청할 수 있는 이메일은 `email.com` 도메인으로만 제한한다.
- 닉네임은 한글만 가능하고 전체 길이는 1자 이상 20자 미만이다.
- result는 이메일에 해당하는 부분의 문자열을 오름차순으로 정렬하고 중복은 제거한다.

 

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

 

풀이 코드

package onboarding;

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

public class Problem6 {
    public static List<String> solution(List<List<String>> forms) {
        List<List<String>> tempForms = new ArrayList<>(forms);
        List<String> result = new ArrayList<>();
        String[] nameArr = tempForms.stream().map(o -> o.get(1)).toArray(String[]::new);
        Map<String, Integer> checkMap = new HashMap<>();
        
        for(String s : nameArr) {
            if(s.length() < 2) continue;
            Set<String> tempSet = new HashSet<>();
            
//            불필요한 로직이라 주석처리 (최초 풀이)
//            for(int i = 2; i <= s.length(); i++) {
//                for(int j = 0; j <= s.length() - i; j++) {
//                    String key = s.substring(j, j + i);
//                    checkMap.put(key, checkMap.getOrDefault(key, 0) + 1);
//                }
//            }

            for(int j = 0; j <= s.length() - 2; j++) { // ---- #1
                String key = s.substring(j, j + 2);
                tempSet.add(key);
            }

            for(String key : tempSet) { // ---- #2
                checkMap.put(key, checkMap.getOrDefault(key, 0) + 1);
            }
        }

        checkMap.entrySet().removeIf(o -> o.getValue() == 1);
        for(String k : checkMap.keySet()) {
            for (int i = 0; i < tempForms.size();) {
                if (tempForms.get(i).get(1).contains(k)) {
                    result.add(tempForms.get(i).get(0));
                    tempForms.remove(i);
                } else {
                    i += 1;
                }
            }
        }

        return result.stream().distinct().sorted().collect(Collectors.toList());
    }
}

 

문제 해결 전략

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

일단 코드 설명 후 문제를 풀면서 든 생각과 이슈들에 대한 정리를 진행

사용된 변수들의 의미

• List<List<String>> tempForms : 입력 받은 forms의 복사본 (요소 remove를 하기 위해 복사하여 사용)
• String[] nameArr : 닉네임만 추출하여 저장하고 있는 String 배열
• Map<String, Integer> checkMap : 2개의 단어로 이루어진 문자열을 Key, 해당 문자열이 나온 닉네임의 카운트를 Value로 갖는 중복을 확인하기 위해 사용할 Map
• Set<String> tempSet : 닉네임에서 2단어 문자열로 나올 수 있는 단어를 저장하고 있는 첫번째로 나오는 향상된 for문에서 임시로 쓰이는 Set
• List<String> result : 최종 반환할 결과값을 저장하는 List

코드 설명

첫 번째 향상된 for문 : 닉네임을 순회하며 2글자 이상의 닉네임의 경우, 2글자로 이루어진 문자열을 checkMap에 저장 및 카운팅

첫 번째 향상된 for문을 빠져나온 후 checkMap에서 카운트가 1인 단어는 제거

두 번째 향상된 for문 : checkMap의 Key를 순회하며 해당 단어를 포함하는 닉네임의 Email을 result에 추가 후 해당 요소를 tempForm에서 제거 (제거하는 이유는 이미 중복으로 확인되어 추가했기 때문에 다시 해당 요소를 확인할 필요가 없기에 제거)

두 번째 향상된 for문을 빠져나온 후 result에서 중복 제거(불필요한 과정으로 코드에서 빼는게 좋아 보입니다.) 후 오름차순 정렬 후 반환하여 해결

 

생각 및 이슈 정리

이런 유형의 문제를 많이 접하지 않았기에 보자마자 "오우.. 코드가 좀 복잡해 지겠는데..?"와 "이건.. 시간 복잡도가 산으로 가는 방법 밖에 안떠오르는데.." 라는 생각이 동시에 떠올랐다.

그래도 일단 뭐라도 해야 진척이 있으니 구현을 시작하여 위 코드에서 주석 처리 한 코드로 구현을 했었다.

이 후 알고리즘 스터디원의 조언을 듣고는 위 주석 처리 된 코드는 불필요하다고 판단, 현재 코드로 수정을 하여 해결

스터디원의 조언을 내 언어로 요약하여 표현을 하자면 "어차피 2글자에서 중복이 되면 3글자 중복을 찾을 필요가 있을까?" 이다.

듣고보니 어차피 3글자 이상에서 중복인 단어는 2글자에서도 이미 중복으로 확인이 될 것이고, 그렇다면 2글자 초과의 경우에 대한 중복 확인은 불필요한 로직인 것!

그리고 스터디에서 해당 내용 발표 후 문제점을 지적 받았는데, 지적 받았던 문제는 위 코드에선 수정이 되었기에 발생하지 않는다.

지적 받았던 문제는 "#1" 주석과 "#2" 주석이 있는 코드 부분이 아래와 같은 코드 였기에 발생한 반복된 단어로 이루어진 닉네임의 경우에 해당 닉네임이 반복 되는 키 값으로 카운트가 증가하여 제거되는 문제이다.

            for(int i = 2; i <= s.length(); i++) {
                for(int j = 0; j <= s.length() - i; j++) {
                    String key = s.substring(j, j + i);
                    checkMap.put(key, checkMap.getOrDefault(key, 0) + 1);
                }
            }

간단한 예를 들자면, 입력으로 들어온 닉네임 리스트가 {"테스트", "반복반복"} 라고 한다면 닉네임간 중복되는 단어가 없기 때문에 반환값이 없어야 하지만 "반복반복"에 대한 닉네임을 확인하는 과정에서 "반복"이라는 단어가 2회 카운트 되면서 해당 닉네임이 중복 단어가 있는 닉네임으로 판단되어 반환값에 추가되는 문제였다.

그래서 문제가 되는 코드를 "#1"과 "#2" 주석이 있는 코드로 수정하여 해결하였다. (Set을 사용하여 하나의 닉네임에서 동일한 단어는 제외 후 Map에 카운트를 증가시키는 로직)

 

좋은 구현 방법이라고 생각되는 코드(알고리즘 스터디원) :  깃 허브

---

코드를 업로드해 둔 깃 허브