트라이

[프로그래머스] level2 전화번호 목록 (C++)

C++에서 map을 사용한 해시로 쉽게 풀 수 있다. 나는 보자마자 트라이를 쓰는 문제 같았다. 해시를 떠올리지 못했다. 해시로 푸는 방법은 아래 블로그 참고 [Programmers] 전화번호 목록 간단한 문자열 문제입니다. 백준에서 골드 4정도의 완전히 동일한 문제가 있습니다. 동일한 문제이지만, 이... blog.naver.com 트라이의 특징은 문자열의 종료 위치를 표시해준다는 점이다. 따라서 주어진 배열을 먼저 길이 순으로 오름차순 정렬하고, 길이가 같은 경우에는 문자열의 값에 따라 오름차순 정렬한다. 이렇게 먼저 정렬해주면 뒤에 나오는 문자열이 그보다 앞에 나오는 문자열의 접두사인 경우를 배제할 수 있다. 그렇게 트라이로 풀 수 있는 조건이 성립하게 된다. 트라이에 문자를 하나씩 넣으면서 트라이..