APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.  

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

📝 입력

첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

• 예제 입력 1

  5
  abcde

• 예제 입력 2

  3
  zzz

• 예제 입력 3

  1
  i

  
  

📝 출력

문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

• 예제 출력 1

  4739715

• 예제 출력 2

  25818

• 예제 출력 3

  9

  
  

힌트

예제 1: abcde의 해시 값은 1 × 310 + 2 × 311 + 3 × 312 + 4 × 313 + 5 × 314 = 1 + 62 + 2883 + 119164 + 4617605 = 4739715이다.

예제 2: zzz의 해시 값은 26 × 310 + 26 × 311 + 26 × 312 = 26 + 806 + 24986 = 25818이다.

💡 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int L = Integer.parseInt(br.readLine());
        String S = br.readLine();
        long result = 0;
        long pow = 1;

        for(int i = 0; i < L; i++) {
            result += ((S.charAt(i) - 96) * pow);
            // pow는 31을 매번 곱함
            pow = (pow * 31) % 1234567891;
            // 곱해줄 때마다 1234567891을 나눠주면 long을 넘지 않음
        }

        System.out.println(result % 1234567891);
    }
}

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

• 예제 입력 1

  10
  6 3 2 10 10 10 -10 -10 7 3
  8
  10 9 -5 2 3 4 5 -10

  
  

📝 출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

• 예제 출력 1

  3 0 0 1 2 0 0 2

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int[] ary = new int[N];

        for(int i = 0; i < N; i++) {
            ary[i] = s.nextInt();
        }

        Arrays.sort(ary);

        int M = s.nextInt();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++) {
            int num = s.nextInt();
            sb.append(upperBound(ary, num) - lowerBound(ary, num)).append(' ');
        }
        System.out.println(sb);
    }

    private static int lowerBound(int[] ary, int num) {
        int start = 0;
        int end = ary.length;

        while (start < end) {
            int mid = (start + end) / 2;

            if (num <= ary[mid]) end = mid;
            else start = mid + 1;
        }
        return start;
    }

    private static int upperBound(int[] ary, int num) {
        int start = 0;
        int end = ary.length;

        while (start < end) {
            int mid = (start + end) / 2;

            if (num < ary[mid]) end = mid;
            else start = mid + 1;
        }
        return start;
    }
}

💡 다른 방법

위의 방법보다 메모리와 시간이 둘 다 적다는 장점이 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int[] counting = new int[20000001];

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

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

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < M; i++) {
            sb.append(counting[Integer.parseInt(st.nextToken()) + 10000000]).append(' ');
        }

        System.out.println(sb);
    }
}

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

• 예제 입력 1

  6

  
  

📝 출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

• 예제 출력 1

  4

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Queue<Integer> q = new LinkedList<>();

        int N = in.nextInt();

        for (int i = 1; i < N + 1; i++) {
            q.offer(i);
        }

        while (q.size() != 1) {
            q.poll();

            int n = q.poll();
            q.offer(n);
        }

        System.out.println(q.peek());
    }
}

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

📝 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

• 예제 입력 1

  5
  4 1 5 2 3
  5
  1 3 7 9 5

  
  

📝 출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

• 예제 출력 1

  1
  1
  0
  0
  1

  
  

💡 코드

import java.util.*;

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

        int N = s.nextInt();
        int A[] = new int[N];

        for(int i = 0; i < N; i++) {
            A[i] = s.nextInt();
        }

        Arrays.sort(A);

        int M = s.nextInt();
        for(int i = 0; i < M; i++) {
            sb.append(binary(A, s.nextInt())).append("\n");
        }
        System.out.print(sb);
    }

    public static int binary(int[] ary, int n) {
        int first = 0;
        int last = ary.length - 1;

        while(first <= last) {
            int mid = (first + last) / 2;

            if(ary[mid] < n) first = mid + 1;
            else if (ary[mid] > n) last = mid - 1;
            else return 1;
        }
        return 0;
    }
}

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

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 ≤ 1,000)

• 예제 입력 1

  7 3

  
  

📝 출력

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

• 예제 출력 1

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

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Queue<Integer> q = new LinkedList<>();

        int N = in.nextInt();
        int K = in.nextInt();

        System.out.print("<");

        for (int i = 1; i < N + 1; i++) {
            q.offer(i);
        }

        while (q.size() != 1) {
            for (int i = 0; i < K - 1; i++) {
                int num = q.poll();
                q.offer(num);
            }
            System.out.print(q.poll() + ", ");
        }

        System.out.print(q.poll() + ">");
    }
}

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

📝 입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

• 예제 입력 1

  20
  7
  23
  19
  10
  15
  25
  8
  13

  
  

