상당히 어려운 문제입니다. 우선 세그먼트 트리라는 자료구조에 대해 알고 있어야 합니다.
우선 각 쿼리마다 정답의 첫 번째 글자를 알아냅니다. 이것은 복잡한 자료구조 없이 해결할 수 있습니다.
그러면 문제는 첫 번째 글자와 k가 주어졌을 때 "첫 글자가 x인 닉네임 중 사용 가능한 k번째 닉네임"를 구하는 쿼리 문제로 바뀝니다. 이것을 효율적으로 구하려면 "소설의 일정 위치부터 등장하지 않는 k번째 글자"를 효율적으로 구해야 하는데, 여기서 세그먼트 트리가 사용됩니다.
전체 풀이는 https://ucpc-kr.github.io/final/ 에서 확인할 수 있습니다.
park780172 4년 전
우선 알고리즘 초보인 저는 이 문제를 읽고, 아래처럼 생각하였습니다.
사실 이런 류의 문제는 보통 백트래킹으로 접근하려는 편입니다. 어떻게 보면 노가다 탐욕스러운 멍청한 짓일 수도 있겠네요 ㅠ
1. 어찌됐든 모든 것(모든 숫자들)을 탐색할 수 밖에 없다. 그리고, 비교한다. 예) 23이면, 2 >= 3인지 2 <= 3인지.
2. 그리고 탐색한 것을 map이나 어떠한 형태에 담아놔서 저장을 한 후, 이 후에 입력하는 K에 따라 바로 출력가능하게 한다.
위의 2개처럼 생각하였지만, 백트래킹 외에는 다른 방법이 생각이 나지 않습니다.
당연히 백트래킹은 시간 초과날 것임을 예상합니다.
모든 숫자를 탐색하는 수 밖에 없는 것 같은데,
백트래킹 외에
아주 조그마한 힌트 주실 분 계실까요?
조그만한 힌트로 풀어보려고 합니다 ㅠㅠ
첨부한 코드는...............
그냥 시간 초과 발생하라고 구현한 미천한 코드이니 제물로 드리겠습니다 ㅠ