[BOJ_16139] 인간-컴퓨터 상호작용

 

📌 문제 링크: https://www.acmicpc.net/problem/16139

16139번: 인간-컴퓨터 상호작용

 

❌ 내 풀이(Failure) - 50점:

 

✅ 내 풀이(Success) - 100점, PyPy3 제출:

 

🧐 Review:

 서브테스크 1번을 맞춰서 50점을 받기는 쉽지만, 100점을 받기 위해서는 입력 값의 크기를 고려해서 시간 복잡도를 계산해야 한다. 문자열의 길이와 질문 개수 q는 최대 200,000으로 q번 동안 문자열 전체에 대해 알파벳의 존재 여부를 확인한다면 시간 초과가 발생한다. 따라서 매번 특정 구간에 대해 알파벳의 존재를 확인하는 것이 아닌 미리 알파벳의 등장 횟수를 모두 구해두고, 그 결과를 이용하는 방법을 사용해야 한다. 그래서 누적 합과 구간 합을 적용하도록 코드를 수정해서 100점으로 통과할 수 있었다.