[Java] 문제 009 (백준 12891번)

문제

DNA 비밀번호

설명

 

 

교재 풀이

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

public class P12891_DNA비밀번호 {
  static int checkArr[];
  static int myArr[];
  static int checkSecret;

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(bf.readLine());
    int S = Integer.parseInt(st.nextToken());
    int P = Integer.parseInt(st.nextToken());
    int Result = 0;
    char A[] = new char[S];
    checkArr = new int[4];
    myArr = new int[4];
    checkSecret = 0;
    A = bf.readLine().toCharArray();
    st = new StringTokenizer(bf.readLine());
    for (int i = 0; i < 4; i++) {
      checkArr[i] = Integer.parseInt(st.nextToken());
      if (checkArr[i] == 0)
        checkSecret++;
    }
    for (int i = 0; i < P; i++) { //초기 P부분 문자열 처리 부분
      Add(A[i]);
    }
    if (checkSecret == 4)
      Result++;
    // 슬라이딩 윈도우 처리 부분
    for (int i = P; i < S; i++) {
      int j = i - P;
      Add(A[i]);
      Remove(A[j]);
      if (checkSecret == 4)  // 4자리 수에 대한 크기가 모두 충족되었을 때는 유효한 비밀번호
        Result++;
    }
    System.out.println(Result);
    bf.close();
  }

  private static void Add(char c) { //새로 들어온 문자를 처리해주는 함수
    switch (c) {
    case 'A':
      myArr[0]++;
      if (myArr[0] == checkArr[0])
        checkSecret++;
      break;
    case 'C':
      myArr[1]++;
      if (myArr[1] == checkArr[1])
        checkSecret++;
      break;
    case 'G':
      myArr[2]++;
      if (myArr[2] == checkArr[2])
        checkSecret++;
      break;
    case 'T':
      myArr[3]++;
      if (myArr[3] == checkArr[3])
        checkSecret++;
      break;
    }
  }

  private static void Remove(char c) { //제거되는  문자를 처리해주는 함수
    switch (c) {
    case 'A':
      if (myArr[0] == checkArr[0])
        checkSecret--;
      myArr[0]--;
      break;
    case 'C':
      if (myArr[1] == checkArr[1])
        checkSecret--;
      myArr[1]--;
      break;
    case 'G':
      if (myArr[2] == checkArr[2])
        checkSecret--;
      myArr[2]--;
      break;
    case 'T':
      if (myArr[3] == checkArr[3])
        checkSecret--;
      myArr[3]--;
      break;
    }
  }
}

 

문제에서 입력받는 것 중에, a, g, c, t 각각 특정 숫자 이상이어야 한다는 조건을 입력받음

즉 a, g, c, t 각각을 따로따로 보고, 각 조건을 만족했다는 걸 표현할 때

=> checkSecret이란 변수를 사용했네. a g c t 중 a 조건을 만족했다면 이 변수는 1이 되는 식으로 

=> 그렇게 한 후 checkSecret이 4가 될 때마다 cnt를 증가시킨 거고

 

 

 

내 풀이 (틀림) => 24.6.1자 푼 틀린 코드

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

