moner_ari   1년 전

먼저, 색깔의 이름(color)을 받을 트라이와, 닉네임의 이름(nick)을 받을 트라이까지 2개의 트라이를 만드는데, 모든 색깔 이름의 마지막 글자 정점은 닉네임 트라이의 root 정점과 연결되게 하여 트라이를 구성했습니다. 이때 색깔과 닉네임이 합쳐서 최악의 경우 8백만 글자까지 들어갈 수 있어서, 최대한 공간을 줄이기 위해 Node 구조체로 구성된 동적 배열(vector)을 이용하여 트라이를 만들었습니다.

Node 구조체는 child 정점의 정보를 (가능한 다음 문자: 다음 문자의 index)의 key-value 쌍을 저장하는 map 자료 구조를 사용한 child와, 색깔/닉네임 트라이의 마지막 글자인지를 각각 판별하는 color_end, nick_end로 구성되어 있으며, 처음에는 둘 다 false로 초기화됩니다.

--------

다음으로 문제에서 c(색깔 이름 개수)와 n(닉네임 개수)가 입력되면, 먼저 색깔 트라이를 구성하기 위해 색깔 이름을 1개씩 넣습니다. 이는 insert()에서 com이라는 매개변수가 1인 경우로, 0(색깔 트라이의 root 정점)번 정점에서 시작해서 글자를 채운 후, 나중에 색깔 트라이와 닉네임 트라이를 구성하기 위해 색깔 이름의 마지막 글자 정점의 번호는 따로 colors라는 vector<int>에 집어 넣습니다. 또한, 색깔 트라이의 마지막 정점이라는 표시를 color_end = true로 해줍니다.

이제 색깔 트라이를 완성했으니 닉네임 트라이를 만들어야 하는데, 먼저 닉네임 트라이의 root 정점은 이 시점의 last 번호와 같으니 이로 초기화시켜 줍니다. 그리고 방금 전 색깔 트라이의 마지막 정점들을 모두 닉네임 트라이의 root 정점과 연결시켜야 하므로, colors에 접근해서 각 번호에 접근해서 연결시킵니다.

그러면 닉네임 트라이를 만들어주면 됩니다. 이는 insert()에서 com의 값이 2인 경우로, 기본적인 작동 원리는 위와 같으나 닉네임의 이름의 마지막 글자 정점들은 '닉네임의 끝'이라는 표시를 nick_end = true로 해줍니다.

--------

이렇게 해서 색깔과 닉네임의 트라이를 완성했다면, 이제 Q개의 팀 이름을 받아서 팀 이름을 트라이에서 찾을 수 있는지 검색해야 하는데, 이는 find() 함수로 구현할 수 있습니다. 원래 저의 의도는 다음과 같았습니다.

1. 색깔 부분을 탐색하는데, 만약 color_end == true이고 현재 탐색하는 글자가 child에 있는 경우: 이 경우 색깔 부분을 그 시점에서 끝내고 바로 닉네임으로 탐색할 수도 있고, 아직 색깔이 끝나지 않았다고 가정하고 계속 색깔 부분을 탐색할 수도 있습니다. 그렇기 때문에 재귀 함수를 호출해서 '색깔 부분이 현재 탐색 중인 문자에서 끝난다.'라고 가정했을 때, 팀 이름을 트라이에서 찾을 수 있는지 처리한 결과를 alter라는 변수에 저장합니다.

2. 색깔 부분을 탐색하는데, 만약 color_end == true이고 현재 탐색하는 글자가 child에 없는 경우: 이 경우 색깔 부분은 그 글자에서 이미 끝났기 때문에, 이제 무조건 닉네임 트라이에서 검색을 이어가야 합니다.

3. 위의 1, 2번을 제외하고, 현재 탐색하는 글자를 트라이에서 찾을 수 없는 경우: 이 경우 팀 이름을 트라이에서 찾을 수 없기 때문에 탐색에 실패하며, 이에 따라 false를 반환해야 합니다.

4. 그 외의 경우: 탐색하는 글자를 트라이에서 찾을 수 있기 때문에 계속 탐색을 이어가야 합니다.

1~4번 과정이 완전히 종료되었다면 팀 이름 전체를 트라이에서 탐색했다는 뜻인데, 만약 현재 위치가 '닉네임의 끝'이라면 팀 이름을 트라이에서 찾을 수 있으며, 그렇지 않다면 팀 이름을 트라이에서 찾을 수 없습니다. 이에 따라 각각 true, false를 반환합니다.

--------

이렇게 해서 아래 코드와 같이 구현했는데, 한 68% 정도에서 '맞왜틀'을 당했습니다... testcase.ac에서도 직접 코드를 돌려보면서 반례를 찾아보고 거기서 '모든 테스트 케이스에 대해 통과하는 코드입니다.'라고 뜨는데도 이렇게 맞왜틀(?)을 당하니 너무 답답하네요. 제가 어떤 실수를 하고 있는지 잘 모르겠습니다.

제가 아이디어를 구상한 후 이를 구현하는 과정에서 뭔가가 꼬였는지, 아니면 제가 코드에서 만든 찾기 어려운 실수로 인해 문제 풀이에 실패한건지, 아니면 아예 접근 방법이 완전히 잘못되었는지 궁금합니다.

아래 코드는 제가 이 문제에 실제로 제출한 코드 중 하나입니다. 구현이 조금 복잡하지만 설명은 제가 위에서 했으니 참고하시면서 읽어 주시면 감사하겠습니다.

amazingtt2   1년 전

안녕하세요. 색깔과 닉네임 간에는 중복이 가능하기 때문에, 색깔과 닉네임을 한 트라이에서 탐색하는 대신, 색깔과 닉네임을 따로 분리하여 탐색, 관리하는 방법을 추천드립니다.

다음은 올려주신 코드에 대한 반례입니다.

4 5

ab

a

b

abc

ab

a

b

abc

bc

1

abc

정답

Yes

출력

No

moner_ari   1년 전

도움 주셔서 감사합니다!

오늘은 일단 밤이 늦었으니 이만 들어가고, 나중에 시간 내서 왜 제가 그동안 제출한 코드들이 시간 초과가 나거나 반례가 생겼는지 분석해보려 합니다.

일단 조언에 따라 색깔과 닉네임을 서로 분리해서 2개의 트라이로 구분해서 풀게 했는데 '시간 초과'가 나더라고요. 솔직하게 말하면 결국 이 시점까지도 계속 헤매서 다른 분들의 글에서 힌트를 얻었습니다. 워낙 어려운 문제인데다 최근 며칠동안 트라이 관련 문제들 풀면서 자신감이 생겨서 어떻게든 제 힘으로 풀어보려 했는데 결국 100% 제 힘으로는 풀지 못해서 많이 부끄럽네요. 그래도 이것도 하나의 성장 과정이라고 생각하고 인내해 보려고 합니다.

댓글을 작성하려면 로그인해야 합니다.