코후닝

알고리즘 분류: 트라이, 해싱문제 링크: https://www.acmicpc.net/problem/19585 【 문제 】 색깔을 의미하는 문자열 c개와 유저의 닉네임 n개가 주어진다.이후 팀원들의 닉네임이 n개가 주어질 때, 색상 이름과 닉네임이 순서대로 주어진 목록에 있는지 확인하는 문제이다. 【 풀이 】 정말 쉽지 않은 문제였다.정답을 맞히는데 까지 총 3번의 리팩토링을 거쳤다. 1. 색깔은 정방향으로 트라이 탐색, 닉네임은 역방향으로 트라이 탐색 이 풀이가 거의 10분 만에 생각나서 날먹하려 했지만.. 당연히 시간초과가 났다쿼리 20000개, 색깔과 닉네임 개수 4000개, 그리고 문자열 길이 각각 1000글자 싹이니, 색깔의 길이를 L, 닉네임 길이를 K라고 한다면이 풀이는 시간 복잡도 O(q *..