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

 

 

 

 누적 합을 이용해서 풀 수 있는 문제이다. 문자열을 입력받은 후, 문자열의 길이만큼 이차원 배열을 선언한다. 이차원 배열의 크기는 [문자열의 길이][26] 이다(알파벳은 26개). 문자열의 각 인덱스 별로 알파벳이 몇 번 나왔는지 저장하면 된다. 0 번째 인덱스부터 length - 1 번째 인덱스까지 반복하며 해당 알파벳을++ 해 주면 된다.

 

 

 말로 하면 복잡하기도 하고 필자가 설명을 잘 못 하기도 하니 코드로 확인해 보자.

Scanner scanner = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
String str = scanner.next();//입력받을 문자열
int n = scanner.nextInt();//테스트 갯수
char character = scanner.next().charAt(0);//확인할 문자
int from = scanner.nextInt();//l
int to = scanner.nextInt();//r
int[][] counted = new int[str.length()][26];//문자열의 인덱스 별 누적 합 저장 변수
counted[0][str.charAt(0) - 'a']++;//문자열의 0번째 알파벳 ++

우선 필요한 변수들을 선언하고, 문자열의 0 번째 인덱스에 해당하는 알파벳을 ++ 한다.

 

 

 

 

 

 

 

 

//1번쨰 인덱스부터 문자열을 돌면서 해당 알파벳을 ++
for(int i = 1; i<str.length(); i++){
    for(int j = 0; j<26; j++){
        counted[i+1][j] = counted[i][j];
    }
    counted[i][str.charAt(i)-'a']++;
}

그 다음, 1 번째 인덱스부터 시작해서 누적 합을 하며, 해당 인덱스에 해당하는 알파벳을 ++ 한다.

 

 

 

sb.append(counted[to][character-'a'] - counted[from][character-'a'] + (str.charAt(from) == character ? 1 : 0));
sb.append("\n");

결과 문자열에 추가해 준다.

 주의해야 할 점은 입력값이

bavdad

1

a 1 5 일 시,

counted[to][character-'a'] - counted[from][character-'a'] 만 해 버리면 1 번째 인덱스에 있는 a가 count 되지 않게 되므로, str.charAt(from) == character ? 1 : 0 를 꼭 더해주자.

 

 

 

 

 

 

//나머지 작업
for(int i = 1; i<n; i++){
    character = scanner.next().charAt(0);
    from = scanner.nextInt();
    to = scanner.nextInt();
    sb.append(counted[to][character-'a'] - counted[from][character-'a'] + (str.charAt(from) == character ? 1 : 0));
    sb.append(i == n-1 ? "" : "\n");
}

나머지 작업을 해 준다. 누적 합을 사용해 결과를 계속 저장해주면 된다.

여기도 마찬가지로 입력값이

bavdad

1

a 1 5 일 시,

counted[to][character-'a'] - counted[from][character-'a'] 만 해 버리면 1 번째 인덱스에 있는 a가 count 되지 않게 되므로, str.charAt(from) == character ? 1 : 0 를 꼭 더해주자.

 

 

 

 

 

 

 

 

 

결과 코드 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        String str = scanner.next();//입력받을 문자열
        int n = scanner.nextInt();//테스트 갯수
        char character = scanner.next().charAt(0);//확인할 문자
        int from = scanner.nextInt();//l
        int to = scanner.nextInt();//r
        int[][] counted = new int[str.length()][26];//문자열의 인덱스 별 누적 합 저장 변수

        counted[0][str.charAt(0) - 'a']++;//문자열의 0번째 알파벳 ++

        //1번쨰 인덱스부터 문자열을 돌면서 해당 알파벳을 ++
        for(int i = 1; i<str.length(); i++){
            for(int j = 0; j<26; j++){
                counted[i+1][j] = counted[i][j];
            }
            counted[i][str.charAt(i)-'a']++;
        }
        sb.append(counted[to][character-'a'] - counted[from][character-'a'] + (str.charAt(from) == character ? 1 : 0));
        sb.append("\n");

        //나머지 작업
        for(int i = 1; i<n; i++){
            character = scanner.next().charAt(0);
            from = scanner.nextInt();
            to = scanner.nextInt();
            sb.append(counted[to][character-'a'] - counted[from][character-'a'] + (str.charAt(from) == character ? 1 : 0));
            sb.append(i == n-1 ? "" : "\n");
        }
        System.out.print(sb);
    }
}