와드의 블로그

문제2와 5로 나누어 떨어지지 않는 정수 n이 주어졌을 때, 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수를 구하는 문제입니다.입력: 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 정수 n (1 ≤ n ≤ 10000)이 주어집니다.출력: 각 테스트 케이스마다 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수를 출력합니다.풀이1로만 이루어진 수(1, 11, 111, 1111...)를 만들며 n으로 나누어 떨어지는지 검사하는 문제입니다.EOF(End of File) 처리: 테스트 케이스의 개수가 명시되어 있지 않으므로, BufferedReader.readLine()이 null을 반환할 때까지 반복해서 입력을 받아야 합니다.모듈러(나머지) 연산 최적화 (오버플로우 방지): 1로만 이루어진 ..

문제자연수 A를 B번 곱한 수를 구하려고 합니다. 단, 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 문제입니다.입력: 첫째 줄에 A, B, C가 빈칸을 사이에 두고 주어집니다. (A, B, C는 모두 2,147,483,647 이하의 자연수)출력: 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력합니다.링크: https://www.acmicpc.net/problem/1629풀이B가 최대 약 21억이므로 단순한 for 반복문(O(N))으로 A를 B번 곱하면 무조건 시간 초과가 발생합니다. 따라서 지수 법칙을 활용하여 연산 횟수를 절반씩 줄여나가는 분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring) 알고리즘을 사용해야 합니다. 시간 복잡도를 O(lo..

문제단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 짝을 지을 때, 선이 교차하지 않고 모든 글자를 짝지을 수 있는 단어를 '좋은 단어'라고 합니다. 주어진 N개의 단어 중 좋은 단어의 개수를 구하는 문제입니다.입력: 첫째 줄에 단어의 수 N (1 ≤ N ≤ 100,000)이 주어집니다. 둘째 줄부터 N개의 줄에 'A'와 'B'로만 이루어진 단어가 한 줄에 하나씩 주어집니다.출력: 첫째 줄에 좋은 단어의 개수를 출력합니다.링크: https://www.acmicpc.net/problem/3986풀이선이 교차하지 않고 인접한 같은 글자끼리 짝을 지어 소거해 나가는 조건은 전형적인 괄호 짝맞추기(올바른 괄호 문자열) 문제의 논리와 완전히 동일합니다. 따라서 스택(Stack) 구조를 사..

문제갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있습니다. 갑옷은 두 개의 재료로 만드는데, 두 재료의 고유한 번호를 합쳐서 M이 되면 갑옷이 만들어집니다. 주어진 N개의 재료 번호들 중 합이 M이 되는 두 재료의 쌍의 개수를 구하는 문제입니다.입력: 첫째 줄에 재료의 개수 N (1 ≤ N ≤ 15,000), 둘째 줄에 갑옷을 만드는데 필요한 수 M (1 ≤ M ≤ 10,000,000), 셋째 줄에 N개의 재료 번호가 주어집니다.출력: 갑옷을 만들 수 있는 쌍의 개수를 출력합니다.링크: https://www.acmicpc.net/problem/1940풀이 1: 이중 반복문을 활용한 완전탐색 (Brute Force)가장 직관적인 방법으로, 이중 반복문을 사용하여 2개의 재료를 고르는 모든 경우의 수를..

문제임한수와 임문빈은 서로 알파벳 대문자로만 이루어진 영어 이름을 팰린드롬으로 바꾸는 프로그램을 만들고자 합니다. 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말합니다. 주어진 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들되, 정답이 여러 개일 경우 사전순으로 가장 앞서는 것을 출력해야 합니다. 만약 팰린드롬으로 바꿀 수 없다면 "I'm Sorry Hansoo"를 출력합니다.입력: 첫째 줄에 영어 이름이 주어집니다. (알파벳 대문자로만 이루어져 있으며, 최대 50글자)출력: 첫째 줄에 문제의 정답을 출력합니다.링크: https://www.acmicpc.net/problem/1213풀이 1: 양끝 동시 삽입 (insert 활용)알파벳 빈도수를 구한 뒤, 역순으로 탐색하며 StringB..

문제해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않습니다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경 대신 렌즈를 착용해야 합니다. 해빈이가 가진 의상들이 주어졌을 때, 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있는지 구하는 문제입니다.입력:첫째 줄: 테스트 케이스의 수 T (최대 100)각 테스트 케이스의 첫째 줄: 해빈이가 가진 의상의 수 N (0 ≤ N ≤ 30)다음 N개의 줄: 의상의 이름과 의상의 종류가 공백으로 구분되어 주어짐 (같은 종류의 의상은 하나만 입을 수 있음)출력: 각 테스트 케이스마다 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우의 수링크: https://www.acmicpc.ne..

문제포켓몬 도감에 수록된 포켓몬의 이름이 주어질 때, 번호를 입력받으면 이름을, 이름을 입력받으면 번호를 출력하는 문제입니다.입력: 첫째 줄에 포켓몬의 개수 N과 맞춰야 하는 문제의 개수 M이 주어집니다. 둘째 줄부터 N개의 줄에 포켓몬의 이름이 1번부터 N번까지 차례대로 주어집니다. 이어서 M개의 줄에 맞춰야 하는 문제가 번호 또는 이름으로 주어집니다.출력: 입력으로 번호가 들어오면 해당하는 포켓몬의 이름을, 이름이 들어오면 해당하는 포켓몬의 번호를 출력합니다.링크: https://www.acmicpc.net/problem/1620풀이입력되는 쿼리의 종류가 숫자(번호)와 문자열(이름) 두 가지이므로, 양방향 검색이 모두 O(1)의 시간 복잡도로 빠르게 이루어져야 시간 초과를 방지할 수 있습니다. 번호로..

문제매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 구하는 문제입니다.입력: 첫째 줄에 전체 날짜의 수 N과 합을 구하기 위한 연속적인 날짜의 수 K가 주어집니다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어집니다.출력: 연속적인 K일 동안의 온도의 합이 최대가 되는 값을 출력합니다.링크: https://www.acmicpc.net/problem/2559풀이연속된 구간의 합을 매번 반복문으로 구하면 시간 초과가 발생할 수 있습니다. 이를 해결하기 위해 누적 합(Prefix Sum) 배열을 미리 만들어두고 활용하는 O(N) 풀이입니다.누적 합 배열 생성: 크기가 N + 1인 psum 배열을 선언합니다. 입력을 받음과 동시에..

문제어떤 파일 이름이 주어졌을 때, 해당 파일 이름이 특정 패턴과 일치하는지 판별하는 문제입니다. 패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어져 있습니다. 별표는 빈 문자열을 포함하여 임의의 문자열로 변환될 수 있습니다.입력: 첫째 줄에 파일의 개수 N이 주어지고, 둘째 줄에 패턴이 주어집니다. 다음 N개의 줄에는 파일 이름이 주어집니다.출력: 각 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력합니다.링크: https://www.acmicpc.net/problem/9996풀이 1: 접두사와 접미사 분리 (String 메서드 활용)패턴의 유일한 별표(*)를 기준으로 앞부분(접두사)과 뒷부분(접미사)을 분리하여 각 문자열을 검사하는 방식으로 해결할 수 있습니다. 자바의 문..