[백준 / BOJ] 19585 전설 (cpp / Java)

문제

출처 : https://www.acmicpc.net/problem/19585

19585번: 전설

C개의 색상, N개의 닉네임, Q개의 팀이 주어진다.

이때, Q개의 팀중 색상+닉네임 으로 이루어진 팀은 "Yes" 아닌경우 "No"를 출력하는 문제다.

---

풀이

Trie + 해싱 알고리즘으로 푼 문제다.

색상과 닉네임을 모두 Trie구조로 만들경우,

색상의 최대길이 * 닉네임의 최대길이 * 팀의 최대 갯수 = 1000 * 1000 * 20000이 되어서 TLE가 나온다.

따라서, 색상 혹은 닉네임을 찾는 과정을 O(1)로 줄여줘야 하는데, HashSet을 이용하면 쉽게 가능하다.

 

로직은 다음과 같다.

 

1. 색상을 Trie구조로 만든다.

2. 닉네임을 Set에 저장한다.

3. 팀명을 입력받으면 색상 Trie구조를 탐색해가며, 현재 지점이 어떠한 색의 마지막이 될 수 있는지 체크한다. 만약 될 수 있다면, 현재 지점까지의 색을 팀명에서 뺀 값이 닉네임 Set에 존재하는지 체크한다. 

4. 존재한다면, Yes를 출력, 아니라면 No를 출력한다.

 

위 과정을 Q번 반복하면된다.

 

닉네임을 찾는과정을 O(1)로 줄여서 총 시간복잡도는 O(Q) 가 된다.

 

---

전체 소스코드

(들어가면, Java 파일과 cpp파일이 모두 있습니다.)

https://github.com/devxb/JJUNalgo/tree/master/19585%20전설

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