📝 출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

• 예제 출력 1

  7
  8
  10
  13
  19
  20
  23

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int arr[] = new int[9]; int sum = 0;

        for(int i = 0; i < 9; i++) {
            arr[i] = s.nextInt();
            sum += arr[i];
        }

        for(int i = 0; i < 8; i++) {
            for(int j = i + 1; j < 9; j++) {
                if((sum - arr[i] - arr[j]) == 100) {
                    arr[i] = 0; arr[j] = 0;
                    break;
                }
            }
            if(arr[i] == 0) break;
        }

        Arrays.sort(arr);

        for(int i = 2; i < 9; i++) {
            System.out.println(arr[i]+ " ");
        }
    }
}

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

📝 입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

• 예제 입력 1

  5
  1 6
  3 7
  6 2
  7 100
  9 635

  
  

📝 출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

• 예제 출력 1

  1
  7
  6
  1
  9

  
  

💡 코드

import java.util.*;

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

        for(int i = 0; i < n; i++) {
            int a = s.nextInt();
            int b = s.nextInt();
            int r = a % 10;

            for (int j = 1; j < b; j++) {
                r = (r * a) % 10;
            }
            if(r == 0) r = 10;

            System.out.println(r);
        }
    }
}

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

📝 입력

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

• 예제 입력 1

  9999

• 예제 입력 2

  122

• 예제 입력 3

  12635

• 예제 입력 4

  888888

  
  

📝 출력

첫째 줄에 필요한 세트의 개수를 출력한다.

• 예제 출력 1

  2

• 예제 출력 2

  2

• 예제 출력 3

  1

• 예제 출력 4

  6

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s[] = scanner.next().split("");
        String num[] = { "0", "1", "2", "3", "4", "5", "6", "7", "8" };
        int count[] = new int[9]; int set = 1;

        for(int i = 0; i < s.length; i++) {
            for (int j = 0; j < num.length; j++) {
                if (s[i].equals("9")) {
                    count[6]++;
                    break;
                } else if (s[i].equals(num[j])) {
                    count[j]++;
                    break;
                }
            }
        }

        for(int j = 0; j < num.length; j++) {
            int six = (int)Math.round((double)count[6]/2);

            if(j != 6 && set < count[j]) set = count[j];
            else if(j == 6 && set < six) set = six;
        }

        System.out.print(set);
    }
}

어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다.

수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자.

📝 입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다.

• 예제 입력 1

  121
  1231
  12421
  0

  
  

📝 출력

각 줄마다 주어진 수가 팰린드롬수면 'yes', 아니면 'no'를 출력한다.

• 예제 출력 1

  yes
  no
  yes

  
  

💡 코드

import java.util.*;

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

        while(!n.equals("0")) {
            String s[] = n.split("");
            String arr[] = new String[(int)s.length / 2];
            int len = arr.length;

            if(s.length == 1) System.out.println("yes");

            for(int i = 0; i < len; i++) {
                arr[i] = s[i];
            }

            if(s.length % 2 == 0) repeat(arr, s, len);
            else { // 홀수
                len++;
                repeat(arr, s, len);
            }

            n = scanner.next();
        }
    }

    private static void repeat(String[] arr, String[] s, int len) {
        for(int i = arr.length - 1; i > -1; i--) {
            if(!arr[i].equals(s[len++])) {
                System.out.println("no");
                break;
            } else if(i == 0) System.out.println("yes");
        }
    }
};

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

• 예제 입력 1

  10

  
  

📝 출력

첫째 줄에 n번째 피보나치 수를 출력한다.

• 예제 출력 1

  55

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int f1 = 0; int f2 = 1;
        int answer = f1 + f2;

        for(int i = 2; i < n; i++) {
            f1 = f2;
            f2 = answer;
            answer = f1 + f2;
        }

        System.out.print(answer);
    }
};

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

📝 입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

• 예제 입력 1

  4
  3
  0
  4
  0

• 예제 입력 2

  10
  1
  3
  5
  4
  0
  0
  7
  0
  0
  6

  
  

📝 출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 2^31-1보다 작거나 같은 정수이다.

• 예제 출력 1

  0

• 예제 출력 2

  7

  
  

💡 코드

• for(int o : stack) : stack 에 담긴 원소 훑기

  import java.util.*;
  

