컴싸 공부방

애너그램은 단어 A가 주어졌을 때 문장을 이루는 알파벳을 바꿔서 다른 단어 B를 만들 수 있으면 A와 B를 애너그램이라고 한다.

예를 들어 A = abc라고 하면 B = abc, acb, bac, bca, cab, cba가 될 수 있다.

문제의 요점은 A와 B는 모두 같은 길이로 되어있는 구성이 같은 알파벳의 나열이라는 것이다. 그렇다면 순서와 상관없이 알파벳의 갯수만 체크하면 간단히 풀릴 것이다.

알파벳의 총 개수는 52개이며 아스키코드값에 의해  A = 65, B = 65, ... ,Z = 90, a = 97, b = 98, ..., z = 122가 된다.

해당 숫자들을 0~52까지 매핑 시킨 후, 갯수를 체크하면 된다.

다음은 전체 소스 코드이다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        while (n-- > 0) {
            int[] ana = new int[52];
            StringTokenizer st = new StringTokenizer(br.readLine());
            String s1 = st.nextToken();
            String s2 = st.nextToken();
            boolean result = true;

            if (s1.length() != s2.length()) {
                bw.write(s1 + " & " + s2 + " are NOT anagrams.\n");
                continue;
            }

            for (int i = 0; i < s1.length(); i++) {
                int c = s1.charAt(i);
                if (c >= 65 && c <= 90) {
                    ana[c - 65]++;
                } else if (c >= 97 && c <= 122) {
                    ana[c - 71]++;
                }
            }

            for (int i = 0; i < s2.length(); i++) {
                int c = s2.charAt(i);
                if (c >= 65 && c <= 90) {
                    ana[c - 65]--;
                } else if (c >= 97 && c <= 122) {
                    ana[c - 71]--;
                }
            }

            for (int i = 0; i < 52; i++) {
                if (ana[i] != 0) {
                    result = false;
                    break;
                }
            }
            if (result == true) {
                bw.write(s1 + " & " + s2 + " are anagrams.\n");
            } else {
                bw.write(s1 + " & " + s2 + " are NOT anagrams.\n");
            }
        }
        bw.flush();
        bw.close();
    }
}

계단 오르기는 마지막 계단까지 올라 갔을때 밟은 계단의 값을 합하였을 때 최대가 되는 값을 구하는 문제이다.

계단을 오를 때의 규칙은 다음과 같다.

• 규칙1. 계단은 한 번에 한 계단 씩 혹은 두 계단씩 오를 수 있다.
• 규칙2. 연속된 세 개의 계단을 밟아서는 안 된다. 단, 시작점은 포함되지 않는다.
• 규칙3. 마지막 도착 계단은 반드시 밟아야 한다.

이 규칙에 의해 각각의 계단들에 대한 가능한 경로들을 구해보았다.

4번째 계단(배열상 s[3])의 경우의 수를 보면 s[0] + s[2] + s[3] 혹은 s[0] + s[1] + s[3] 혹은 s[1] + s[3]의 경우가 가능하다.

전 단계의 계단을 보면 s[0] + s[1] + s[3] 혹은 s[1] + s[3]에 대한 경우의 수는 2번째 계단에서 구하였으며 해당 경우는 2칸을 건너 뛰어 왔을 경우에 해당 됩니다. 그렇다면 한칸 직전에서 올라온 것은 s[0] + s[2] + s[3]가 될텐데 이 경우는 규칙2에 의해서 s[0] (2칸 + 1칸의 경우에 해당)에 대한 경우를 구하면 된다.

해당 식을 정리해보면

s[i] + (2칸전의 최대값) or s[i] + s[i-1] + (3칸전의 최대값) 이 될 것이다.

다음은 위의 식을 정리하여 소스코드를 만들면 다음과 같다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] stairs = new int[n + 1];

        for (int i = 0; i < n; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        
        int[] memo = new int[n + 1];
        memo[0] = stairs[0];
        memo[1] = Math.max(stairs[0] + stairs[1], stairs[1]);
        memo[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);
        for (int i = 3 ; i < n; i++) {
            memo[i] = Math.max(memo[i - 3] + stairs[i - 1], memo[i - 2]) + stairs[i];
        }
        bw.write(memo[n - 1] + "\n");
        bw.flush();
        bw.close();
    }
}

Max Array Sum은 배열에서 인접하지 않은 원소들의 합 중 최대가 되는 값을 구하는 문제이다.

여기서 인접하지 않는다는 말은 임의의 인덱스 i, j 값이 i != j + 1 or i != j - 1일 경우를 말한다.

