고양이 두 잔

문제 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른 것의 개수는 12개이다. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. 출력 첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다. 풀이 처음엔 어떻게든 조합을 이용해서 풀어야 하는 문제라고 생각했는데 전혀 아니었다. 생각보다 쉬운 문제였는데도 멀리멀리 돌아왔지만 하여간 풀기는 풀었다. 문자..

목차 지난 한 주간은 백준에서 집합과 관련된 문제를 주로 풀었다. 그러면서 해시 셋과 트리 셋의 특성에 대해 전보다 익숙해진 느낌이 들어 든든한 느낌도 든다. 어쨌거나 집합과 맵에 대한 문제를 풀어본 김에, 자바 컬렉션 프레임워크에서 제공하는 집합과 관련된 메서드를 정리하고 가면 좋겠다는 생각이 들었다. 대단히 어려운 내용은 없지만, 그림과 함께 하나씩 정리하자. 먼저, 아래와 같은 셋 두 개를 준비한다. public class example { public static void main(String[] args) { Set treeSet = new TreeSet(List.of(1, 2, 3, 4, 5)); Set hashSet = new HashSet(List.of(4, 5, 6, 7, 8)); } }..

문제 자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다. 예를 들어, A = { 1, 2, 4 }이고, B = { 2, 3, 4, 5, 6 }라고 할 때, A-B = { 1 }이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다. 입력 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을..

문제 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 각 문자열은 입력 순서대로 1부터 시작하는 번호를 부여받는다. 입력으로 주어지는 문자와 번호에 대해 대응하는 값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 문제의 개수 M (1 ≤ N, M ≤ 100,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열과 번호들이 주어진다. 입력으로 주어지는 문자열은 알파벳 대문자와 소문자로 이루어져 있으며, 길이는 최소 2, 최대 20이다. 또한 입력으로 주어지는 숫자는 1과 N 사이의 숫자이다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄부터 차례대로 M개의 주에 문제에 대한 답을 출력..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다. 풀이 지난번 문제와 마찬가지로 HashSet을 연습하라는 문제이다. N개의..

캐시에 대해서는 두 번이나 정리한 적이 있으므로, 오늘은 바로 본론으로 들어간다. 2022.12.11 - [Development/Technical Interview] - [면접 준비 - Java?]Primary Memory [면접 준비 - Java?]Primary Memory 어제오늘 JVM의 메모리 구조를 공부하다가 속도와 용량, 일처리 속도의 최적화에 대해 조금 더 알고 싶어서 찾아보게 되었다. 당연하게도 관련 자료가 매우 많고 논문까지 쌓여있는(...) 수준이라 gnidinger.tistory.com 2023.01.14 - [Development/Database] - [Redis]캐시(Cache), 그리고 레디스(Redis) [Redis]캐시(Cache), 그리고 레디스(Redis) Cache 전에..

문제 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수..

문제 지민이는 자신의 저택에서 NM개의 단위 정사각형으로 나누어져 있는 N×M 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..

문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈..