[Algorithm] 백준 문자열 문제 - 문자열 게임 2(20437) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준의 문자열 문제 - 문자열 게임 2 자바풀이를 진행하도록 하겠습니다.

문제출처: https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = parseInt(br.readLine());
        
        StringGame stringGame = new StringGame();
        for (int i = 0; i < t; i++) {
            stringGame.addStr(br.readLine());
            stringGame.addTarget(parseInt(br.readLine()));
        }
        stringGame.find();
    }
}

class StringGame {
    List<String> strs = new ArrayList<>(); // 문자열을 담을 리스트
    List<Integer> targets = new ArrayList<>(); // k를 담을 타겟 리스트
    Map<Character, List<Integer>> map = new HashMap<>(); // 해시맵
    
    void addStr(String str) {
        strs.add(str);
    }
    
    void addTarget(int k) {
        targets.add(k);
    }
    
    void init() {
        for (char c = 'a'; c <= 'z'; c++) map.put(c, new ArrayList<>());
    } // 미리 각 문자에 대한 어레이 리스트 생성하여 맵에 저장
    
    void find() {
        init();
        StringBuilder sb = new StringBuilder();

        // T: 100  W: 10000   idx: 10000 / 26 (k = 1) , 삭제 10000 / 26,  알파벳 26
        // O(T * W + T * 10000 / 26 * 2 * 26) = O(300만)
        for (int i = 0; i < strs.size(); i++) { // 문자열 순회
            String str = strs.get(i);
            int k = targets.get(i);
            int min = Integer.MAX_VALUE; // 먼저 최소값 맥스로 설정
            int max = -1; // max는 문자열 길이이므로 1 이상 나올 수 있으므로 -1로 최소화 설정
            
            for (int j = 0; j < str.length(); j++) { // 각 문자에 대한 charAt으로 탐색
                List<Integer> idxs = map.get(str.charAt(j));
                idxs.add(j); // 인덱스 추가하기
            }
            
            Set<Character> set = map.keySet(); // 맵에서 키셋을 가져오기
            
            for (Character ch : set) { // 키셋을 순회하며 ch 가져옴
                List<Integer> idxs = map.get(ch); // 각 맵에 저장되어 있는 인덱스를 저장한 리스트 가져오기
                
                if (idxs.size() >= k) { // k보다 같거나 크다면, k개 이상이 알파벳이 존재한다는 의미
                    for (int idx = 0; idx + (k - 1) < idxs.size(); idx++) { // 현재 인덱스부터 k - 1 큰 인덱스까지
                        min = Math.min(min, idxs.get(idx + k - 1) - idxs.get(idx) + 1); // 1 ~ 3까지의 길이는 3이므로 + 1
                        max = Math.max(max, idxs.get(idx + k - 1) - idxs.get(idx) + 1);
                    }
                } 
                idxs.clear(); // 저장된 인덱스 모두 제거하기
            }
            
            if (min == Integer.MAX_VALUE && max == -1) sb.append(-1).append("\n");
            else sb.append(min).append(" ").append(max).append("\n");
        }
        
        System.out.print(sb);
    }
}

 

2. 풀이 중점사항

 

시간 복잡도 계산

해당 문제는 1초라는 시간이 주어졌고, 1024M라는 충분한 메모리가 제시되어 있습니다.

저는 각 문자열을 탐색하면서 map에 저장하고, map에 저장된 리스트의 길이가 k보다 같거나 크다면 내부의 인덱스를 순회하며 인덱스 간의 길이가 가장 길고 짧은 것을 판단하는 로직을 생각하였습니다.

 

가장 최악의 케이스를 고려해보면 다음과 같습니다.

 

T: 100 (케이스 개수)

W: 10000 (문자열 길이)

C: 26개의 알파벳이 모두 10000 / 26 개를 나눠가짐 

K: 1 (k = 1이므로 idx에 저장된 값을 모두 탐색)

A: 알파벳 26개 

 

따라서, 계산은 O(T * W + T * C * A) = O(100 * 10000 + 100 * 10000 / 26 * 26 * 2(add 후 clear)) = O(약 300만)

1초당 1억번이 가능하다고 가정하면 대략적으로 300만이면 충분히 가능한 시간이라고 판단하였습니다.

 

Map 사용

Map<Character, List<Integer>> map = new HashMap<>(); // 해시맵

--- 중략 ----

void init() {
        for (char c = 'a'; c <= 'z'; c++) map.put(c, new ArrayList<>());
    } // 미리 각 문자에 대한 어레이 리스트 생성하여 맵에 저장
    
---- 중략 ----

Set<Character> set = map.keySet();

 

HashMap에 먼저 알파벳과 arrayList<>를 저장하였습니다. 

그리고 각 문자열을 순회하며 각 문자가 나온 인덱스를 map에 저장하였습니다.

map.keySet()으로 알파벳을 모두 가져왔습니다.

 

 

idx.size() >= k개 활용

 

for (Character ch : set) { // 키셋을 순회하며 ch 가져옴
    List<Integer> idxs = map.get(ch); // 각 맵에 저장되어 있는 인덱스를 저장한 리스트 가져오기

    if (idxs.size() >= k) { // k보다 같거나 크다면, k개 이상이 알파벳이 존재한다는 의미
        for (int idx = 0; idx + (k - 1) < idxs.size(); idx++) { // 현재 인덱스부터 k - 1 큰 인덱스까지
            min = Math.min(min, idxs.get(idx + k - 1) - idxs.get(idx) + 1); // 1 ~ 3까지의 길이는 3이므로 + 1
            max = Math.max(max, idxs.get(idx + k - 1) - idxs.get(idx) + 1);
        }
    } 
    idxs.clear(); // 저장된 인덱스 모두 제거하기
}

idxs.size()로 k와 비교를 한 후, idx + (k - 1)가 idx.size()보다 작을 때까지 순회하며 값을 업데이트하였습니다.

 

이상으로 문자열 게임2 자바 풀이를 마치도록 하겠습니다.

감사합니다.!