문제를 이해하기 쉽게 배열을 그려보았다.

위의 배열 그림에서 연두색이 기준이 되는 인덱스라 가정한다(맨 위의 그림에서 3번 인덱스 색). 

각각의 경우에서 최소 -2만큼 떨어져 있는 인덱스를 더할 수 있으며 위에서 부터

[2, 0], [3, 0], [3, 1], [4, 2], [4, 2, 0], [4, 1], [4, 0] 의 경우가 가능하다. 

brute force를 통해 문제를 푼다면 3중 for문이 필요할 것이다. O(n^3)이 되므로 많은 경우에 효율적인 알고리즘이라고 보기 힘들 것이다.

문제의 규칙을 정의해보자.

해당 문제의 규칙을 만들어 보자.

• 규칙 1. 양수의 경우 더하는 것이 무조건 유리하다. (음수는 더하면 무조건 분리하다.)
• 규칙 2. 임의의 인덱스 i에 최소 2 만큼 떨어져 있는 수만 더할 수 있다.

위의 규칙을 적용하여 각각의 인덱스에서 최대값을 구하면 다음과 같을 것이다.

각각의 인덱스에서 최대값은 i -2 인덱스와 i - 3인덱스의 최대 값을 포함합니다. 위의 규칙을 이용하여 소스코드를 작성하면 다음과 같다.

