문제
언어 모델은 원시 텍스트가 아니라 토큰을 다룹니다. 간단한 토크나이저는 텍스트를 소문자로 바꾸고, a-z 문자와 0-9 숫자가 연속된 부분을 하나의 단어로 봅니다. 그 밖의 모든 것(공백, 문장 부호, 기타 문자)은 단어를 구분합니다.
어휘 사전을 만드세요: 서로 다른 단어를 등장 횟수가 많은 순서로 정렬하고, 같으면 알파벳순으로 정렬합니다. 이 목록에서 단어의 위치가 토큰 ID입니다.
build_vocabulary(text)를 구현하세요.
입력
text: 임의의 텍스트.
출력
어휘 사전을 단어 목록으로 반환하세요. 텍스트에 단어가 없으면 빈 목록을 반환하세요.
제약 조건
0 ≤ text의 길이 ≤ 100,000
예시
입력:
text = "The cat sat on the mat. The end!"
예상 출력:
expected = ["the", "cat", "end", "mat", "on", "sat"]
입력:
std::string text = "The cat sat on the mat. The end!";
예상 출력:
std::vector<std::string> expected = {"the", "cat", "end", "mat", "on", "sat"};
입력:
string text = "The cat sat on the mat. The end!";
예상 출력:
string[] expected = new string[] {"the", "cat", "end", "mat", "on", "sat"};
설명
소문자로 바꾸면 단어는 the, cat, sat, on, the, mat, the, end입니다. "the"는 3번, 나머지는 한 번씩 나오며 알파벳순으로 정렬됩니다: ["the", "cat", "end", "mat", "on", "sat"].
입력:
text = "AI, ai and A.I. (2024)"
예상 출력:
expected = ["ai", "2024", "a", "and", "i"]
입력:
std::string text = "AI, ai and A.I. (2024)";
예상 출력:
std::vector<std::string> expected = {"ai", "2024", "a", "and", "i"};
입력:
string text = "AI, ai and A.I. (2024)";
예상 출력:
string[] expected = new string[] {"ai", "2024", "a", "and", "i"};
설명
단어: ai, ai, and, a, i, 2024. "ai"는 두 번, 나머지는 한 번씩 나오며 숫자가 문자보다 앞서는 알파벳순으로 정렬됩니다: ["ai", "2024", "a", "and", "i"].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
먼저 문자와 숫자로만 이루어진 연속 구간만 뽑고, 소문자로 바꾼 뒤 나머지는 무시하세요.
힌트 2
각 단어의 등장 횟수를 센 다음, 빈도 내림차순과 동률일 때 알파벳 순으로 정렬하세요.
힌트 3
텍스트에 유효한 단어가 없으면 singleton이나 null 대신 빈 리스트를 반환하세요.
예상 복잡도
시간 O(n log k), 추가 공간 O(k)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.