검색 코드를 구분하는 가장 짧은 접두사
자바스크립트 코딩테스트 문제로 unique-prefix-trie 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
여러 검색 코드가 있을 때, 각 코드를 다른 코드와 구분할 수 있는 가장 짧은 접두사를 찾아보세요.
문제 설명
문자열 배열 codes가 주어집니다.
각 코드에 대해, 다른 어떤 코드도 같은 접두사로 시작하지 않는 가장 짧은 접두사를 찾아야 합니다.
예를 들어 ["shop", "ship", "shoe", "stock"]에서 "ship"은 "s"와 "sh"까지는 다른 코드들과 겹치지만, "shi"부터는 혼자만 가지는 접두사입니다.
각 코드의 답을 원래 입력 순서대로 담은 배열을 반환하는 shortestUniqueSearchPrefixes 함수를 작성하세요.
단, 어떤 코드가 다른 코드의 접두사라서 끝까지 봐도 혼자만의 접두사가 되지 않는 경우에는 그 코드 전체를 반환합니다.
제한사항
1 <= codes.length <= 1000001 <= codes[i].length <= 30codes[i]는 영문 소문자로만 이루어져 있습니다.codes안의 문자열은 서로 중복되지 않습니다.- 모든 코드 길이의 합은
300000이하입니다. - 반환값은
codes와 같은 길이의 문자열 배열입니다.
예시
- 입력:
codes = ["cart", "car", "dog"]-> 출력:["cart", "car", "d"] - 입력:
codes = ["alpha", "beta", "gamma"]-> 출력:["a", "b", "g"] - 입력:
codes = ["shop", "ship", "shoe", "stock"]-> 출력:["shop", "shi", "shoe", "st"] - 입력:
codes = ["aa", "ab", "aaa"]-> 출력:["aa", "ab", "aaa"]
힌트
- 접두사가 같은 코드들은 앞부분 문자를 공유합니다.
- 각 접두사를 몇 개의 코드가 지나가는지 저장해 보세요.
- 어떤 코드의 문자를 왼쪽부터 따라가다가 통과 개수가
1인 노드를 처음 만나면 그 지점이 정답입니다.
해설
모든 코드 쌍을 직접 비교하면 코드 수가 많을 때 너무 느립니다. 이 문제는 공통 접두사를 한 번만 저장하는 트라이를 쓰면 자연스럽게 풀 수 있습니다.
먼저 모든 코드를 트라이에 넣습니다. 문자를 하나 내려갈 때마다 해당 노드의 count를 1씩 늘립니다. 이 count는 그 접두사로 시작하는 코드가 몇 개인지를 뜻합니다.
그다음 각 코드를 다시 트라이에서 따라갑니다. 왼쪽부터 한 글자씩 내려가면서 현재 노드의 count가 1인지 확인합니다.
count가1이면 이 접두사를 가진 코드는 현재 코드뿐입니다.- 따라서 그 지점까지 자른 문자열이 가장 짧은 고유 접두사입니다.
예를 들어 codes = ["shop", "ship", "shoe", "stock"]을 보면 "ship"은 다음처럼 확인됩니다.
"s"로 시작하는 코드는 4개입니다."sh"로 시작하는 코드는 3개입니다."shi"로 시작하는 코드는 1개입니다.
그래서 "ship"의 답은 "shi"입니다.
반면 ["aa", "ab", "aaa"]에서 "aa"는 "aaa"의 접두사이기도 합니다. "aa"까지 내려가도 같은 접두사를 가진 코드가 2개이므로 혼자만의 접두사를 찾지 못합니다. 이런 경우에는 문제 조건에 따라 코드 전체인 "aa"를 반환합니다.
모든 코드를 넣고 다시 따라가는 동안 각 문자는 상수 번만 처리됩니다. 따라서 시간 복잡도는 모든 코드 길이의 합을 L이라고 할 때 O(L)이고, 트라이가 저장하는 노드 수도 최대 L개이므로 공간 복잡도도 O(L)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.