public class Main {
    static int maxSubsetSum(int[] arr) {
        int n = arr.length;

        if (n == 1) {
            return arr[0];
        } else if (n == 2) {
            return Math.max(arr[0], arr[1]);
        }

        int[] memo = new int[n + 1];
        memo[0] = -100000;
        memo[1] = arr[0];
        memo[2] = arr[1];
        int max = -100000;
        for (int i = 2; i < n; i++) {
            int memoMax = Math.max(memo[i - 1], memo[i - 2]);
            if (arr[i] >= 0) {
                memo[i + 1] = Math.max(memoMax + arr[i], arr[i]);
            } else {
                memo[i + 1] = memoMax;
            }
            max = Math.max(max, memo[i + 1]);
        }
        return max;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int res = maxSubsetSum(arr);

        bufferedWriter.write(String.valueOf(res));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Abbreviation은 주어진 A 문자열에서 B문자열을 만들어 낼 수 있는지 판단하는 문제이다.

규칙은 다음과 같다.

• 규칙 1. A 문자열 중 소문자는 지울 수 있다.
• 규칙 2. A 문자열 중 소문자는 대문자로 변환 시킬 수 있다.

소문자는 없는 문자로 취급해도 되니, 순서에 맞게 B문자열이 나올 수만 있으면 정답이 될 것이다.

위의 규칙을 소스코드로 만들어 보면 다음과 같을 것이다.

    public static void abbreviation(String a, String b) {
    	if (b.length() == 0) { #3
            if (hasUpperCase(a) == false) {
                result = true;
            }
            return;
        }
        
        char aLetter = a.charAt(0);

        if (Character.isLowerCase(aLetter) == true) { #1
            abbreviation(a.substring(1), b);
        }
        if (Character.toUpperCase(aLetter) == b.charAt(0)) { #2
            abbreviation(a.substring(1), b.substring(1));
        }
        return;
    }
    
    static boolean hasUpperCase(String a) {
        for (int i = 0; i < a.length(); i++) {
            if (Character.isUpperCase(a.charAt(i))) {
                return true;
            }
        }
        return false;
    }

#1 if 문 : 소문자는 지울 수 있다.

#2 if문 : 소문자를 대문자로 바꿀 수 있다.

재귀를 통해 쉽게 구현을 할 수 있다. 항상 재귀는 탈출 조건을 가지고 있어야하는데 위의 문제 탈출 조건은 변환이 가능할 때와 그렇지 않을 때이다. #3에서 B 문자열이 존재하지 않을 때(#2에 의해서 지워진다.), A 문자열의 남은 문자열에 대문자가 있으면 답이 아닌 것으로 간주(#1의 조건 문에 의하여)한다.

예를 들어 A 문자열이 ABCdfgh이고 B 문자열이 ABC이면 ABC가 #2에 의해 맞아 떨어지고 A문자열이 dfgh가 남았을 경우 dfgh는 지울 수 있는 문자이므로 답이라고 본다.

하지만 위의 코드를 정답에 넣어보면 타임아웃이 나올 것이다. 

한가지 예시가 있다. dd라는 문자열이 A 문자열로 들어 왔을 때이다. 왼쪽으로 가면 규칙 1에 의해 소문자를 지우고 오른쪽으로 가면 규칙 2에 의해 대문자로 만든다. 만약 dd뒤에 더 많은 문자열이 있다면 리프 노드의 D는 중복이다. 문자열이 길어질 수록 이런 중복된 계산은 더 비효율적인 계산이 될 것이다. (마치 피보나치에서 중복 계산을 하는 것 처럼)

이러한 중복된 계산을 지우기 위해 미리 계산해 놓을 필요가 있다.

    public static void abbreviation(String a, String b) {
        if (b.length() == 0) {
            if (hasUpperCase(a) == false) {
                result = true;
            }
            return;
        }

        char aLetter = a.charAt(0);

        if (memo.containsKey(a) == true) {
            String memoB = memo.get(a);
            if (memoB.equals(b) == true) {
                return;
            }
        }
        memo.put(a, b);
        if (Character.isLowerCase(aLetter) == true) {
            abbreviation(a.substring(1), b);
        }
        if (Character.toUpperCase(aLetter) == b.charAt(0)) {
            abbreviation(a.substring(1), b.substring(1));
        }

        return;
    }

동적계획법을 활용하여 미리 계산된 값이 있는지 확인하는 코드 이다.

A 문자열이 ddA이고 B문자열이 DC라고 가정하면 경우의 수는 비교 가능한 경우의 수는 

["ddA", "DC"], ["dA", "DC"], ["A", "C"], ["DdA", "DC"], ["dA", "C"], ["A", "C"] 이고 ["A", "C"]가 2번 나오는 계산을 한다. 만약 A뒤의 문자열이 더 길어지면 어떨까? 문자열 A와 문자열 B의 키, 밸류 값으로 중복 계산을 막는 코드를 넣으므로 시간 복잡도는 훨씬 나아질 것으로 기대된다. 

public class Main {
    public static void abbreviation(String a, String b) {
        if (result == true) return;

        if (a.length() < b.length()) return;

        if (b.length() == 0) {
            if (hasUpperCase(a) == false) {
                result = true;
            }
            return;
        }

        char aLetter = a.charAt(0);

        if (memo.containsKey(a) == true) {
            String memoB = memo.get(a);
            if (memoB.equals(b) == true) {
                return;
            }
        }
        memo.put(a, b);
        if (Character.isLowerCase(aLetter) == true) {
            abbreviation(a.substring(1), b);
        }
        if (Character.toUpperCase(aLetter) == b.charAt(0)) {
            abbreviation(a.substring(1), b.substring(1));
        }

        return;
    }

    static boolean hasUpperCase(String a) {
        for (int i = 0; i < a.length(); i++) {
            if (Character.isUpperCase(a.charAt(i))) {
                return true;
            }
        }
        return false;
    }

    private static final Scanner scanner = new Scanner(System.in);
    private static boolean result = false;
    private static Map<String, String> memo = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String a = scanner.nextLine();

            String b = scanner.nextLine();

            abbreviation(a, b);
            bufferedWriter.write(result == true ? "YES" : "NO");
            result = false;
            memo = new HashMap<>();
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

에라토스테네스의 체는 특정 제한된 범위 내의 소수(prime number)를 찾는  고대 수학 알고리즘이다. 

이 알고리즘의 동작 방식은 다음과 같다.

20까지의 수 중 소수를 찾는다고 하면,

1. 2를 소수에 적는다. (2는 가장 작은 소수이다.)

2. 20까지의 소수 중 2의 배수를 지운다.

3. 지워지지 않은 가장 작은 수를 찾아 소수에 적는다.

4. 20까지의 해당 수의 배수를 지운다.

5. 3~4를 20까지 반복한다.

이런 식으로 5단계까지 완료하면 남는 수가 제한된 범위까지의 소수이다.

위의 과정이 체처럼 소수들을 거른다는 느낌이 들어서 이 알고리즘의 이름을 에라토스테네스의 체라고 정말 잘 지은 것 같다는 생각이 든다.

백준 2960번 에라토스테네스의 체는 이 알고리즘을 이용하여 푸는 문제이다. 단순히 에라토스테네스의 체 순서에 따라 지워지는 수를 구하면 되는 문제이다. 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        boolean[] seive = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            seive[i] = true;
        }

        int step = 0;
        int result = -1;
        for (int i = 2; i <= n; i++) {
            if (result != -1) break;
            for (int j = 1; i * j <= n; j++) {
                if (seive[i * j] == false) {
                    continue;
                } else {
                    seive[i * j] = false;
                    step++;
                    if (step == k) {
                        result = i * j;
                        break;
                    }
                }
            }
        }
        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}