public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); Stack stack = new Stack(); int K = in.nextInt(); int sum = 0;

    for (int i = 0; i < K; i++) {
        int num = in.nextInt();

        if(num == 0) stack.pop();
        else stack.push(num);
    }

    for(int o : stack) {
        sum += o;
    }
    System.out.println(sum);
}

} ```

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..

📝 입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

• 예제 입력 1

  5
  5 4 1 3 2

📝 출력

승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

• 예제 출력 1

  Nice

💡 코드

• while (큐나 스택이 비지 않을 때) 가 아닌 그냥 애초에 각각 한바퀴만 돌면 되지 않나라고 생각했음
• 대기열 하나만 num이랑 비교하는 게 아니라 공간이 비지 않았다면 공간도 num이랑 비교 했었어야 한다는 걸 생각못함

  import java.util.*;
  

public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); Queue wait = new LinkedList<>(); Stack space = new Stack<>();

    int N = in.nextInt();
    int num = 1;

    for (int i = 0; i < N; i++) {
        wait.offer(in.nextInt());
    }

    while (!wait.isEmpty()) {
        if (wait.peek() == num) {
            wait.poll();
            num++;
        } else if (!space.isEmpty() && space.peek() == num) {
            space.pop();
            num++;
        } else space.push(wait.poll());
    }

    System.out.println(result(space, num));
}

static String result(Stack space, int num) {
    while (!space.isEmpty()) {
        int order = (int) space.peek();

        if (num == order) {
            space.pop();
            ++num;
        } else return "Sad";
    }
    return "Nice";
}

} ```

다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다.

1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다.

연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 8개 숫자가 주어진다. 이 숫자는 문제 설명에서 설명한 음이며, 1부터 8까지 숫자가 한 번씩 등장한다.

• 예제 입력 1

  ascending

• 예제 입력 2

  descending

• 예제 입력 3

  mixed

  
  

📝 출력

첫째 줄에 ascending, descending, mixed 중 하나를 출력한다.

• 예제 출력 1

  1 2 3 4 5 6 7 8

• 예제 출력 2

  8 7 6 5 4 3 2 1

• 예제 출력 3

  8 1 7 2 6 3 5 4

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int as[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
        int de[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
        int a = 0; int d = 0;

        for(int i = 0; i < 8; i++) {
            int num = s.nextInt();
            if (as[i] == num) a++;
            else if (de[i] == num) d++;
        }

        if (a == 8) System.out.println("ascending");
        else if (d == 8) System.out.println("descending");
        else System.out.println("mixed");
    }
};

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

📝 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

• 예제 입력 1

  5
  3 2 1 -3 -1

  
  

📝 출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

• 예제 출력 1

  1 4 5 3 2

  
  

💡 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayDeque<int[]> d = new ArrayDeque<>();
        int N = in.nextInt();

        for (int i = 0; i < N; i++) {
            int[] arr = {i + 1, in.nextInt()};
            d.offer(arr);
        }

        /* d의 내용 
               0 -> [1, 3] 
               1 -> [2, 2] 
               2 -> [3, 1] 
            3 -> [4, -3] 
            4 -> [5, -1] 
        */

        while (d.size() > 1) {
            int[] arr = d.poll(); // [1, 3]
            int n = arr[1];       // 3
            System.out.print(arr[0] + " "); // 1

            if (n > 0) {
                for (int j = 1; j < n; j++) {
                    d.offerLast(d.pollFirst());
                }
            } else if (n < 0) {
                for (int j = n; j < 0; j++) {
                    d.offerFirst(d.pollLast());
                }
            }
        }

        System.out.print(d.poll()[0]);
    }
}

상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다.

전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다.

숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다.

상근이의 할머니는 전화 번호를 각 숫자에 해당하는 문자로 외운다. 즉, 어떤 단어를 걸 때, 각 알파벳에 해당하는 숫자를 걸면 된다. 예를 들어, UNUCIC는 868242와 같다.

할머니가 외운 단어가 주어졌을 때, 이 전화를 걸기 위해서 필요한 최소 시간을 구하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다.

• 예제 입력 1

  WA

• 예제 입력 2

  UNUCIC

  
  

📝 출력

첫째 줄에 다이얼을 걸기 위해서 필요한 최소 시간을 출력한다.

• 예제 출력 1

  13

• 예제 출력 2

  36

  
  

💡 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int time = 0;

        for(int i = 0; i<s.length(); i++) {
            int temp = s.charAt(i) - 'A';
            if(temp < 3) 
                time += 3;
            else if (temp > 2 && temp < 6) 
                time += 4;
            else if (temp > 5 && temp < 9) 
                time += 5;
            else if (temp > 8 && temp < 12) 
                time += 6;
            else if (temp > 11 && temp < 15) 
                time += 7;
            else if (temp > 14 && temp < 19) 
                time += 8;
            else if (temp > 18 && temp < 22) 
                time += 9;
            else if (temp > 21 && temp < 26) 
                time += 10;
            else 
                time += 11;
        }
        System.out.print(time);
    }
}

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

