[Leet Code] Search Suggestions System

기면지·2021년 6월 1일

LeetCode

목록 보기

16/20

안녕하세요! 오늘은 5월 5주차 3번째 알고리즘인 Search Suggestions System 풀이를 작성해보겠습니다.

문제

요약
주어진 searchWord 의 첫 글자부터 차례대로 시작하는 products 를 최대 3개까지 찾아 List에 저장해서 return하는 문제입니다.
즉, List의 0번 인덱스 List는 searchWord 의 첫 글자로 시작하는 단어들로 이루어져 있습니다.

처음으로 생각한 방법

자바의 substring 내장 함수를 사용해서 searchWord 의 처음부터 부분 문자열을 만듭니다. 그 후에 products 를 순회하면서 부분 문자열을 만들어서 두 개의 부분 문자열이 같은지 비교한 후에 List에 저장합니다.

이 방법이 틀렸는데, 이유는 두 가지가 있습니다.
1. List의 최대 길이가 3인 것을 적용하지 않았다.
2. searchWord 보다 products 에 있는 단어의 길이가 짧을 때, 예외가 발생할 수 있다.

두번째로 생각한 방법

자바의 startsWith 내장 함수를 사용해서 searchWord 의 부분문자열로 시작하는 products 안의 문자열을 찾아서 리스트에 최대 3개까지 저장합니다.

위의 방법에도 오류가 있었는데, products 문자열을 정렬하지 않아서 발생했습니다.
~~( 꼭 문제를 꼼꼼하게 읽자.. )~~

이제 코드 설명에 들어가겠습니다.

코드 설명

List<List<String>> result = new ArrayList<>();
Arrays.sort(products);

return할 result 리스트를 ArrayList 로 선언하고, 인수로 주어지는 products 를 정렬합니다.

for (int i = 1; i < searchWord.length() + 1; i++) {
    ArrayList<String> suggest = new ArrayList<>();
    String word = searchWord.substring(0, i);

    // ...
}

for문을 1부터 순회하면서 searchWord 의 부분 문자열인 word 를 만들어줍니다.
그리고 result 리스트에 저장할 suggest 리스트를 만들어줍니다.

for (int i = 1; i < searchWord.length() + 1; i++) {
	// ...

    for (int j = 0; j < products.length; j++) {
        if (suggest.size() >= 3) break;
        if (products[j].startsWith(word)) suggest.add(products[j]);
    }

    result.add(suggest);
}

그 다음에 products 배열을 순회하면서 만약 suggest 리스트의 길이가 3 이상이면 리스트가 모두 만들어졌으므로 break 로 루프를 빠져나옵니다.
만약 suggest 리스트의 길이가 3 미만이라면 products 의 문자열이 word 로 시작하는지 확인하여, true 라면 suggest 리스트에 추가합니다.

for문을 모두 순회한 후에 result 리스트에 suggest 리스트를 추가합니다.

전체 코드

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> result = new ArrayList<>();
        Arrays.sort(products);

        for (int i = 1; i < searchWord.length() + 1; i++) {
            ArrayList<String> suggest = new ArrayList<>();
            String word = searchWord.substring(0, i);

            for (int j = 0; j < products.length; j++) {
                if (suggest.size() >= 3) break;
                if (products[j].startsWith(word)) suggest.add(products[j]);
            }

            result.add(suggest);
        }
        
        return result;
    }
}