treecode

문제

DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다.

임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용한다.

단, 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다

그리고 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

부분 문자열의 길이는 고정적이기 때문에 일정 간격으로 옮겨가면서 비밀번호가 될 수 있는지 체크를 해야 한다.

슬라이딩 윈도우로 푼다.

슬라이딩 윈도우를 한칸씩 움직이면서 left 문자를 빼주고 right 문자를 더해주는 식으로 하면 문자열마다 A, C, G, T 문자를 새로 구할 필요가 없다.

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

import static java.lang.System.in;

public class Main {
    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(in));
        final StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        final char[] dnaCharacters = br.readLine().toCharArray();

        st = new StringTokenizer(br.readLine());
        DnaPassword password = new DnaPassword(
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken())
        );

        int lt = 0;
        int rt = 0;
        int count = 0;

        while (rt < P) {
            password.add(dnaCharacters[rt++]);
        }

        while (rt < dnaCharacters.length) {
            if (password.canCreatePassword()) {
                ++count;
            }
            password.remove(dnaCharacters[lt++]);
            password.add(dnaCharacters[rt++]);
        }

        if (password.canCreatePassword()) {
            ++count;
        }

        System.out.println(count);
    }

    static class DnaPassword {
        final int[] standardCounts;
        final int[] countOfcharacter = new int[4];

        DnaPassword(int A, int C, int G, int T) {
            standardCounts = new int[]{A, C, G, T};
        }

        public void add(char ch) {
            countOfcharacter[indexOf(ch)] += 1;
        }

        public void remove(char ch) {
            countOfcharacter[indexOf(ch)] -= 1;
        }

        private int indexOf(char ch) {
            if (ch == 'A') {
                return 0;
            }
            if (ch == 'C') {
                return 1;
            }
            if (ch == 'G') {
                return 2;
            }
            if (ch == 'T') {
                return 3;
            }

            throw new IllegalArgumentException();
        }

        public boolean canCreatePassword() {
            return standardCounts[0] <= countOfcharacter[0] &&
                    standardCounts[1] <= countOfcharacter[1] &&
                    standardCounts[2] <= countOfcharacter[2] &&
                    standardCounts[3] <= countOfcharacter[3];
        }
    }
}

문제

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다.

 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성

N개의 재료는 각각 고유 번호를 가지고 있고 두 재료의 고유 번호를 더해서 M이 되면 갑옷이 만들어진다.

문제의 예시를 보면 [2, 7]과 [4, 5]으로 2개가 만들어진다.

6 //N
9 //M
2 7 4 1 5 3 // 고유 번호

2개의 고유 번호를 더해서 확인해야 되기 때문에 일일이 더하면서 확인하면 대략 N^2번을 체크할 것 같다.

M에서 첫번째 재료의 고유 번호를 뺀 값이 있으면 갑옷을 만들 수 있기 때문에 Set을 사용해서 페어가 있는지 확인하면 좋을 것 같다.

Set<Integer> elements = new HashSet<>();
List<Integer> numbers = new ArrayList<>();
int count = 0;

while (st.hasMoreTokens()) {
    int value = Integer.parseInt(st.nextToken());
    elements.add(value);
    numbers.add(value);
}

for (Integer num : numbers) {
    if (elements.remove(num) && elements.remove(M - num)) {
        ++count;
    }
}

고유한 번호이기 때문에 정렬을 하고 양쪽 끝에서 투 포인터로 숫자를 비교하면서 값을 구할 수도 있다.

어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 구하는 문제

연속된 수의 조합이고 N의 범위가 크기 때문에 투 포인터(lt, rt)를 사용해서 조합의 합이 N보다 작으면 rt를 증가, N보다 크면 lt를 증가 시키면서 이동한다.

곧바로 떠오르는 고려할 점은 어디까지 수를 체크 할 것이냐인데 최소한의 연속된 수로 나타낼 수 있는 경우는 N의 절반이 될 것이다.

연속된 숫자가 1개인 경우도 포함되기 때문에 자기 자신도 포함하면 기본값은 1이 될 것

int N = Integer.parseInt(br.readLine());
int end = N / 2;
int count = 1;
int lt = 1;
int rt = 2;
int sum = lt + rt;

while (lt <= end) {
    if (sum > N) {
        sum -= lt;
        ++lt;
    }
    if (sum == N && rt != N) {
        ++count;
    }
    if (sum <= N) {
        ++rt;
        sum += rt;
    }
}

컴퓨터의 개수(n)와 컴퓨터간 네트워크 연결 정보(computers)가 주어졌을때 네트워크의 개수를 구하는 문제로 아래의 경우 A와 B가 연결 되어 있고, C는 따로 있으므로 총 네트워크 수는 2개가 된다.

예전에 푼 문제를 다시 보니 전에는 문제를 어떤식으로 풀까 하는 생각을 별로 안하고 풀었던 것 같다.

class Solution {
    static int L;
    static boolean flag = false;
    static int[][] ch;

    public int solution(int n, int[][] computers) {
        ch = new int[n][n];
        L = 1;
        for (int i = 0; i < n; i++) {
            flag = false;
            BFS(i, n, computers);
            if (flag)
                L++;
        }
        return L - 1;
    }

    private static void BFS(int i, int n, int[][] computers) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        while (!queue.isEmpty()) {
            int p = queue.poll();
            for (int j = 0; j < n; j++) {
                if (computers[p][j] == 1 && ch[p][j] == 0) {
                    flag = true;
                    ch[p][j] = L;
                    ch[j][p] = L;
                    queue.offer(j);
                }
            }
        }
    }

}

다시 푼 코드인데 0 ~ n-1개 컴퓨터를 돌면서 network[] 체크가 안되어있으면 새로운 네트워크로 보고 count를 증가시킨다.

dfs는 해당 컴퓨터에 연결된 다른 컴퓨터를 체크하면서 network[]를 true로 바꾼다.

class Solution {
    static boolean[] network;
    static int[][] computers;
    
    public int solution(int n, int[][] computer) {
        computers = computer;
        network = new boolean[n];
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (!network[i]) {
                count++;
            }
            dfs(n, i);
        }
        
        return count;
    }
    
    private void dfs(int n, int i) {
        network[i] = true;
        
        for (int j = 0; j < n; j++) {
            if (!network[j] && computers[i][j] == 1) {
                dfs(n, j);
            }
        }
    }
}