백준/16139 인간-컴퓨터 상호작용 / 다이나믹프로그래밍,메모이제이션

인간-컴퓨터 상호작용 서브태스크

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

256 MB

10013

2690

2216

29.606%

문제

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. 

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 S$S$, 특정 알파벳 α$\alpha$와 문자열의 구간 [l,r]$[l,r]$이 주어지면 S$S$의 l$l$번째 문자부터 r$r$번째 문자 사이에 α$\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0$0$번째부터 세며, l$l$번째와 r$r$번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q$q$번 할 것이다.

입력

첫 줄에 문자열 S$S$가 주어진다. 문자열의 길이는 200,000$200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q$q$가 주어지며, 문제의 수는 1≤q≤200,000$1\leq q\leq 200,000$을 만족한다. 세 번째 줄부터 (q+2)$(q+2)$번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 αi$\alpha_i$와 0≤li≤ri<|S|$0\leq l_i\leq r_i<|S|$를 만족하는 정수 li,ri$l_i,r_i$가 공백으로 구분되어 주어진다.

출력

각 질문마다 줄을 구분해 순서대로 답변한다. i$i$번째 줄에 S$S$의 li$l_i$번째 문자부터 ri$r_i$번째 문자 사이에 αi$\alpha_i$가 나타나는 횟수를 출력한다.

서브태스크 1 (50점)

문자열의 길이는 2,000$2,000$자 이하, 질문의 수는 2,000$2,000$개 이하이다.

서브태스크 2 (50점)

추가 제한 조건이 없다.

예제 입력 1 복사

seungjaehwang
4
a 0 5
a 0 6
a 6 10
a 7 10

예제 출력 1 복사

0
1
2
1

---

풀이

시간제한과 주어지는 입력갯수를 보고 반복문이 이중반복문만되도 풀수없구나를 판단한다.

어떤 로직을 가지고 원하는값에 대한 dp 배열을 채우고, 그걸 이용해서 값을 반환할지 생각한다.

/*
문자열의 길이는 20만 ,문제의 수도 20만, 인덱스 범위도 20만까지니까 반복문을 이용하면 시간초과가 날것같다.
어떻게해야 연산수를 줄일 수 있을까?
일단 물어보는것은 해당 인덱스범위에 나오는 특정 문자의 갯수이다. 즉 i,j 범위라고 치면 j까지 특정문자의 총 갯수합 - i까지 특정문자의 총 갯수합 이다.
각 알파벳에 대해 a-z까지 문자열 각 인덱스에 대한 특정문자 합을 저장해두면 되지않을까? dp[26][n]  문자열 길이 * 알파벳 갯수 만큼
 */

 

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    문자열의 길이는 20만 ,문제의 수도 20만, 인덱스 범위도 20만까지니까 반복문을 이용하면 시간초과가 날것같다.
    어떻게해야 연산수를 줄일 수 있을까?
    일단 물어보는것은 해당 인덱스범위에 나오는 특정 문자의 갯수이다. 즉 i,j 범위라고 치면 j까지 특정문자의 총 갯수합 - i까지 특정문자의 총 갯수합 이다.
    각 알파벳에 대해 a-z까지 문자열 각 인덱스에 대한 특정문자 합을 저장해두면 되지않을까? dp[26][n]  문자열 길이 * 알파벳 갯수 만큼
     */
    static int dp[][];
    static int q;
    static String input;


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        input = br.readLine();
        q = Integer.parseInt(br.readLine());
        dp = new int[26][input.length()];

    }

    static void solve() throws IOException {
        checkSum();
        for (int i = 0; i < q; i++) {
            String[] question = br.readLine().split(" ");
            int questionAscii = (int) question[0].charAt(0) - 97;
            int indexI = Integer.parseInt(question[1]);
            int indexJ = Integer.parseInt(question[2]);
            if (indexI == 0) {
                bw.write(dp[questionAscii][indexJ] + "\n");
            }
            else{
                bw.write(dp[questionAscii][indexJ] - dp[questionAscii][indexI - 1] + "\n");
            }
        }


    }

    static void checkSum ()  throws IOException{
        //자바에서 int 기본값을 0으로 따로 초기화할필요없다.
        for (int i = 0; i < input.length(); i++) {
            char currentCharacter = input.charAt(i);
            int currentAscii = (int) currentCharacter - 97; // a는 0 부터 z는 25 인덱스를 가지게끔

            dp[currentAscii][i] += 1; //해당 문자의 dp배열에 값을 증가 시킨다.
            if (i != 0) {
                for (int j = 0; j < 26; j++) {
                    //이전 인덱스값과 현재값을 더해 현재 인덱스값으로 초기화해줌으로서 해당위치에 문자갯수합을 저장해준다.
                    dp[j][i] += dp[j][i-1];
                }
            }
        }

//        for (int[] a : dp) {
//            bw.write(Arrays.toString(a) + "\n");
//        }
    }


}