1. 매내처(마나허) 알고리즘을 써야 시간 초과가 발생하지 않습니다. 2. 입력 닉네임으로 바로 퀼린드롬을 찾지 말고, 닉네임의 모든 알파벳들에 대해 먼저 '대칭이 존재하는 알파벳들로 변환'을 해줘야 합니다. 이때, '대문자와 소문자가 모두 대칭이 존재하는 알파벳'의 경우, '둘 중 하나로 통일'시켜줘야 추후 탐색 과정에서 제대로 탐색이 이뤄집니다. 예를 들어, uoU라는 닉네임이 들어왔다고 해봅시다. uoU를 그대로 사용해도, 세 글자 모두 대칭이 존재하니 문제가 없을 것으로 생각할 수 있습니다. 하지만, 그대로 사용하면 u와 U가 서로 다른 것으로 인식될 경우 최종 결과가 UouoU와 같이 5글자가 될 수 있습니다. 실제 정답은 3글자로, UoU 혹은 uou, UOU, uOu의 4가지 중 하나여야 합니다. 3. '기존 닉네임이 부분 문자열인 퀼린드롬'은 기존 닉네임 혹은 그 닉네임의 일부에 대한 대소문자 변형만 한 문자열이 한쪽 끝에 있어야 합니다. 3.1 부분 문자열은 부분 수열과 다르게 주어진 값이 부모 문자열 내부에서 연속되어 있어야 하기 때문입니다. 4. '최장 길이 퀼린드롬의 중심'이 '퀼린드롬 닉네임의 중심'과 일치하지 않을 수도 있습니다. 예를 들어, zss22s라는 입력이 들어왔다고 해봅시다. 여기서 최장 길이 퀼린드롬은 'S'와 '2'가 대칭이므로 SS22가 됩니다. (s는 대문자만 대칭이 있으므로 모두 S로 교체해야 합니다.) 하지만, 앞서 3번에서 언급했듯 기존 닉네임은 최종 닉네임의 한쪽 끝에 있어야 합니다. 만약 SS22를 중심으로 퀼린드롬을 만들고자 한다면 z와 s가 대칭이 아니므로 제대로 된 퀼린드롬이 만들어지지 않습니다. 그런데 z,s는 모두 대소문자 변형을 가하면 대칭이 있는 알파벳이며 2 또한 대칭인 알파벳이 있습니다. 그렇기에 '퀼린드롬 닉네임의 중심이 되기 위해'서는 발견한 '퀼린드롬의 한쪽 끝이 입력의 한쪽 끝에 닿아야' 합니다. 5. 만약 4번에서 발견한 조건인 '퀼린드롬의 한쪽 끝이 입력의 한쪽 끝에 닿는 퀼린드롬'이 입력 값에 없다면, 입력을 그대로 출력하고, 입력을 뒤집어서 한 번 더 출력해주면 됩니다. 6. 여기까지 해놓고, 한 글자짜리 대칭을 놓치는 불상사가 일어날 수도 있으니 주의하세요.
adfsfsf 1년 전 1
1. 매내처(마나허) 알고리즘을 써야 시간 초과가 발생하지 않습니다.
2. 입력 닉네임으로 바로 퀼린드롬을 찾지 말고, 닉네임의 모든 알파벳들에 대해 먼저 '대칭이 존재하는 알파벳들로 변환'을 해줘야 합니다.
이때, '대문자와 소문자가 모두 대칭이 존재하는 알파벳'의 경우, '둘 중 하나로 통일'시켜줘야 추후 탐색 과정에서 제대로 탐색이 이뤄집니다.
예를 들어, uoU라는 닉네임이 들어왔다고 해봅시다. uoU를 그대로 사용해도, 세 글자 모두 대칭이 존재하니 문제가 없을 것으로 생각할 수 있습니다.
하지만, 그대로 사용하면 u와 U가 서로 다른 것으로 인식될 경우 최종 결과가 UouoU와 같이 5글자가 될 수 있습니다.
실제 정답은 3글자로, UoU 혹은 uou, UOU, uOu의 4가지 중 하나여야 합니다.
3. '기존 닉네임이 부분 문자열인 퀼린드롬'은 기존 닉네임 혹은 그 닉네임의 일부에 대한 대소문자 변형만 한 문자열이 한쪽 끝에 있어야 합니다.
3.1 부분 문자열은 부분 수열과 다르게 주어진 값이 부모 문자열 내부에서 연속되어 있어야 하기 때문입니다.
4. '최장 길이 퀼린드롬의 중심'이 '퀼린드롬 닉네임의 중심'과 일치하지 않을 수도 있습니다.
예를 들어, zss22s라는 입력이 들어왔다고 해봅시다.
여기서 최장 길이 퀼린드롬은 'S'와 '2'가 대칭이므로 SS22가 됩니다. (s는 대문자만 대칭이 있으므로 모두 S로 교체해야 합니다.)
하지만, 앞서 3번에서 언급했듯 기존 닉네임은 최종 닉네임의 한쪽 끝에 있어야 합니다.
만약 SS22를 중심으로 퀼린드롬을 만들고자 한다면 z와 s가 대칭이 아니므로 제대로 된 퀼린드롬이 만들어지지 않습니다.
그런데 z,s는 모두 대소문자 변형을 가하면 대칭이 있는 알파벳이며 2 또한 대칭인 알파벳이 있습니다.
그렇기에 '퀼린드롬 닉네임의 중심이 되기 위해'서는 발견한 '퀼린드롬의 한쪽 끝이 입력의 한쪽 끝에 닿아야' 합니다.
5. 만약 4번에서 발견한 조건인 '퀼린드롬의 한쪽 끝이 입력의 한쪽 끝에 닿는 퀼린드롬'이 입력 값에 없다면, 입력을 그대로 출력하고, 입력을 뒤집어서 한 번 더 출력해주면 됩니다.
6. 여기까지 해놓고, 한 글자짜리 대칭을 놓치는 불상사가 일어날 수도 있으니 주의하세요.
이상으로 풀이하면서 겪었던 시행착오들을 적어봤습니다.