[5주차_화요일] 전자사전 만들기

[yeongleej]

• 사이트 : 코드트리(CT)
• 문제: 전자사전 만들기

[yeongleej]

🤔 시간복잡도 고려사항

• 단어 개수 N ≤ 100,000
• 문자열 길이 ≤ 1000
• 출력 횟수 T ≤ 1000
• 단순 완전탐색으로 단어를 찾기는 불가 => O(100,000 1000 1000)
• 이분탐색으로 사전을 탐색하기 => T * O(logN) 가능

💡 풀이 아이디어

• 사전에 있는 단어를 이분탐색으로 찾아야 하므로 정렬
• 이분탐색으로 word(찾고자하는 시작단어)보다 작거나(뒤에 있음) 같은 최소 단어를 찾으면 그 단어는 word로 시작할 수 있음
• 문자열 비교
  • s1.compareTo(s2) == 0 : s1와 s2가 같음
  • s1.compareTo(s2) > 0 (양수) : s2가 s1보다 사전순으로 앞섬
  • s1.compareTo(s2) < 0 (음수) : s2가 s1보다 사전순으로 뒤에 있음
• 즉, srr[i].compareTo(word) >= 0인 최소 인덱스 찾기
• 찾은 인덱스로부터 k번째 떨어져 있는 수가 정답
  • 이때, 구한 인덱스가 -1이 아니고 && 탐색할 인덱스 범위를 벗어나지 않으며 && word의 길이보다 크거나 같고 && word로 시작하는 단어라면 출력

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= N <= 100,000
• 1 <= T <= 1,000
• 완전탐색
  • 입력된 문자열에 대해 정렬하고, T만큼 탐색
  • 정렬비용 + 1,000 × 100,000 > 1억 (시간초과)
• 정렬하고 특정 원소를 찾는 문제 → 이분탐색
  • 정렬비용 + 1,000 × log(100,000) < 1억

💡 풀이 아이디어

• Node 클래스
  • String str: 입력된 문자의 정보
  • int idx: 몇 번째로 입력됐는지에 대한 정보
• getUppderIdx(String str)
  • 사전에서 str로 시작하는 단어가 끝난 직후 idx를 구하는 함수
  • S1.startWith(S2) 함수 이용
  • 문자열 S1이 문자열 S2로 시작했다면 true 반환
  • S1.compareTo(S2)
  • -1 반환: S1가 S2보다 앞서있음
  • 0 반환: S1과 S2가 같음
  • 1 반환: S1가 S2보다 뒤에 있음
• getLowerIdx(String str)
  • 사전에서 str로 시작하는 단어가 시작되는 idx를 구하는 함수

1. Node[] arr를 입력 후 정렬
2. T 개수만큼 반복
   • 입력된 str에 대해 lowerIdx와 uppderIdx찾기

     int diff = (uppderIdx - lowerIdx) - 1;
     if(diff < a - 1) -1;
     else arr[lowerIdx + (a - 1)].idx + 1

upperIdx는 구할 필요가 없었네요 !! ㅎㅎ

[icegosimperson]

🤔 시간복잡도 고려사항

• N(100,000) T(1,000) 길이 (1,000) -> 완전탐색 불가
• O(n logn)으로 줄이기 -> 이분탐색사용

💡 풀이 아이디어

• ArrayList: 사전 순으로 정렬한 단어 저장
• HashMap : 각 단어가 입력된 원래 위치(Key, Value값 함께 저장)
• Collections.sort 사전 순으로 정렬
• prefix로 시작하는 단어들 중 K번째가 있는지 이분 탐색으로 확인 -> 존재하지 않을 경우 -1 출력
• 이분탐색으로 첫 단어 위치를 찾음 : lower
• prefix 다음으로 올 수 있는 단어 위치 찾음 : nextPrefix

[baexxbin]

🤔 시간복잡도 고려사항

• 1 <= N <= 100,000
• 1 <= T <= 1,000
• O(NlogN) 이내로 풀기

💡 풀이 아이디어

처음에 트라이 문제인줄 알고,,, 공부하면서 풀었는데 실패했습니다🥹 이분탐색 문제였네요ㅠㅠ

• 트라이로 풀 경우 메모리 초과
• 최대단어개수 (N)100,000 * (T) 1000 *a 만큼의 공간을 가지고 있어야하는데 너무 큼
• 조건으로 알파벳이 소문자만 주어지는지 등도 알 수 없음

• 이분 탐색
  • 특정단어(s)로 시작할 수 있는 단어위치 찾기
  • 반환된 값은 s로 시작되는 단어의 시작 위치
  • 찾은 단어가 s로 시작하고, 존재하는 단어라면 입력순서 반환
  • 입력순서는 해시맵 사용

문제를 똑바로 읽고! 어떤 알고리즘 유형을 사용해야할지 더더 생각하고 문제 풀어야겠습니다!!!!

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 100,000 → 10^5이므로 O(N logN)의 이분 탐색 혹은 힙 정렬
• 1 ≤ 주어지는 문자열의 길이 ≤ 1,000 → 모든 키워드를 만들어서 저장하면 메모리 초과

💡 풀이 아이디어

• HashMap을 이용해서 입력된 순서를 저장
• 이분 탐색으로 해당 접두사를 가지는 가장 작은 인덱스(Lower Bound)를 찾음
• Lower Bound로부터 입력 받은 인덱스 만큼 증가한 곳의 문자열의 입력 순서 반환
  • 경계를 벗어나거나, 인덱스 만큼 증가한 곳의 문자열이 해당 접두사로 시작하지 않으면 -1 반환

    private static int getLowerBound(String prefix) {
    int l = 0, r = words.length - 1;
    while (l <= r) {
    int m = (l + r) / 2;
    if (words[m].compareTo(prefix) < 0)
        l = m + 1;
    else
        r = m - 1;
    }
    return l - 1;
    }

    words[idx + lowerBound - 1].startsWith(prefix)

    순간 공간복잡도 신경안쓰고 편하게 TreeMap으로 구현하려다가 메모리 초과났네요😿

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: 1 ≤ N ≤ 100,000 → 10^5 으로 O(NlogN) 이내로 풀이하기

💡 풀이 아이디어

1. 사전에서 T 의 특정문자 startWith() 와 compareTo() 에 따라 이분탐색(start,end)
2. k번째 해당하는 단어 찾기
3. 원본 사전에서 특정단어 찾기

시간 제한: 1000ms 초과한거 같은데..? 왜 통과된걸까요? 다른분들 코드보고 리팩토링을 해봐야겠어요ㅜㅜ 코드리뷰 환영해요🤩

수빈님 코드 참고해서 리팩토링 했더니 798ms 로 줄였어요!