[백준]12891 DNA 비밀번호 - 자바/Java

12891번: DNA 비밀번호

풀이

💡 메모리 : 26536KB, 시간 360ms

• 만족스러운 코드는 아니다.
• 일단 줄이 길어지는 기능 단위의 코드들은 메소드로 구분하여 구현했다. 이를 통해 코드의 가독성은 처음보다 개선되었다.
• 하지만 알고리즘에 맞추어 코드를 작성하다보니, 조건 분기가 잘못 설정되어 슬라이딩 윈도우의 마지막 회차에서 conCheck()메소드가 동작하지 않고 끝나게 되었다.
• 결국 for문 바깥쪽에서 if(conCheck()) ans++; 로 문제가 요구하는 답은 해결할 수 있었다.
• 이번에 배운 건, ‘알고리즘에 맞춰 코드를 작성’ 하는게 아니라
• ‘전체적인 코드 플로우를 구상하고, 이에 맞추어 알고리즘의 반환, 진행을 커스터마이징 하는 것’이 더 깔끔한 가독성있고 깔끔한 코드를 만든다는 것이다.

//틀린 코드입니다.
for(int i = 0; i<S-P+1; i++) { //투포인터 알고리즘
			int[] conTmp = new int[4]; // 검사할 array
			for(int j = i; j<i+P; j++) {
				char dnaPiece = dnaArray[j];
				switch(dnaPiece) {
				case 'A' : conTmp[0]++; break;
				case 'C' : conTmp[1]++; break;
				case 'G' : conTmp[2]++; break;
				case 'T' : conTmp[3]++; break;
				}
			}
			//조건 검사
			if(con[0] > conTmp[0] || con[1] > conTmp[1] || con[2] > conTmp[2] || con[3] > conTmp[3]) continue;
			ans++;
		}

for(int i = 0; i<S-P+1; i++) { //투포인터 알고리즘
			int[] conTmp = new int[4]; // 검사할 array
			for(int j = i; j<i+P; j++) {
				char dnaPiece = dnaArray[j];
				switch(dnaPiece) {
				case 'A' : conTmp[0]++; break;
				case 'C' : conTmp[1]++; break;
				case 'G' : conTmp[2]++; break;
				case 'T' : conTmp[3]++; break;
				}
			}
			//조건 검사
			if(con[0] > conTmp[0] || con[1] > conTmp[1] || con[2] > conTmp[2] || con[3] > conTmp[3]) continue;
			ans++;
		}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static char[] dnaArray;
	static int[] conWindow;
	static int[] con;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int S = sc.nextInt(); // 문자열의 길이
		int P = sc.nextInt(); // 부분문자열의 길이
		String dna = sc.next();
		dnaArray = dna.toCharArray();
		con = new int[4]; //A C G T의 조건 개수
		conWindow = new int[4]; //슬라이딩 윈도우로 체크할 조건 개수
		for(int i = 0; i<4; i++) con[i] = sc.nextInt();
		int ans = 0;
		
		firstEdit(P);
		for(int i = P; i<S; i++) {
			if(conCheck()) {
				ans++;
			}
			plusEdit(dnaArray[i]);
			minusEdit(dnaArray[i-P]);
		}
		if(conCheck()) ans++;
		sb.append(ans);
		System.out.print(sb.toString());
		sc.close();
	}
	
	static void firstEdit(int P) {
		for(int i = 0; i<P; i++) {
			switch(dnaArray[i]) {
			case 'A' : conWindow[0]++;
			break;
			case 'C' : conWindow[1]++;
			break;
			case 'G' : conWindow[2]++;
			break;
			case 'T' : conWindow[3]++;
			break;
			}
		}
	}
	
	static void plusEdit(char dnaPiece) {
		switch(dnaPiece) {
		case 'A' : conWindow[0]++;
		break;
		case 'C' : conWindow[1]++;
		break;
		case 'G' : conWindow[2]++;
		break;
		case 'T' : conWindow[3]++;
		break;
		}
	}
	
	static void minusEdit(char dnaPiece) {
		switch(dnaPiece) {
		case 'A' : conWindow[0]--;
		break;
		case 'C' : conWindow[1]--;
		break;
		case 'G' : conWindow[2]--;
		break;
		case 'T' : conWindow[3]--;
		break;
		}
	}
	
	static boolean conCheck() {
		for(int i = 0; i<4; i++) {
			if(con[i] > conWindow[i]) return false;
		}
		return true;
	}
	
}

---

코드 리뷰

