[코딩테스트] [12891] DNA비밀번호 & [2118] 두개의탑

[12891] DNA비밀번호

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

512 MB

28574

10363

7546

35.011%

문제

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 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’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

입력

첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000)

두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.

세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.

문제풀이

문제를 요약하자면 길이 |S|의 DNA 문자열에서 길이가 |P|인 부분문자열 중{'A', 'C', 'G', 'T'}를 각 개수 이상 가진 비밀번호의 개수를 구하라. 부분문자열의 등장 위치가 다르다면 부분문자열이 같다고 해도 다른 문자열로 취급한다.

**// 예제
16 4
ACGTACGTAACCGGTT
1 1 1 1**

위의 예제를 생각해보면 답은 총 6이 나온다.

그러면 길이가 S인 문자열 중 길이가 P인 부분 문자열의 개수를 구해 보면

S - P + 1이 된다.

그러면 전체적으로 문자열을 순회하면서 하나씩 비교를 해주고 값이 있을때마다 증가를 시켜주면 정답이 나온다.

        // 비밀번호의 종류 수를 저장할 변수
        int ans = 0;

        // 부분 문자열을 반복하면서 카운트
        for (int l = 0; l <= S - P; l++) {
            int[] count = new int[4]; // A, C, G, T의 개수를 저장할 배열

            // 부분 문자열의 각 문자를 반복하면서 카운트
            for (int i = 0; i < P; i++) {
                char currentChar = sequence.charAt(l + i);
                if (currentChar == 'A') count[0]++;
                else if (currentChar == 'C') count[1]++;
                else if (currentChar == 'G') count[2]++;
                else if (currentChar == 'T') count[3]++;
            }

            boolean isValid = true; // 유효성 플래그 초기화
            for (int i = 0; i < 4; i++) {
                if (count[i] < minimumCount[i]) isValid = false; // 최소 개수 조건 확인
            }

            if (isValid) ans++; // 유효한 경우 카운트 증가
        }

하지만 시간복잡도가 O(S * P)가 나오게 되고 결국 시간 초과가 발생한다.

그러면 문자가 나올 때 개수를 세는 방식을 알아보자.

1. 문자를 그대로 index로 사용 (ASCII)

int[] count = new int[128];
count[S[i]]++;

2. 문자를 축약된 index로 변환하는 함수

static int baseToIndex(char alp) {
	if (alp == 'A') return 0;
	else if ( alp == 'C') return 1;
}