public class Main
{
	public static void main(String[] args) throws IOException{
// 		DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 
// 		임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용
		
// 		예
// 		    DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4
// 		    부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다
// 		    이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다.
// 		    하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.
		
// 		 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램
		 
// 		첫 번째 줄에 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000)
//         두번 째 줄에는 임의로 만든 DNA 문자열이 주어진다.
//         세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다.
//             각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.
        
//         입력
//             9 8
//             CCTGGATTG
//             2 0 1 1
//                 s가 9, p가 8 
//                 a가 2, c가 0, g가 1, t가 1 이상 있어야 cnt++ 
//         출력
//             0 
//         접근법
//             슬라이딩 윈도우를 사용해야 함을 아는 상태 
//                 dna 문자열을 배열로 받음 
//                 투 포인터인데, 길이가 4로 유지되는 거임 
//                 처음 투 포인터 사이에 어떤 문자열이 있는지 그 개수를 카운트하는 배열도 따로 만들고 거기에 개수 넣기 
//                 그 다음 반복문 돌리면서 포인터 계속 하나씩 오른쪽으로 옮기면서
//                     들어오는 원소는 카운트 배열에 개수 반영해주고, 빠지는 원소도 반영해서 카운트 배열에 반영하기 
//                     그리고 최소 조건 만족시킬 때마다 cnt++해주기 
//                     ei가 문자열 배열 끝을 가리키면 반복 종료
//         슈도코드 
//             s와 p를 입력받음 
//             문자열을 배열로 입력받음  -> br.readLine().toCharArray()로 문자 배열로 받기 
//             require 배열로 a,c,g,t 최소 개수 입력받음 
            
//             cnt 변수 초기화 
//             반복문 
//                 si, ei 초기화 
//                 반복될 때마다 현재 si, ei 가리키는 거 count 배열에서 넣고 빼고 해주고 
//                 count 배열로 초기화된 슬라이딩 윈도우의 a,c,g,t 개수 확인하고 넣기
//                 현재 count 배열과 require 배열을 비교해서 조건 만족하면 cnt++해주기 
                
        
        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()); //  부분 문자열 개수, 슬라이딩 윈도우 범위
        
        char[] arr=br.readLine().toCharArray();// 안 되면 StringTokenizer로 해주고, 잡코드니까 나중에 신경 쓰기 
        
        // require 배열로 a,c,g,t 최소 개수 입력받음 
        int[] require=new int[4];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<4;i++){
            require[i]=Integer.parseInt(st.nextToken());
        }
        
        // 초기화 부분 
        long cnt=0;
        int si=0, ei=p-1;
        int[] count=new int[4];
        //현재 투 포인터 범위에서 문자 개수를 세서 count 배열에 담음
        for(int i=si;i<=ei;i++){
            if(arr[i]=='A'){
                count[0]++;
            }
            else if(arr[i]=='C'){
                count[1]++;
            }
            else if(arr[i]=='G'){
                count[2]++;
            }
            else if(arr[i]=='T'){
                count[3]++;
            }
        }
        
        
        //핵심 로직 
        while(ei<arr.length-1){
            // count 배열이 require에 만족하면 cnt ++해줘야 하는데 
            //     어떻게 만족함을 아는가?
            //     각 인덱스별로 원소값을 비교해주는 거지 
            
            if(count[0]>=require[0] && count[1]>=require[1] && count[2]>=require[2] && count[3]>=require[3]){
                cnt++;
            }
            
            // 반복될 때마다 현재 si, ei 가리키는 거 count 배열에서 넣고 빼고 해주고 
            // si 처리부터
            if(arr[si]=='A'){
                    count[0]--;
                }
            else if(arr[si]=='C'){
                count[1]--;
            }
            else if(arr[si]=='G'){
                count[2]--;
            }
            else if(arr[si]=='T'){
                count[3]--;
            }
            si++;
            
            // ei 처리 
            ei++;
            if(arr[ei]=='A'){
                count[0]++;
            }
            else if(arr[ei]=='C'){
                count[1]++;
            }
            else if(arr[ei]=='G'){
                count[2]++;
            }
            else if(arr[ei]=='T'){
                count[3]++;
            }

        }
        
        System.out.println(cnt);
            
	}
	
}
// 디버그를 해보자
//     처음에 117번에 배열 인덱스 초과 에러가 났음 
//     ei++ 후에 arr에 접근할 때 문제가 생긴건가? 
//         arr는 예제에선 크기가 4임. S가 4니까 
//         ei는 초기화가 p-1임. 즉 1이 되는데, 
    //     밎이. ei는 1이 됨을 확인했어 
    //     혹시 while(ei<arr.length)가 끝자락일 때 오류난 거 아니야?
    //         arr.length는 4야 
    //         ei가 3일 때도 반복문 돌지
    //         그러네, 이 때 범위 오류가 난 거네 
    // 그보다 다른 문제를 찾은 것 같은데
    //     현재 투 포인터 범위에서 문자 개수를 세서 count 배열에 담음
    //     요 부분 코드가 계속 반복될 때마다 실행되면 내 의도와 다른 결과를 나을 것 같은데 
    // 잠정 결론 
    //     아, 이거 고치려면 시간 걸리는데, 제한 시간 초과한다 
    //     물론 시간 초과해서 하려고 하면 할 수 있음
    //     해볼까? 
