[코딩 면접] 아마존 인터뷰 준비 - Search Suggestion System

제가 처음 이 문제를 풀었을 때는 products 배열을 그냥 사전순으로 정렬한 뒤 매 타이핑 글자마다 앞에서부터 3개를 잘라내는 방식으로 접근했었습니다. 작은 입력에서는 답이 맞는 듯했지만 한 번 제출해 보고 나서 시간 복잡도를 곱셈으로 다시 계산하는 순간 O(N²)이라는 결론이 떠올라 당황했었습니다. 그때부터 Trie로 갈아탈 수 밖에 없다는 생각이 들어, 각 노드에 top3 리스트를 같이 들고 다니게 만들고 searchWord를 한 글자씩 내려가며 사전순 후보를 저장하도록 다시 짜봤습니다. 그 결과로 빈 입력 처리도 자연스럽게 따라붙고, 면접관 입장에서도 "왜 정렬보다 Trie를 골랐는지" 한 문장으로 답할 수 있게 됐습니다.

문제 설명

제가 처음 이 문제를 만났을 때는 products 라는 이름의 문자열 배열과 searchWord라는 문자열이 주어진다, 라고 길게 적혀 있는 줄만 보고도 한숨부터 나왔었습니다. 시간이 지나서 알았지만 사실 searchWord의 각 문자가 타이핑될 때마다 products 안에 있는 상품명을 최대 3개까지 추천하는 추천 시스템을 디자인하라는 요구는, 입력 변수가 두 개로 작아 보이지만 "키 한 글자마다 결과가 새로 생긴다"는 점이 시간 복잡도를 폭증시키는 함정이라는 게 핵심이었습니다.

저는 처음에 제약 조건(1 <= products.length <= 1000, 1 <= Σ products[i].length <= 2 * 10^4) 줄을 흘겨보고 그냥 "작은 문제겠지"라고 넘겼다가, searchWord의 길이가 1000자 가까이 되는 입력 한 개에서 답이 늦게 나오는 걸 보고서야 그 2 * 10^4라는 숫자가 문자열을 다 모으면 searchWord 한 글자당 평균 20글자를 훑어야 한다는 뜻이라는 걸 뒤늦게 깨달았습니다. 면접 모의에서 이 줄을 무시했다가 시간 안에 못 끝낸 적도 있어서, 지금은 추천 시스템 류의 문제를 받으면 제약 조건 줄을 먼저 음미한 다음에야 풀이에 들어가는 습관을 들이고 있습니다.

예제 1:
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [ ["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"] ]

설명: 상품명의 사전식 순서는 ["mobile","moneypot","monitor","mouse","mousepad"] 이다. m과 mo를 타이핑하면 ["mobile","moneypot","monitor"] 순서대로 상풍명을 추천해야한다. mou, mous, 그리고 mouse를 타이핑하면["mouse","mousepad"] 를 추천해야한다.

예제 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

예제 3:
Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

예제 4:
Input: products = ["havana"], searchWord = "tatiana" Output: [[],[],[],[],[],[],[]]

제약 조건:
- 1 <= products.length <= 1000
- 중복되는 상품명 없음.
- 1 <= Σ products[i].length <= 2 * 10^4
- products[i]의 모든 문자열은 영문 소문자로 구성되어 있음.
- 1 <= searchWord.length <= 1000
- searchWord의 모든 문자는 영문 소문자로 구성되어 있음.

접근 방법

저는 처음에 "사전식 순서로 배열을 반환해야 한다는 점을 최대한 이용하기 위해서 먼저 products 배열을 오름차순으로 정렬을 하면 훨씬 쉬어진다"는 말을 읽고, 곧이곧대로 정렬 한 번 한 뒤 이중 for문으로 searchWord 글자마다 후보를 다시 잘라내는 단순한 코드를 짜봤었습니다. 작은 입력에서는 답이 맞았지만, 위에서 말씀드린 것처럼 한 화면 분량의 입력에서는 답이 한참 뒤에 떨어졌고, 면접관 화면에는 시간이 미끄러지는 게 그대로 보였습니다. 그래서 지금은 이 추천 시스템 같은 류에는 처음부터 검색 단계가 O(N)에 가깝게 끝나는 자료구조를 고르는 쪽을 기본값으로 잡고 있습니다.

• products 배열을 오름차순으로 정렬한다.
• Trie class를 정의한다. 다음 Trie와 현재 문자열의 top 3 리스트를 멤버 변수로 정의하면 무난하다.
• product[i]의 모든 문자열을 Trie로 생성한다. 동시에 top 3 리스트의 사이즈가 3 이하이면 현재 product[i]를 추가한다. 상품명이 이미 정렬되어 있기 때문에 현재 문자열을 집어넣는 것이 최선의 방법이다.
• searchWord의 문자를 처음부터 끝까지 확인하면서 현재 문자를 위에서 만들어놓은 Trie 자료구조 안에서 찾을 수 있으면 해당 Trie의 top 3을 저장한다. 만약 Trie에 존재하지 않는다면 현재 문자 이후로도 존재하지 않는다는 뜻이므로 남은 문자열 길이만큼 빈 리스트를 추가하고 끝낸다.
• 저장된 추천 리스트를 반환한다.