count[baseToIndex(S[i])++;

3. 문자를 축약된 index로 변환하는 배열(ASCII)

int[] baseToIndex = new int[128];
baseToIndex['A'] = 0;, baseToIndex['C'] = 1; ...
count[baseToIndex[S[i]]]++;

4. 문자를 축약된 index로 변환하는 Map

Map<Character, Integer> baseToIndex = new HashMap<>();
baseToIndex.put('A', 0); baseToIndex.put('C', 1);
count[baseToIndex.get(S[i])]++;

누적합을 이용한 풀이 방법

이 문제는 누적합으로 풀 수 있다.

각 알파벳에 대한 누적합을 사용하면 부분문자열의 구성을 확인하는 시간복잡도를 줄일 수 있다.

import java.util.Scanner;

public class Main {
    public static int baseToIndex(char alp) {
        if (alp == 'A') return 0;
        else if (alp == 'C') return 1;
        else if (alp == 'G') return 2;
        else if (alp == 'T') return 3;
        return -1; // 잘못된 문자가 들어올 경우
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 첫 번째 줄: S와 P 입력받기
        int S = sc.nextInt();
        int P = sc.nextInt();
        sc.nextLine(); // 줄바꿈 문자 처리

        // 두 번째 줄: DNA 문자열 입력받기
        String sequence = sc.nextLine();

        // 세 번째 줄: 최소 개수 입력받기
        int[] minimumCount = new int[4]; // A, C, G, T의 최소 개수
        for (int i = 0; i < 4; i++) {
            minimumCount[i] = sc.nextInt();
        }

        int[][] accCount = new int[S + 1][4];
        for (int i = 1; i <= S; i++) {
            for (int j = 0; j < 4; j++)
                accCount[i][j] = accCount[i - 1][j];

            int index = baseToIndex(sequence.charAt(i - 1));
            accCount[i][index]++;
        }

        // 비밀번호의 종류 수를 저장할 변수
        int ans = 0;

        // 부분 문자열을 반복하면서 카운트
        for (int l = 0; l <= S - P; l++) { // S - P로 수정
            boolean isValid = true;
            // 누적합을 사용
            for (int i = 0; i < 4; i++) {
                int count = accCount[l + P][i] - accCount[l][i];
                if (count < minimumCount[i]) {
                    isValid = false;
                    break; // 조건을 만족하지 않으면 더 이상 확인할 필요 없음
                }
            }

            if (isValid) ans++; // 유효한 경우 카운트 증가
        }

        // 결과 출력
        System.out.println(ans);
    }
}

위의 코드로 제출을 한다면 시간복잡도 O(s)로 맞는 것을 확인할 수 있다.

투 포인터 문제 풀이

[i:i+P-1] 문자열의 구성을 안다면 [i+1:i+P] 문자열의 구성을 셀 때 공통된 부분을 그대로 사용할 수 있다.

즉, 0~3 까지의 문자열을 알면 1~4중에 1~3의 문자열을 알고 있으니 0을 제외해주고 4만 알면 된다.

아래 이미지를 보면 이해가 더욱 쉽다.

그리고 만약 추가되는 문자가 같은 값이라면 구성이 변하지 않는다.

즉, 앞에서부터 차례로 길이가 |P|인 부분문자열을 확인하면 이전 부분문자열의 구성을 통해 다음 부분문자열의 구성을 O(1)만에 구할 수 있다.

이렇게 공통된 구간의 정보를 재사용하는 것, 두 포인터를 같은 방향으로 움직이며 구간의 정보를 재사용하는 것을 Sliding Window 라고도 한다.

자 그러면 이제 코드로 변환해보자.

0. 입력받기 및 minimumBaseCount 정하기

        Scanner sc = new Scanner(System.in);

        int S = sc.nextInt();
        int P = sc.nextInt();
        char[] sequence = sc.next().toCharArray();
        
        int[] minimumBaseCount = new int[4];
        for (int i = 0; i < 4; i++)
            minimumBaseCount[i] = sc.nextInt();

1. 맨 처음 문자열 구하기

첫 부분문자열을 미리 계산하자. 슬라이딩 윈도우를 하기위해 처음을 구해야 한다.

       int[] currentBaseCount = new int[4];
        for (int i = 0; i < P; i++)
            currentBaseCount[baseToIndex(sequence[i])]++;

2. 모든 경우의 수 탐색하며 투 포인터 사용

       for (int i = 1; i <= S - P; i++) {
            currentBaseCount[baseToIndex(sequence[i - 1])]--;
            currentBaseCount[baseToIndex(sequence[i + P - 1])]++;
            if (isValidSequence(currentBaseCount, minimumBaseCount))
                ans++;
        }

3. 문자를 받아 Count하는 함수 생성

    static int baseToIndex(char alp) {
        if (alp == 'A') return 0;
        else if (alp == 'C') return 1;
        else if (alp == 'G') return 2;
        else if (alp == 'T') return 3;
        return -1;
    }

4. 최소 개수 조건에 부합하는 지 비교하는 함수 생성

   static boolean isValidSequence(int[] baseCount, int[] minimumBaseCount) {
        for (int i = 0; i < baseCount.length; i++)
            if (baseCount[i] < minimumBaseCount[i])
                return false;
        return true;
		    }

전체코드

import java.util.Scanner;

public class Main {
    public static int baseToIndex(char alp) {
        if (alp == 'A') return 0;
        else if (alp == 'C') return 1;
        else if (alp == 'G') return 2;
        else if (alp == 'T') return 3;
        return -1; // 잘못된 문자가 들어올 경우
    }

    public static boolean isVaild(int[] baseCount, int[] minimumBaseCount) {
        for (int i = 0; i < baseCount.length; i++)
            if (baseCount[i] < minimumBaseCount[i])
                return false;
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 첫 번째 줄: S와 P 입력받기
        int S = sc.nextInt();
        int P = sc.nextInt();
        sc.nextLine(); // 줄바꿈 문자 처리

        // 두 번째 줄: DNA 문자열 입력받기
        char[] sequence = sc.next().toCharArray();

        // 세 번째 줄: 최소 개수 입력받기
        int[] minimumCount = new int[4];
        for (int i = 0; i < 4; i++) {
            minimumCount[i] = sc.nextInt();
        }

        int[] currentBaseCount = new int[4];
        for (int i = 0; i < P; i++)
            currentBaseCount[baseToIndex(sequence[i])]++;

        // 비밀번호의 종류 수를 저장할 변수
        int ans = 0;

        // 부분 문자열을 반복하면서 카운트
        for (int i = 1; i <= S - P; i++) {
            currentBaseCount[baseToIndex(sequence[i - 1])]--;
            currentBaseCount[baseToIndex(sequence[i + P - 1])]++;
            if (isVaild(currentBaseCount, minimumCount))
                ans++;
        }
        // 결과 출력
        System.out.println(ans);
    }
}

시간복잡도

이 알고리즘의 시간복잡도는 투 포인터를 사용했기에 O(S)이다

[2118] 두개의탑

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

3108

1140

834

40.505%

문제

1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.

지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.

연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 답을 출력한다.

문제풀이

이 문제는 원형으로 연결된 N개의 지점 중 두 곳에 탑을 세울 때 가능한 거리의 최댓값을 구하는 문제이다.

예제 1를 보면서 문제를 이해해보자. 두 개의 탑의 시계/반시계 방향 중 짧은 쪽이 거리가 된다.

0:3 까지의 거리를 기준으로 고르면 시계 방향은 1,2,3 을 지나니 총 6이 된다.

반시계 방향은 5,4를 지나 총 9가 된다. 그 중 짧은 쪽이 6이 된다.

모든 경우의 수를 구하는 풀이

반복문을 이용하여 하나의 지점을 고르고 두 번째 지점까지 이동할 지점의 개수를 구해보자.

아래 코드는 Modular 연산을 통해 배열을 환열처럼 사용할 수 있게 한다.

시계 방향 거리와 반시계 방향 거리를 계산하여 최소거리계산을 구해주는 방법이다.

        // 모든 시작점에 대해 반복
        for (int i = 0; i < N; i++) {
            for (int clockCount = 1; clockCount < N; clockCount++) {
                int distClockWise = 0;
                // 시계 방향 거리 계산
                for (int j = 0; j < clockCount; j++) {
                    distClockWise += distance[(i + j) % N];
                }

                int distCounterClockWise = 0;
                // 반시계 방향 거리 계산
                for (int j = 1; j <= N - clockCount; j++) {
                    distCounterClockWise += distance[(i - j + N) % N];
                }

                // 최소 거리 계산
                int dist = Math.min(distClockWise, distCounterClockWise);
                ans = Math.max(ans, dist); // 최대 거리 업데이트
            }
        }

하지만 이 코드로 문제를 푼다면 시간복잡도 O(N^3)d으로 시간초과를 맞이한다.

선형자료구조를 이용해 환형구조를 나타낼 때 배열을 2배로 늘리면 인덱스 관리가 쉬워질 수 있다.

모듈러 연산을 하지 않고 계산이 가능하다.

코드로 봐보면 모듈러 없이 직접 계산이 가능한것을 볼 수 있다.

        int[] distance = new int[N]; // 거리 배열
        int distanceSum = 0;

        // 거리 배열 입력받기
        for (int i = 0; i < N; i++) {
            distance[i] = sc.nextInt(); // 거리 입력
            distanceSum += distance[i]; // 총 거리 합계 계산
        }

        int ans = 0; // 최대 거리 초기화

        // 모든 시작점에 대해 반복
        for (int i = 0; i < N; i++) {
            for (int clockCount = 1; clockCount < N; clockCount++) {
                int distClockWise = 0;
                // 시계 방향 거리 계산
                for (int j = 0; j < clockCount; j++) {
                    distClockWise += distance[i + j]; // 모듈러 없이 직접 인덱스 사용
                }

                int distCounterClockWise = distanceSum - distClockWise; // 반시계 방향 거리 계산
                int dist = Math.min(distClockWise, distCounterClockWise); // 최소 거리 계산
                ans = Math.max(ans, dist); // 최대 거리 업데이트
            }
        }

환형 구조에서의 구간합은 누적합 풀이가 가능하다.

        int[] accDist = new int[N + 1]; // 누적 거리 배열
        int distanceSum = 0;

        // 거리 배열 입력받기 및 누적 거리 계산
        for (int i = 1; i <= N; i++) {
            distance[i - 1] = sc.nextInt(); // 거리 입력
            accDist[i] = accDist[i - 1] + distance[i - 1]; // 누적 거리 계산
            distanceSum += distance[i - 1]; // 총 거리 합계
        }

        int ans = 0; // 최대 거리 초기화

        // 모든 시작점에 대해 반복
        for (int i = 1; i <= N; i++) {
            for (int clockCount = 1; clockCount < N; clockCount++) {
                int targetIndex = i + clockCount - 1;
                int distClockWise = accDist[Math.min(N, targetIndex)] - accDist[i - 1];

                if (targetIndex > N) {
                    distClockWise += accDist[targetIndex - N]; // 시계 방향 거리 추가
                }

                int distCounterClockWise = distanceSum - distClockWise; // 반시계 방향 거리 계산
                int dist = Math.min(distClockWise, distCounterClockWise); // 최소 거리 계산
                ans = Math.max(ans, dist); // 최대 거리 업데이트
            }
        }

하지만 이 방법도 O(N^2)이 나오기에 시간초과가 발생한다.

투 포인터 풀이

그렇다면 각 지점에 대해 가장 먼 지점은 어떻게 나타내는지보 보자.

 

각 지점에 대해 가장 먼 지점은 절반의 거리를 경계로 가장 가까운 반시계방향(A) 혹은 시계방향(B) 지점 중 min(DA, DB)가 더 큰 쪽이 된다

disti(A) = min(6, 9) = 6

disti(B) = min(10, 5) = 5

즉, 둘 중 더 큰쪽이 6이 i를 기준으로 최대값이 된다.

아래 이미지는 0을 기준으로 증가하여 최대값을 계산하는 부분이다.

기준선을 넘는 순간 반시계 방향이 더 가까워진다.

즉 (0,0), (0,1) (0,2) (0,3) (0,4) 중 가장 큰 값은 6이다.

그래서 절반을 기준으로 가장 가까운 둘 중 큰 값이 정답이 된다.

새로운 경계를 기준으로 A, B가 이동해야 한다.

distCWi(B) < distCCWi(B)라면 A, B를 시계방향으로 한 지점씩 옮긴다.

전체코드

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] distance = new int[N];
        int distanceSum = 0;
        for (int i = 0; i < N; i++) {
            distance[i] = sc.nextInt();
            distanceSum += distance[i];
        }

        int pairIndex = 1;
        int leftDistance = distance[0];
        int rightDistance = distanceSum - distance[0];
        int maxDistance = Math.min(leftDistance, rightDistance);
        for (int i = 0; i < N; i++) {
            while (leftDistance < rightDistance) {
                leftDistance += distance[pairIndex];
                rightDistance -= distance[pairIndex];
                pairIndex = (pairIndex + 1) % N;
            }
            maxDistance = Math.max(maxDistance, Math.min(leftDistance, rightDistance));

            leftDistance -= distance[i];
            rightDistance += distance[i];
        }
        System.out.println(maxDistance);
    }
}

시간복잡도

이 알고리즘의 시간복잡도는 O(N)이다