백준 java 문제풀이 (43) 12891 : DNA 비밀번호

 

주어진 문자열의 연속된 부분 문자열 중 조건에 만족하는 문자열의 개수를 찾는 문제다.

우선 출력값이 0인 예제는 보통 도움이 안되므로 2번 예제를 확인해보자.

 

 

 

음.. 끄덕끄덕.. 그렇게 푸는 문제군요.

이런 연속된 값도 그냥 투포인터로 풀어도 되겠지만 입력값의 최대값이 1,000,000이라고 한다.

더 효율적인 방법은 없을까?

 

그렇다면 당신은 슬라이딩 윈도우입니다.

 

슬라이딩 윈도우는 기본적으로 네트워크 패킷 교환에 사용되는 알고리즘이며, 그 외에도 여러가지 데이터 가공 목적으로 활용되는 알고리즘이다. 

더 궁금하면 검색해보고.. 아무튼 구해야하는 값이 연속적이며, 크기가 일정하다면 문자열 뿐 아니라 구간합 구하기 같은 문제에도 활용할 수 있다.

 

처음 봤던 예제를 다시 한 번 보자.

전체 배열의 크기는 4, 구해야하는 문자열의 길이는 2다.

그리고 부분 문자열에 들어가야하는 문자는 A 1개, T 1개였다.

 

이런 식으로 풀어보면 어떨까요.

1. 반드시 필요한 각 문자 개수 (위의 경우 {1 0 0 1})를 배열로 받는다. => requiredDna라고 부르겠다.

2. 비교 대상으로 쓸 비어있는 배열을 만들어준다 {0, 0, 0, 0} => checkArray라고 부르겠다

3. 우선 문제에서 제시한 구해야할 문자열 크기만큼 전체 배열크기를 반복해서 돌리며 checkArray에 값을 입력해준다.

그러면 위 예제에서는 checkArray{1,0,1,0}이 될 것이다. requiredDna{1 0 0 1}과 일치하지 않으므로 다음 단계로 넘어간다.

4. 우리는  구해야할 문자열의 크기만큼 통채로 돌리면서 비교하기로 했다. 따라서 우선 새로운 반복문을 만들되 시작 위치는 이전까지 비교한 부분의 다음 부분부터다. 기존에 비교하면서 체크했던 결과는 그대로 남겨두고, 우측으로 이동할 것이기 때문에 0번의 문자열은 제거하고 우측 문자열은 추가해주는 형태가 될 것이다.

위 예제에서는 G가 빠지고 T가 들어오기 때문에 ckeckArray{1, 0, 0, 1}이 되고 카운트가 1 증가한다.

5. 다시 한 번 이동하며 A가 제거되어 checkArray{0,0,0,1}이 되지만 새롭게 들어오는 문자열도 A이기 때문에 다시 checkArray{1,0,0,1}의 배열이 된다.

 

그리고 비교하는 함수는 이런 식으로 만들면 어떨까요.

 

처음 입력된 오리지널 문자열을 temporaryDna라고 부르겠다.

1. 인자로 requiredDna, checkArray, temporaryDna를 받는다.

2. temporaryDna를 각 A, C, G, T와 비교하며 checkArray[해당위치]에 ++해준다.

3. if ( checkArray[해당위치] == requiredDna[해당위치 ) 라면 카운트를 ++해주고, 임시 카운트가 구해야할 문자열 길이만큼 모인다면 정답 카운트를 ++해준다.

 

 

 

 

 

근데 이렇게 풀다보면 느낄 것이다.

코드가 더럽게 길어지던지 반복문이 많이 들어가야 한다.

 

둘 다 기분 나쁘니까 Map으로 바꿔보는 건 어떨까?

난 다 풀고 Map으로 갈아 엎엎다. 훨씬 깔끔해진다.

(글을 작성하고 다른 사람들 푼 걸 구경해봤는데 그냥 배열로도 극단적으로 축약하면 충분히 짧게 작성할 수는 있더라)

 

정답은 밑으로.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main (String[] args) throws Exception {
        // 첫 번째 입력 : 만들 문자열 길이 S와 비밀번호로 사용할 길이 P
        // 두 번째 입력 : 임의 DNA 문자열
        // 세 번째 입력 : {A,C,G,T}의 최소 개수가 주어
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int dnaLength = Integer.parseInt(st.nextToken());
        int pwdLength = Integer.parseInt(st.nextToken());
 
        String[] temporaryDna = br.readLine().split("");
 
        st = new StringTokenizer(br.readLine(), " ");
        Map<String,Integer> requiredDna = new HashMap<>();
        Map<String,Integer> checkDna = new HashMap<>();
 
        requiredDna.put("A", Integer.parseInt(st.nextToken()));
        requiredDna.put("C", Integer.parseInt(st.nextToken()));
        requiredDna.put("G", Integer.parseInt(st.nextToken()));
        requiredDna.put("T", Integer.parseInt(st.nextToken()));
 
        for (int i=0; i<pwdLength; i++) {
            add(temporaryDna[i], checkDna);
        }
 
        int answer = checkCount(requiredDna, checkDna);
 
        for (int i=pwdLength; i<dnaLength; i++) {
            int j = i-pwdLength;
            add(temporaryDna[i], checkDna);
            remove(temporaryDna[j], checkDna);
            answer += checkCount(requiredDna, checkDna);
        }
 
        System.out.println(answer);
    }
 
    public static void add(String str, Map<String,Integer> checkDna) {
        checkDna.put(str,checkDna.getOrDefault(str, 0)+1);
    }
 
    public static void remove(String str, Map<String,Integer> checkDna) {
        checkDna.put(str,checkDna.get(str)-1);
    }
 
    public static int checkCount(Map<String,Integer> requiredDna, Map<String,Integer> checkDna) {
        boolean bool = requiredDna.entrySet()
                .stream()
                .map((entry) -> {
                    if (checkDna.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                        return 0;
                    }
                    else return 1;
                })
                .noneMatch(num -> num==0);
 
        return (bool) ? 1 : 0;
    }
}