treecode

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다.

Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수 (그러한 수가 없는 경우에 오큰수는 -1)

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. 이 때, 차례대로 오큰수를 출력

오른쪽에 있으면서 가장 왼쪽에 있는 수는 자기보다 큰 수가 나오면 바로 찾아지는데 단순하게 계산하면 for문 2개를 돌리게 된다.

더 나은 방법을 생각해봤는데 떠오르지 않아 찾아보니 스택에 값이 아닌 인덱스를 활용해서 푸는 방법이 있었다.

stack에는 인덱스를 push 하는데 배열의 다음 값과 stack에서 peek을 한 인덱스에 해당하는 값을 비교해서 다음 값이 작을 경우에 해당 값의 인덱스를 stack에 push 한다. 그러다가 stack의 인덱스에 해당하는 값보다 큰 값을 만나면 오큰수로 체크하는 식으로 계산하면 된다. 처음에 오큰수를 기록하는 answer 배열을 -1로 초기화하기 때문에 오큰수가 없는 경우는 따로 체크할 필요가 없다.

int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());

Stack<Integer> stack = new Stack<>();
int[] arr = new int[N];
int[] answer = new int[N];

for (int i = 0; i < N; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
}

Arrays.fill(answer, -1);

stack.push(0);
for (int i = 1; i < arr.length; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
        answer[stack.pop()] = arr[i];
    }
    stack.push(i);
}

for (int num : answer) {
    sb.append(num).append(" ");
}

System.out.println(sb);

문제

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.

이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하시오

문제의 예시를 보면 "4 3 6 8 7 5 2 1" 가 주어지면 stack을 사용해서 해당 수열을 만들 수 있는지 구하는 것이다.

stack에는 오름차순으로 push를 해야하는 규칙이 있기 때문에 1, 2, 3, 4.. 순서로 push를 하고 4가 push 되었을때 pop을 2번 하면 4, 3이 나오게 되어서 문제의 예시대로 4, 3을 만들 수 있다.

먼저 입력을 받아서 기존의 배열과 오름차순으로 정렬이 된 배열을 만든다.

그리고 정렬이 된 배열에서 하나씩 push를 하다가 기존의 배열 순서에 맞는 숫자가 나오면 pop을 하는 식으로 구현하면 될 것 같다.

int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] sortedArr = new int[N];
Stack<Integer> stack = new Stack<>();

for (int i = 0; i < N; i++) {
    int value = Integer.parseInt(br.readLine());
    arr[i] = value;
    sortedArr[i] = value;
}

Arrays.sort(sortedArr);

int idx = 0;
for (int num : sortedArr) {
    sb.append("+").append("\n");
    stack.push(num);
    while (!stack.isEmpty() && stack.peek() == arr[idx]) {
        sb.append("-").append("\n");
        stack.pop();
        ++idx;
    }
}

if (!stack.isEmpty()) {
    System.out.println("NO");
    return;
}

System.out.println(sb);

문제

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;
    }
}

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