• 특이하게 Map을 사용하여 풀이했다.
• map1은 부분 문자열의 성립 조건 ( 2 0 1 1 형태로 주어지는 ), map2는 슬라이딩 윈도우를 하면서 증감되는 ‘현재 범위의 DNA 문자열 카운트 횟수’ 이다.
• Map의 특성상 key값을 DNA 값으로, value를 카운팅 횟수로 설정해두면 확실히 덜 헷갈리고 코드는 간결해진다.isPossiblePassword() 에서 등장한이 코드는 뭔지 모르겠다. Map과 관련된 함수인 것 같은데, 아마도 위의 코드 동작 과정은(2) 불러온 key 값들은 x로 하나씩 iteration된다.(4) map2.get(x) ≥ map1.get(x) 는 각 A G C T key값에 대한 value 크기 비교로, 문제에서 요구하는 비밀번호로 사용할 조건을 충족시키는지, .count() == 4는 해당 조건을 만족하는 개수가 4개이면 true, 아니면 false를 반환한다.
• 로 보인다. Map에 이런 메소드가 있는지 처음 알았다. 익혀두면 유용하게 쓰일 듯.
• (3) → 이 후에는 조건과 반환 형태가 결정된다.
• (1) map2의 모든 key 값을 불러온다.
• map2.keySet().stream().filter(x -> map2.get(x)>=map1.get(x)).count() == 4;
• DNA 염기서열을 String으로 한번에 받고, 필요할 때마다 .charAt()함수로 꺼내 쓰는 것도 나쁘지 않아 보인다. 근데 이러면 메소드 호출이 많아져서 시간이 오래 걸리지 않나?

💡 풀이자 : kwonsg514, 메모리 : 167788KB, 시간 820ms

import java.io.*;
import java.util.*;

public class Main {
    static Map<Character, Integer> map1 = new HashMap<>();
    static Map<Character, Integer> map2 = new HashMap<>();
    static int count = 0;

    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 str = br.readLine();

        st = new StringTokenizer(br.readLine());
        map1.put('A', Integer.parseInt(st.nextToken()));
        map1.put('C', Integer.parseInt(st.nextToken()));
        map1.put('G', Integer.parseInt(st.nextToken()));
        map1.put('T', Integer.parseInt(st.nextToken()));
        map2.put('A', 0);
        map2.put('C', 0);
        map2.put('G', 0);
        map2.put('T', 0);

        //Initial setting
        for(int i=0; i<=P-2; i++)
            if(isACGT(str.charAt(i))) map2.put(str.charAt(i), map2.get(str.charAt(i))+1);

        int lp = 0; int rp = P-2;
        while (rp<S-1){
            rp++;
            if(isACGT(str.charAt(rp))) map2.put(str.charAt(rp), map2.get(str.charAt(rp))+1);

            if (isPossiblePassword()) count++;

            if(isACGT(str.charAt(lp))) map2.put(str.charAt(lp), map2.get(str.charAt(lp))-1);
            lp++;
        }
        System.out.println(count);
    }

    // Methods
    static boolean isACGT(char c) {
        return (c == 'A' || c == 'C' || c == 'G' || c == 'T');
    }

    static boolean isPossiblePassword() {
        return map2.keySet().stream().filter(x -> map2.get(x)>=map1.get(x)).count() == 4;
    }
}

 

• 로직은 나랑 비슷하다.
• 다만 이 사람은 비트 마스킹이라던가, 아스키 코드를 좀 더 잘 활용하는 것으로 보인다.

💡 풀이자 : jeuk817 메모리 : 20528KB, 시간 188ms

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int s;
	static int p;
	static String dnaString;
	static int condition = 0;
	final static int FULLFILLED_CONDITION = (1 << ('A' & 31)) + (1 << ('C' & 31)) + (1 << ('G' & 31)) + (1 << ('T' & 31));
	static int[] acgtCondition = new int['Z' + 1];
	static int[] currCondition = new int['Z' + 1];
	static char[] acgt = {'A', 'C', 'G', 'T'};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		/* set input */
		s = Integer.parseInt(st.nextToken());
		p = Integer.parseInt(st.nextToken());
		dnaString = br.readLine();
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < 4; i++) {
			char alphabet = acgt[i];
			acgtCondition[alphabet] = Integer.parseInt(st.nextToken());
			if(acgtCondition[alphabet] == 0) condition |= 1 << (alphabet & 31);
		}
		/* /set input */
		
		// set current condition
		for(int i = 0; i < p; i++) {
			currCondition[dnaString.charAt(i)]++;
		}
		checkCurrCondition();
		
		// count available passwords
		int count = condition == FULLFILLED_CONDITION ? 1 : 0;
		int startIdx = 0, endIdx = p - 1;
		while(++endIdx < s) {
			// remove
			char removeAlphabet = dnaString.charAt(startIdx++);
			if(currCondition[removeAlphabet] == acgtCondition[removeAlphabet])
				condition &= ~(1 << (removeAlphabet & 31));
			currCondition[removeAlphabet]--;
			
			// add
			char addAlphabet = dnaString.charAt(endIdx);
			currCondition[addAlphabet]++;
			if(currCondition[addAlphabet] == acgtCondition[addAlphabet])
				condition |= 1 << (addAlphabet & 31);
			
			if(condition == FULLFILLED_CONDITION) count++;
		}
		System.out.println(count);
		
		br.close();
	}
	
	static void checkCurrCondition() {
		for(int i = 0; i < 4; i++) {
			char alphabet = acgt[i];
			if(currCondition[alphabet] >= acgtCondition[alphabet]) condition |= 1 << (alphabet & 31);
			else condition &= ~(1 << (alphabet & 31));
		}
	}
}

---

Conclusion

• Map에 관련된 흥미로운 메소드를 알게 되었다.
• 숫자와 알파벳에 관련된 아스키 코드는 기본적으로 외워두면 쓸모가 많을 것 같다.