더 이상 물러설 곳이 없다

www.acmicpc.net/problem/9613

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1

3

4 10 20 30 40

3 7 5 12

3 125 15 25

예제 출력 1

70

3

35

풀이 .

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

public class Main {
    public static int gcd(int a, int b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            long sum = 0;
            for(int i = 0; i < n - 1; i++) {
                for(int j = i + 1; j < n; j++) {
                    sum += gcd(arr[i], arr[j]);
                }
            }
            System.out.println(sum);
        }
    }
}

총 n^2 (100^2 = 10^4) 개의 GCD가 나올 수 있고 그 최대값은 10^6이다.

sum의 최대값은 10^10 이므로 long을 써야 한다.

www.acmicpc.net/problem/1850

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

예제 입력 1

3 4

예제 출력 1

1

예제 입력 2

3 6

예제 출력 2

111

예제 입력 3

500000000000000000 500000000000000002

예제 출력 3

11

풀이 .

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

public class Main {
    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        long gcd = gcd(a, b);
        for(int i = 0; i < gcd; i++) {
            sb.append("1");
        }
        System.out.println(sb.toString());
    }
}

함정이다.

입력받은 1의 개수만큼 1을 이어붙인 숫자를 만들어서 GCD를 구하려고 했다.

이렇게 하려면 예제 입력 3번의 경우에는 도저히 숫자를 만들어낼 수가 없다.
(50경자리 숫자를 어떻게 만들어..)

정답 코드를 찾아보니,

1의 개수끼리 GCD를 구하면 그게 그 수의 GCD에 들어있는 1의 개수가 된단다.

왜인지는 모르겠다. 편하게 이해하기엔 수학적 머리가 너무 딸린다.

알고 싶지도 않다.

www.acmicpc.net/problem/1934

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

3

1 45000

6 10

13 17

예제 출력 1

45000

30

221

풀이 .

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

public class Main {
    public static int gcd(int a, int b) {  // 최대공약수
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            int gcd = gcd(a, b);
            int lcm = (a * b) / gcd;
            System.out.println(lcm);
        }
    }
}

GCD를 통해 LCM을 구할 수 있다.

외우자.

www.acmicpc.net/problem/2609

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6

72

풀이 .

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

public class Main {
    public static int gcd(int a, int b) {  // 최대공약수
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int gcd = gcd(a, b);
        int lcm = (a * b) / gcd;
        System.out.println(gcd);
        System.out.println(lcm);
    }
}

유클리드 호제법을 통해 GCD(=최대공약수)를 구한다.

GCD를 통해 LCM(최소공배수)를 구한다.

왜 가능한지 굳이 이해하려고 하지 말자. 어차피 까먹는다.

GCD, LCM은 그냥 외우자.

www.acmicpc.net/problem/1158

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

풀이 .

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

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());
        StringBuilder sb = new StringBuilder();
        Queue<Integer> que = new ArrayDeque<>();

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        for(int i = 1; i <= n; i++) {
            que.add(i);
        }

        sb.append("<");
        while(!que.isEmpty()) {
            if(que.size() == 1) {
                sb.append(que.poll());
                break;
            }

            for(int i = 1; i < k; i++) {
                que.add(que.poll());
            }
            sb.append(que.poll() + ", ");
        }
        sb.append(">");

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

O(kn) 으로 처리 가능.

www.acmicpc.net/problem/1406

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

LDBP $

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력 1

abcd

3

P x

L

P y

예제 출력 1

abcdyx

예제 입력 2

abc

9

L

L

L

L

L

P x

L

B

P y

예제 출력 2

yxabc

예제 입력 3

dmih

11

B

B

P x

L

B

B

B

P y

D

D

P z

풀이 1. (틀린 코드)

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

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));
        StringBuilder sb = new StringBuilder();

        char[] arr = br.readLine().toCharArray();
        ArrayList<Character> list = new ArrayList<>();
        int len = arr.length;
        for(int i = 0; i < len; i++) {
            list.add(arr[i]);
        }

        int n = Integer.parseInt(br.readLine());
        int cursor = list.size() - 1;  // 마지막 문자에 커서
        StringTokenizer st = null;
        while(n-- > 0) {
            st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "L" :
                    if(cursor != -1)
                        cursor -= 1;
                    break;
                case "D" :
                    if(cursor != list.size() - 1)
                        cursor += 1;
                    break;
                case "B" :
                    if(cursor != -1) {
                        list.remove(cursor);
                        cursor -= 1;
                    }
                    break;
                case "P" :
                    cursor += 1;
                    list.add(cursor, st.nextToken().charAt(0));
                    break;
            }
        }

        for(char c : list) {
            sb.append(c);
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

별 생각 없이 곧이곧대로 구현하고 시간초과를 받았다.

list.remove() 가 O(n)이 소요되는데,

n = 10^5 이고, 명령어의 개수 m = 5 * 10^5 이다.

m개 모두 remove 연산일 경우 O(m*n) = 5 * 10^10 로 시간초과다.

풀이 2. (정답 코드)

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        char[] arr = br.readLine().toCharArray();
        Stack<Character> left = new Stack<>();
        Stack<Character> right = new Stack<>();
        for(char c : arr) {
            left.push(c);
        }

        int n = Integer.parseInt(br.readLine());
        while(n-- > 0) {
            st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "L" :
                    if(!left.isEmpty())
                        right.push(left.pop());
                    break;
                case "D" :
                    if(!right.isEmpty())
                        left.push(right.pop());
                    break;
                case "B" :
                    if(!left.isEmpty())
                        left.pop();
                    break;
                case "P" :
                    left.push(st.nextToken().charAt(0));
                    break;
            }
        }

        while(!left.isEmpty()) {
            right.push(left.pop());
        }
        while(!right.isEmpty()) {
            sb.append(right.pop());
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

스택 대신 덱을 사용해도 무방하다.

O(m + 2n) 으로 O(n) 만에 처리할 수 있다.

제발, 꼭, 코드 짜기 전에 시간 복잡도 계산부터 해보자...

www.acmicpc.net/problem/11656

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

예제 입력 1

baekjoon

예제 출력 1

aekjoon

baekjoon

ekjoon

joon

kjoon

n

on

oon

풀이 .

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

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));
        StringBuilder sb = new StringBuilder();
        String str = br.readLine();

        int len = str.length();
        String[] subStr = new String[len];
        for(int i = 0; i < len; i++) {
            subStr[i] = str.substring(i, len);
        }
        Arrays.sort(subStr);
        for(String sub : subStr) {
            sb.append(sub).append("\n");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

substring()의 파라미터에 주의하자

[begin]~[end] 가 아니라 [begin]~[end - 1] 을 가져온다.

www.acmicpc.net/problem/10824

문제

네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오.

두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다.

입력

첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000)

출력

A와 B를 붙인 수와 C와 D를 붙인 수의 합을 출력한다.

예제 입력 1

10 20 30 40

예제 출력 1

4060

풀이 .

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

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());
        String s1 = st.nextToken() + st.nextToken();
        String s2 = st.nextToken() + st.nextToken();
        long num1 = Long.parseLong(s1);
        long num2 = Long.parseLong(s2);
        System.out.println(num1 + num2);
    }
}

데이터 타입에 주의