// 왜 예제 2을 입력했더니 출력이 1이 나오지?

 

1시간 제한 걸고 풀었는데, 처음엔 배열 인덱스 오류나서 고쳤고, 

다시 보니까 뭔가 의도하지 않은 부분이 있어서 고친 후(코드 블록 밑에 주석 보면 나옴)

예제 2로 입력 후 확인했다

 

그 결과 기대 출력값은 2인데, 답이 1이 나왔다

왜 그럴까?

 

보니까 cnt++해주기 위해 조건 검사하는 if문 위치가 이상하네

내 코드에서는 이게 반복문 제일 위에 있으니까

그 밑에 있는 코드로 si, ei 옮기고 난 후에 변화한 count 배열이 

cnt 조건을 만족하는지 확인 못하고 

반복문 조건 만족 못해서 빠져나가네.

반복문 마지막 끝자락에서 문제가 생겨서, 마지막 부분이 누락되었네 

 

 

 

gpt가 고친 코드(맞음)=> 24.6.1자 내가 푼 틀린 코드를 gpt가 수정해서 맞은 코드

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

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()); // 부분 문자열 개수, 슬라이딩 윈도우 범위

        char[] arr = br.readLine().toCharArray();
        
        // require 배열로 A, C, G, T 최소 개수 입력받음 
        int[] require = new int[4];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            require[i] = Integer.parseInt(st.nextToken());
        }
        
        // 초기화 부분 
        long cnt = 0;
        int si = 0, ei = p - 1;
        int[] count = new int[4];
        
        // 현재 투 포인터 범위에서 문자 개수를 세서 count 배열에 담음
        for (int i = si; i <= ei; i++) {
            if (arr[i] == 'A') {
                count[0]++;
            } else if (arr[i] == 'C') {
                count[1]++;
            } else if (arr[i] == 'G') {
                count[2]++;
            } else if (arr[i] == 'T') {
                count[3]++;
            }
        }
        
        // 초기 윈도우에서 조건을 검사
        if (count[0] >= require[0] && count[1] >= require[1] && count[2] >= require[2] && count[3] >= require[3]) {
            cnt++;
        }
        
        // 핵심 로직 
        while (ei < arr.length - 1) {
            // si 처리부터
            if (arr[si] == 'A') {
                count[0]--;
            } else if (arr[si] == 'C') {
                count[1]--;
            } else if (arr[si] == 'G') {
                count[2]--;
            } else if (arr[si] == 'T') {
                count[3]--;
            }
            si++;
            
            // ei 처리 
            ei++;
            if (arr[ei] == 'A') {
                count[0]++;
            } else if (arr[ei] == 'C') {
                count[1]++;
            } else if (arr[ei] == 'G') {
                count[2]++;
            } else if (arr[ei] == 'T') {
                count[3]++;
            }
            
            // count 배열이 require에 만족하면 cnt ++해주기
            if (count[0] >= require[0] && count[1] >= require[1] && count[2] >= require[2] && count[3] >= require[3]) {
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
}

 

지피티가 수정해 준 거 보니까 딴 건 내 코드와 다 똑같고 

그냥 cnt 증가하기 위해 조건 확인하는 if문 위치만 수정한 거네

역시 gpt, 나보다 코딩 잘해