📝 입력

입력은 없다.

📝 출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

• 예제 출력 1

  1
  3
  5
  7
  9
  20
  31
  42
  53
  64
  |
  |       <-- a lot more numbers
  |
  9903
  9914
  9925
  9927
  9938
  9949
  9960
  9971
  9982
  9993

  
  

💡 코드

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

public class Main {
    public static void main(String[] args) {
        self();
    }

    public static void self() {
        boolean []N = new boolean[10000];
        for(int i = 1; i < 10000; i++) {
            N[i] = true; // 모두 true
        }

        int num = 0;
        for(int i = 1; i < 10000; i++) {
            if(i < 10)
                num = i + i;
            else if (9 < i && i < 100)
                num = i + (i / 10) + (i % 10);
            else if (99 < i && i < 1000)
                num = i + (i / 100) + ((i % 100) / 10) + (i % 10);
            else
                num = i + (i / 1000) + ((i % 1000) / 100) + ((i % 100) / 10) + (i % 10);

            if(num < 10000)
                N[num] = false;
        }

        for(int i = 1; i < 10000; i++) {
            if(N[i] == true)
                System.out.println(i);
        }
    }
}

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

📝 입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다

• 예제 입력 1

  3
  3 7
  15 7
  5 2

• 예제 입력 2

  3
  0 0
  90 90
  50 50

• 예제 입력 3

  3
  10 10
  10 10
  10 10

• 예제 입력 4

  3
  10 10
  10 10
  20 20

  
  

📝 출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

• 예제 출력 1

  260

• 예제 출력 2

  300

• 예제 출력 3

  100

• 예제 출력 4

  200

  
  

💡 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int paper[][] = new int[100][100];
        int area = 0;

        for(int i = 0; i < num; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            for(int j = X; j < X + 10; j++) {
                for(int k = Y; k < Y + 10; k++) {
                    paper[j][k] = 1;
                }
            }
        }

        for(int j = 0; j < 100; j++) {
            for(int k = 0; k < 100; k++) {
                if(paper[j][k] == 1)
                    area++;
            }
        }

        System.out.println(area);
        br.close();
    }
}

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

📝 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

• 예제 입력 1

  1
  10
  13
  100
  1000
  10000
  100000
  0

  
  

📝 출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

• 예제 출력 1

  1
  4
  3
  21
  135
  1033
  8392

  
  

💡 코드

import java.io.*;

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

        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0)
                break;

            int count = 0;
            prime = new boolean[2*n + 1];
            get_prime();

            for(int i = n+1; i <= (2*n); i++) {
                if(prime[i] == false)
                    count++;
            }

            System.out.println(count);
        }
    }

    public static void get_prime() {
        prime[0] = prime[1] = true;
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i])
                continue;
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

• 예제 입력 1

  3
  21 Junkyu
  21 Dohyun
  20 Sunyoung

  
  

📝 출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

• 예제 출력 1

  20 Sunyoung
  21 Junkyu
  21 Dohyun

  
  

💡 코드

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

public class Main {
    public static void main(String[] args) throws IOException {        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Person[] p = new Person[N];

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            p[i] = new Person(age, name);
        }

        // 타입을 Person 으로
        Arrays.sort(p, new Comparator<Person>() {
            @Override
            public int compare(Person s1, Person s2) { // 나이 순 정렬
                return s1.age - s2.age;
            }
        });

        for(int i = 0; i < N; i++) {
            // 객체 배열의 객체를 출력하면 해당 인덱스의 객체의 toString() 이 출력됨
            System.out.println(p[i]);
        }
    }

    public static class Person {
        int age;
        String name;

        public Person(int age, String name) {
            this.age = age;
            this.name = name;
        }

        @Override
        public String toString() {
            return age + " " + name;
        }
    }
}

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

📝 입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

• 예제 입력 1

  5
  0 4
  1 2
  1 -1
  2 2
  3 3

  
  

📝 출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

• 예제 출력 1

  1 -1
  1 2
  2 2
  3 3
  0 4

  
  

💡 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int coordinates[][] = new int[N][2];

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            coordinates[i][0] = Integer.parseInt(st.nextToken());
            coordinates[i][1] = Integer.parseInt(st.nextToken());
        }

        // 람다식 & compare 사용
        Arrays.sort(coordinates, (arr1, arr2) -> {
            if(arr1[1] == arr2[1]) // y축 좌표가 같다면 x축 좌표 비교
                return arr1[0] - arr2[0];
            else
                return arr1[1] - arr2[1];
        });

        for(int i = 0; i < N; i++) {
            System.out.println(coordinates[i][0]+" "+coordinates[i][1]);
        }

        br.close();
    }
}