/
/

BOJ : 백준 12891 DNA 비밀번호(JAVA)

백준 12891 DNA 비밀번호 자바 풀이 💡
알고리즘투포인터
avatar
vari
2025.04.24
·
9 min read

문제

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.
하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다.
임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.
민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.
시간 제한 : 2초
메모리 제한 : 512MB

입력
S P
임의의 DNA 문자열
ACGT개수

풀이

요약
1, 임의의 문자열에서 부분 문자열(start~start+P)을 뽑고
2. ACGT의 개수가 몇 개인지 확인
3. 맞으면 카운트 ++

개수를 세면 되니까 해시맵을 사용하기로 했다.

while(start<S-P) 루프로 돌리고
end = start+P로 세팅
tempSt로 substring을 하자
hashMap에 map.containsKey로 key 가지고 있으면 꺼내서 +1, 없으면 0으로 넣어라
A, C, G, T 개수 확인해야겠지
확인하고 맞으면 res++
start++

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int S = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		String dnaString = br.readLine();
		
		st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int G = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());

		int start = 0, end = 0, res = 0;
		while(start <= S-P) {
			end = start + P;
			
			Map<Character, Integer> map = new HashMap<Character, Integer>();
			String tempStr = dnaString.substring(start, end);
			for(char temp : tempStr.toCharArray()) {
				if(map.containsKey(temp)) {
					map.put(temp, map.get(temp)+1);
					
				} else {
					map.put(temp, 1);
				}
			}
			
			if(A <= map.getOrDefault('A', 0)
				&& C <= map.getOrDefault('C', 0)
				&& G <= map.getOrDefault('G', 0)
				&& T <= map.getOrDefault('T', 0)) {
				res = res+1;
			}
			start++;
		}
		
		System.out.println(res);
	}

}

이렇게 제출했는데 시간 초과가 났다...
for문이 2중이어도 이미 substring한 string을 for문을 돌리므로 괜찮을 거라고 생각했는데 ... 1 ≤ |P| ≤ |S| ≤ 1,000,000 이므로 for문이 이렇게 2중이어서는 안 됐다.

루프가 끝나서 start++가 되기 전의 start와 end를 prevStart, prevEnd라고 하고 start++, end = start+P가 한 번 더 선언된 후의 start, end를 newStart, newEnd라고 해보자.
newStart = prevStart + 1이면 newEnd = prevEnd + 1이나 마찬가지이다.
그러면 꼭 start가 변했을 때 일일히 substring하여 for문을 돌릴 필요가 없지 않을까?
즉, 맨 앞에 있던 문자의 개수를 빼주고, 맨 뒤에 있는 문자의 개수만 추가하면 된다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int S = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		String dnaString = br.readLine();
		
		st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int G = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());

		int start = 0, end = 0, res = 0;
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		while(start <= S-P) {
			end = start + P;
			
			if(start == 0) {
				for(char temp : dnaString.substring(start, end).toCharArray()) {
					map.put(temp, map.getOrDefault(temp, 0)+1);
				}
			} else {
				map.put(dnaString.charAt(start-1), map.get(dnaString.charAt(start-1))-1);
				char newEndChar = dnaString.charAt(end-1);
				map.put(newEndChar, map.getOrDefault(newEndChar, 0)+1);
			}

			if(A <= map.getOrDefault('A', 0)
				&& C <= map.getOrDefault('C', 0)
				&& G <= map.getOrDefault('G', 0)
				&& T <= map.getOrDefault('T', 0)) {
				res++;
			}
			start++;
		}
		
		System.out.println(res);
	}

}
5500

평균 문제 풀이에 비해 메모리와 시간이 만족스럽지 않아 따로 풀이들을 찾아보았다.
hashMap을 사용하여 풀면 편하니 그렇게 풀었는데, array를 쓴 풀이들이 많았다.

  1. hashMap은 내부적으로 해시 함수 계산, 키 탐색 등의 오버헤드 때문에 인덱스로 접근하는 array에 비해 느리다.

  2. A, C, G, T 네 문자 밖에 없기에 length 4의 array로도 충분하며, 맵은 추가적인 메모리 오버헤드(더 많은 메모리)를 사용한다.(데이터 확장을 위한 여유 공간을 미리 할당해놓고, HashMap 객체 자체도 추가 메모리를 차지한다.)

그러므로 메모리, 시간을 단축하기 위해서는 array를 쓰는 게 더 효율적이었다..!
앞으로 키를 미리 알 수 있는 경우에는 array를 적극 활용해야겠다.

문제를 풀며

이렇게 구간의 길이가 고정적인 경우에 투 포인터를 쓰면 슬라이딩 윈도우 알고리즘이라고 한다. 이미 구해둔 교집합 정보를 최대한 사용하는 방법이라 효율적이다.

그리고 처음에 문제를 제대로 이해하지 못 해서.. 부분문자열이 P 값 이상이면 되는 줄 알고 코드를 작성했었다...ㅋㅋㅋ 🥹 심지어 인풋도 ACGT가 아니고 ACTG로 받아와서... 하... 어려운 문제가 아닌데 시간을 오래 썼다.. 😭 이상하다 싶으면 문제 다시 읽을 것!

- 컬렉션 아티클