저는 처음에 이 알고리즘을 그대로 베껴 적은 뒤 products가 한 줄짜리 배열로 들어오는 입력만 가지고 "동작하니까 됐다"고 판단했었습니다. 그런데 면접 모의에서 검증을 한 단계 더 들어가자 바로 무너졌었습니다. 첫째는 products가 비어 있을 때인데, Trie 루트만 남아도 `createTrie`가 입력을 한 번도 받지 않은 채 끝나 버려 searchWord의 모든 글자에 대해 빈 리스트를 만들어내는 루프가 돌지 않는다는 함정이 있었습니다. 둘째는 searchWord의 첫 글자가 products의 어떤 접두사랑도 겹치지 않을 때입니다. 예를 들어 products가 ["apple","banana"]뿐인데 searchWord가 "carrot"이면, 루트에서 `next['c'-'a']`가 null이라 의도대로 다음 글자부터 전부 빈 리스트가 채워져야 하는데, 안에서 도는 for문에 이미 null 처리를 한 번 했어도 다음 글자 인덱스가 그대로 남아 있어서 잘못된 인덱스로 다시 find를 시도하는 일이 한 번 있었습니다. 그래서 지금은 위 코드를 그대로 쓰더라도 본인의 테스트에 다음 네 가지 케이스를 꼭 한 번 더 통과시켜 보는 편입니다.

• products 길이가 1인 경우 (top3 리스트가 곧 결과 전체)
• products 안에 서로 같은 글자로 시작하는 단어가 4개 이상인 경우 (Trie에서 top3가 의도대로 잘리는지)
• searchWord 첫 글자가 어떤 product 접두사와도 겹치지 않는 경우 (예제 4)
• searchWord 길이가 products 안 어떤 단어보다 더 긴 경우 (마지막 글자 이후 빈 리스트가 한 번 더 붙는지)

코드

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        Trie root = createTrie(products, searchWord);

        Trie cur = root;
        List<List<String>> result = new ArrayList<>();
        char[] arr = searchWord.toCharArray();
        for(int i = 0; i < arr.length; i++){
            Trie next = cur.next[arr[i] - 'a'];
            if(next == null) {
                for(;i < arr.length; i++){
                    result.add(Collections.emptyList());
                }
            } else {
                result.add(next.top3);
                cur = next;
            }
        }

        return result;

    }

    private Trie createTrie(String[] products, String searchWord){
        Trie root = new Trie();
        for(String product : products){
            char[] arr = product.toCharArray();
            Trie cur = root;
            for(char c : arr){
                if(cur.next[c - 'a'] == null)
                    cur.next[c - 'a'] = new Trie();;

                cur = cur.next[c - 'a'];
                if(cur.top3.size() < 3)
                    cur.top3.add(product);
            }
        }
        return root;
    }

    class Trie{
        Trie[] next = new Trie[26];
        List<String> top3 = new ArrayList<>();
    }

저는 처음에 "모든 문자열이 영문 소문자 이기 때문에 26개의 배열을 사용하면 모든 문자를 커버할 수 있다"는 한 줄을 보고 묻지도 따지지도 않고 Trie[] next = new Trie[26]을 그대로 베껴 적었었습니다. 그런데 unordered_map에 익숙해져 있는 제 환경에서 그 코드를 옮기려니까 인덱스 계산(c - 'a')과 null 체크 순서가 자꾸 헷갈렸고, 한 번은 26 길이 배열로 만든 다음에 한글 초성 매칭 문제를 옆에서 돌리는 코드를 짜다가 결국 Map로 갈아탄 적도 있습니다. 그래서 이 글에서는 26 길이 배열의 성능 이득을 보여 주는 쪽으로 그대로 두되, 해시 자료구조가 더 편하시다면 그렇게 바꾸셔도 답 자체는 똑같이 나온다는 점을 작은 주석 하나로 함께 적어 두었습니다.

마지막으로, 위 코드의 시간 복잡도는 O(N)이고 공간 복잡도는 O(3M)인데, 저는 이 라인을 그냥 외우고 있다가 면접에서 "왜 3M이냐"는 질문을 받고 한 박자 멈췄던 적이 있었습니다. 그때 돌아보니 답은 단순했는데, 같은 노드에서 최대 3개짜리 추천 리스트만 들고 다녀도 결국 그 리스트들이 모두 트리에 들어가 있고, 그 길이는 중복되지 않은 문자 패턴에 비례해서 자라기 때문에 3M이 그대로 누적이라는 뜻이었습니다. 즉 3은 검색 한 번에 들고 다닐 후보 수, M은 입력 문자 패턴 수라는 분리였고, 이 둘을 한곱셈으로 묶어 "공간 복잡도 O(3M)"이라 적는 게 표준 약속이라는 걸 그 자리에서야 명확히 정리하고 돌아왔었습니다.