백준 16139 인간-컴퓨터 상호작용 [JAVA]

Ga0·2024년 2월 23일

baekjoon

목록 보기

119/137

문제 해석

문제는 첫 줄에 주어진 문자열(S)를 입력받고, 두번째 줄에는 질문의 개수(N)을 입력받는다.
입력받았다면 N줄 만큼 입력을 받는데 첫번째 값은 찾으려는 문자(findChar)이고, 두번째 값은 시작점(start), 세번째 값은 끝점(end)이다.
50점 코드를 작성하고 나서 다른 분들은 어떻게 풀었는지 확인을 해봤는데 2차원배열로 모든 알파벳을 기준으로 누적합을 하는 방식으로 푼 것을 확인했다.
글로 설명하기 어려워서 표로 만들어보았다. (아래의 표)
설명하자면, 주어진 문자열과 알파벳 데이터를 가지는 2차원 배열을 만들어서 주어진 문자열(S)을 기준으로 알파벳을 순서대로 진행하여 해당 알파벳을 들어갔는지 여부를 확인하여 누적합 방식으로 값을 저장한다.
누적합을 모두 구했다면 주어진 범위에 찾으려는 문자(findChar)가 몇개 들어가는 지 구해야한다.
start값과 end값 범위에서 찾으려는 문자(findChar)가 몇개가 들어갔는지 확인하려면 end값 - (start-1 값) 해주면 된다.
이를 코드로 표현하면 아래와 같다.

 alpha[end][findIdx]-alpha[start-1][findIdx] 
 -> findIdx는 찾으려는 문자열의 인덱스이고
 -> end - (start-1) 해주면 범위의 값이 나온다.

코드

50점

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        String S = br.readLine(); // 주어진 문자열
        int N = Integer.parseInt(br.readLine()); //질문의 수

        while(N --> 0) { //질문 개수만큼 반복
            st = new StringTokenizer(br.readLine());
            char findChar = st.nextToken().charAt(0); //찾으려는 문자
            int start = Integer.parseInt(st.nextToken()); //찾으려는 범위의 시작점
            int end = Integer.parseInt(st.nextToken()); //찾으려는 범위의 끝점

            int count = 0; //찾으려는 문자가 범위 내에 몇개 있는지 카운트하는 변수

            if(S.indexOf(findChar) >= 0){ //만약 찾으려는 문자가 포함되어 있으면 (문자열에)
                for(int i = start; i <= end; i++){
                    if(findChar == S.charAt(i)){ //만약 찾으려는 문자이면
                        count++; //카운트 + 1
                    }
                }
            }
            bw.write(count+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

}

누적합이라는 것을 신경을 아예 안쓰고 풀었더니 쉽게 풀긴 했지만 50점짜리 코드가 되었다..

100점

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        String S = br.readLine(); // 주어진 문자열
        int N = Integer.parseInt(br.readLine()); //질문의 수

        int[][] alpha = new int[S.length()+1][26]; //[주어진 문자열의 인덱스][해당 알파벳의 인덱스]

        //나머지 문자 탐색
        for(int i = 1;i<= S.length();i++) {
            //탐색 중인 문자
            int searchChar = S.charAt(i-1)-'a';

            //알파벳 a부터 z까지 반복
            for(int j = 0; j < 26; j++) {
                //현재 탐색중인 문자보다 한단계 앞인 문자의 값(=이전 값)
                int beforeValue = alpha[i-1][j];
                //알파벳과 탐색 중인 문자가 같으면 이전값 + 1,다르면 이전값으로 넣음
                alpha[i][j] = ( j == searchChar ? beforeValue+1 : beforeValue);
            }
        }

        while(N --> 0){
            st = new StringTokenizer(br.readLine());

            int findIdx = st.nextToken().charAt(0)-'a'; //찾으려는 문자의 인덱스
            int start = Integer.parseInt(st.nextToken())+1; //시작점
            int end = Integer.parseInt(st.nextToken())+1; //끝점

            //가장 끝점의 누적합 - 찾으려는 범위의
            bw.write((alpha[end][findIdx]-alpha[start-1][findIdx])+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}