[백준 알고리즘] 20437번 자바(Java) 문자열 게임2

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

 

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

풀이

• 시간복잡도
  • 테스트 케이스만큼 문자열을 2번(char개수 cnt, char개수 반복문)돌리므로 O(TK2), 즉 최대 100100002= 200만이므로 신경안써도 된다
• 풀이과정
  • 알파벳 갯수(26개)크기의 배열리스트들의 리스트를 만든 후 한 테스트케이스 문자열 에서 나온 알파벳의 위치를 저장해준다
  • 이후 각 알파벳에서 k이상의 문자가 나왔다면 이제 k-0, (k+1)-(0+1)…(k+j)-j 인덱스 뺀값을 구하고 기존의 minStrLen와 maxStrLen와 비교하여 값을 치환해준다
  • k개만큼 나오지 않은 경우를 찾는 방법은 maxStrLen 을 처음에 0을 대입해주고 시작하므로 이것을 이용하여 조건을 만들어줬다

 

예제 입력 예시

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

 

예제 출력 예시

4 8
-1

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class P20437{
    private static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
        while(T>0){
            char[] newlineCharArray = br.readLine().toCharArray();
            int k = Integer.parseInt(br.readLine());
            findMinMaxLine(newlineCharArray, k);
            T--;
        }

        System.out.println(sb);
    }

    //입력받은 문자열에서 k개만큼 같은 문자가 속한 min, max line길이 구하기
    static void findMinMaxLine(char[] newlineCharArray, int k){
        ArrayList<Integer>[] charArrayList = new ArrayList[26];

        //line의 각 문자 개수 카운트해주기
        for (int i = 0; i < 26; i++) charArrayList[i] = new ArrayList<>();
        for (int i = 0; i <newlineCharArray.length ; i++) {
            charArrayList[newlineCharArray[i]-97].add(i);
        }

        int minStrLen = 10001;
        int maxStrLen = 0;
        for (int i = 0; i < 26; i++) {
            if(charArrayList[i].size() >= k){
                int tempMinIndex;
                int tempMaxIndex;
                for (int j = k-1; j < charArrayList[i].size(); j++) {
                    tempMinIndex = charArrayList[i].get(j-k+1);
                    tempMaxIndex = charArrayList[i].get(j);
                    minStrLen = Math.min(minStrLen, (tempMaxIndex-tempMinIndex+1));
                    maxStrLen = Math.max(maxStrLen, (tempMaxIndex-tempMinIndex+1));
                }
            }
        }

        if(maxStrLen == 0)  sb.append("-1").append("\n");
        else sb.append(minStrLen).append(" ").append(maxStrLen).append("\n");
    }
}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2