백준 16139번1 [백준 16139번] 인간-컴퓨터 상호작용 풀이 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문자열 S가 주어졌을 때, l 부터 r까지의 인덱스 중 알파벳 a의 개수를 출력하는 문제이다. a, l, r 이 q번 주어질 때마다 문자열을 일일이 탐색하여 해결할 수도 있겠지만 시간 초과가 발생할 것으로 예상된다. 해당 문제는 구간합 개념으로 쉽게 해결할 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 //idx s e u n g j a e h w a n g //s[idx] 0 1 1 1 1 1 1.. 2021. 10. 7. 이전 1 다음