[TIL] dart Sort

티라노·2024년 12월 10일

algorithm

Today I Learned

목록 보기

26/38

leetCode 알고리즘 문제 풀기

오늘 푼 문제에는 전부 sort() 함수가 들어가서 이렇게 제목을 지었다.

첫 번째 문제

정수 배열에서 k번째로 큰 숫자를 반환해라.

코드

class Solution {
  int findKthLargest(List<int> nums, int k) {
    nums.sort();
    return(nums[nums.length-k]);
  }
}

배열을 정렬한 다음 뒤에서 k번째 숫자를 반환하면 끝나는 아주 간단한 문제이다.
dart에는 정렬 알고리즘이 구현되어있어서 편하다. sort를 직접 짜려면 시간이 더 오래 걸렸을 것이다.

나는 빌트인 함수를 안 쓰고 자꾸만 쌩으로 구현하려는 습관이 있는데 이런 함수를 계속 찾아보고 공부해야 더 빠르고 깔끔하게 코딩할 수 있을 것 같다...

대신 편리하다는 장점이 있는 만큼 sort() 함수는 실행시간을 많이 잡아먹는다.

코드가 길어지더라도 실행시간을 줄이고 싶다면 배열의 1번 인덱스부터 k번 순환하며 k번째로 큰 수를 찾는 방법을 쓰면 된다. 물론 이걸 그대로 구현하면 여전히 O(n^2)이다.

이 때 k가 n/2보다 큰지 작은지 조건에 따라 k번째로 큰 수를 반환하거나 n-k번째로 작은 수를 반환할지 분기를 나누면 무조건 n^2보다는 적은 시간 안에 알고리즘을 수행할 수 있다.

두 번째 문제

검색어 제안 시스템을 만들어라.
예를 들어 ["mobile","mouse","moneypot","monitor","mousepad"] 배열이 주어지고 검색어가 "mouse"라면
사용자가 "m" -> "mo" -> "mou" -> "mous" -> "mouse" 순서로 검색어를 입력할 때
[["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]]
처럼 추천 검색어를 오름차순으로 최대 3개씩 저장하는 리스트를 반환해라.

복잡해보이지만 그렇게 어려운 문제는 아니다.
문제에서 실시간으로 사용자의 입력을 감지하는 기능까지 요구하지는 않기 때문이다.

검색어 전체를 순회하면서 실시간 검색어를 업데이트하고, 그에 맞게 startsWith() 로 추천 검색어에 어울리는 요소를 걸러내면 된다.

코드

class Solution {
  List<List<String>> suggestedProducts(List<String> products, String searchWord) {
    products.sort(); // 리스트를 오름차순으로 정렬
    List<List<String>> output = []; // 반환할 리스트
    String search='';  // 실시간 검색 문자열
    
    // searchWord를 순회
    for(int i=0;i<searchWord.length;i++){
      // 실시간 검색 문자열에 searchWord의 현재 인덱스를 추가
      // "m" -> "mo" -> "mou" -> "mous" -> "mouse"
      search+=searchWord[i];
      List<String> curOutput = []; // 실시간 검색어에 따른 추천검색어
      // 추천검색어를 고르는 기능
      for(int j=0;j<products.length;j++){
        if(products[j].startsWith(search)){
          curOutput.add(products[j]);
        }
        // 3개 이상일 경우 추천 알고리즘 종료
        if(curOutput.length>=3){
          break;
        }
      }
	  // 이번 차시의 추천 검색어 목록을 output에 추가
      output.add(curOutput);
    }
    return output;
  }
}