꼬마 정민이는 이제 A + B 정도는 쉽게 계산할 수 있다. 이제 A + B + C를 계산할 차례이다!
입력
첫 번째 줄에 A, B, C (1 ≤ A, B, C ≤ 10^12)이 공백을 사이에 두고 주어진다.
출력
A+B+C의 값을 출력한다.
코드
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());
long sum = 0;
for (int i = 0; i < 3; i++) {
sum += Long.parseLong(st.nextToken());
}
System.out.println(sum);
}
}
오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.
강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.
크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)
출력
돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.
코드
BFS 풀이 방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class JUN12886 {
static int sum;
static boolean[][] visited;
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 C = Integer.parseInt(st.nextToken());
sum = A + B + C;
visited = new boolean[sum+1][sum+1];
if(sum % 3 != 0){
System.out.println("0");
return;
}
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{A,B,C});
visited[A][B] = true;
boolean flag = false;
while (!q.isEmpty()){
int[] now = q.poll();
int a = now[0];
int b = now[1];
int c = now[2];
if(a == b && b == c) {
flag = true;
break;
}
for (int i = 0; i < 2; i++) {
for (int j = i+1; j < 3; j++) {
if(now[i] == now[j]) continue;
int t1 = now[i] > now[j]? now[i] - now[j] : now[i] + now[i];
int t2 = now[i] > now[j]? now[j] + now[j] : now[j] - now[i];
if(!visited[t1][t2]){
visited[t1][t2] = true;
q.offer(new int[]{t1, t2 ,sum - (t1 + t2)});
}
}
}
}
System.out.println(flag?"1":"0");
}
}
DFS 풀이 방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int sum;
static int[][] visited;
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 C = Integer.parseInt(st.nextToken());
sum = A + B + C;
visited = new int[sum+1][sum+1];
if(sum % 3 != 0){
System.out.println("0");
}else {
dfs(A,B);
System.out.println(visited[sum/3][sum/3]);
}
}
public static void dfs(int a, int b){
if(visited[a][b] == 1) return;
visited[a][b] = 1;
int[] now = {a, b, sum - (a+b)};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(now[i] < now[j]) {
int[] temp = {a, b, sum - (a + b)};
temp[i] += now[i];
temp[j] -= now[i];
dfs(temp[0], temp[1]);
}
}
}
}
}
러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.
이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.
가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.
파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.
해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)
다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.
빈칸을 나타내는 '.'
블록을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.
항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.
입력
첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)
다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.
빈칸을 나타내는 '.'
블록을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.
항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.
출력
지워진 블록의 행과 열 위치를 출력하고, 어떤 블록이었는지를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class JUN2931 {
static int R, C, dir, M[];
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static char map[][];
/*
* '|' 세로 블럭
* '-' 가로 블럭
* '+' 십자 블럭
* '1' 오 아 블럭
* '2' 위 오 블럭
* '3' 왼 위 블럭
* '4' 왼 아 블럭
* */
static char[] pipes = {'|','-','+','1','2','3','4'};
// 들어오는 방향에 따라 설치할 수 있는 파이트 종류
static char[][] pipes_case = {
{'|', '+', '4', '1'},
{'+', '|', '3', '2'},
{'2', '1', '-', '+'},
{'3', '4', '+', '-'}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
M = new int[2]; //모스크바 위치
for (int i = 0; i < R; i++) {
map[i] = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
if(map[i][j] == 'M'){
M[0] = i;
M[1] = j;
}
}
}
dir = -1;
//모스크바에서 출발 할 수 있는지 확인
for(int i = 0; i < 4; i++){
int tx = M[0] + dx[i];
int ty = M[1] + dy[i];
if(tx < 0 || tx >= R || ty < 0 || ty >= C) continue;
if(map[tx][ty]!='.') dir = i; // 모스크바와 연결된 가스관이 있으면 방향 저장
}
find_blank(M[0], M[1], dir);
}
// 중간에 끊어진 곳을 찾기
static void find_blank(int x, int y, int d){
int nx = x + dx[d];
int ny = y + dy[d];
//if(map[nx][ny] == '.') find_pip();
switch (map[nx][ny]){
case '.':
find_pipe(nx, ny, d);
break;
case '1':
if(d == 2){
d = 1;
} else{
d = 3;
}
find_blank(nx, ny, d);
break;
case '2':
if(d == 2){
d = 0;
} else{
d = 3;
}
find_blank(nx, ny, d);
break;
case '3':
if(d == 3){
d = 0;
} else{
d = 2;
}
find_blank(nx, ny, d);
break;
case '4':
if(d == 3){
d = 1;
} else{
d = 2;
}
find_blank(nx, ny, d);
break;
default:
find_blank(nx, ny, d);
}
}
// 빈곳에 들어가야하는 파이프 찾기
static void find_pipe(int x, int y, int d){
int undir = 0;
if(d == 0){
undir = 1;
} else if(d == 1){
undir = 0;
} else if(d == 2){
undir = 3;
} else if(d == 3){
undir = 2;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < 4; i++) {
if(i == undir) continue;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] == '.' || map[nx][ny] == 'Z') continue;
for (int j = 0; j < 4; j++) {
if(pipes_case[i][j] == map[nx][ny]){
q.offer(i);
}
}
}
x++;
y++;
if(q.size()>1){
System.out.println(x+" "+y+" "+pipes_case[d][undir]);
}else{
System.out.println(x+" "+y+" "+pipes_case[d][q.poll()]);
}
}
}
워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.
두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.
편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n<m이면 어차피 P는 T중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.
1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
| | | | | | X
P : [ A B C D A B D ]
1 2 3 4 5 6 7
문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 위와 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.
그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5～11번 문자와 P의 1～7번 문자가 서로 하나씩 대응되기 때문이다.
1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
| | | | | | |
P : [ A B C D A B D ]
1 2 3 4 5 6 7
가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1～m번 문자와 P의 1～m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2～m+1번 문자와 P의 1～m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O( (n-m+1) × m ) = O(nm) 의 시간복잡도를 갖는 알고리즘이 된다.
더 좋은 방법은 없을까? 물론 있다. 위에 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1…6에 대해 T[i] = P[i] 라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.
P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5, 6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5, 6번 문자도 A, B이다.
따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5～6번 문자는 P의 1～2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.
이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.
이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.
이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.
입 출 력
첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. T와 P의 길이 n, m은 1이상 100만 이하이고, 알파벳 대소문자와 공백으로만 이루어져 있다.
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
// KMP 알고리즘(Knuth–Morris–Pratt Algorithm)
// O(N+M)
public class JUN1786 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] text = in.readLine().toCharArray();
char[] pattern = in.readLine().toCharArray();
int tLength = text.length, pLength = pattern.length;
int[] pi = new int[pLength];
for(int i=1, j=0; i<pLength; i++){
while(j > 0 && pattern[i] != pattern[j]) j = pi[j-1];
if(pattern[i] == pattern[j]) pi[i] = ++j;
else pi[i] = 0;
}
int cnt = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
// i : 텍스트 포인터 , j: 패턴 포인터
for(int i=0,j=0; i<tLength; ++i) {
while(j>0 && text[i] != pattern[j]) j = pi[j-1];
if(text[i] == pattern[j]) { //두 글자 일치
if(j == pLength-1) { // j가 패턴의 마지막 인덱스라면
cnt++; // 카운트 증가
list.add(i-j+1);
j=pi[j];
}else {
j++;
}
}
}
StringBuilder sb = new StringBuilder();
sb.append(cnt).append("\n");
//System.out.println(cnt);
if(cnt>0) {
//System.out.println(list);
for(int i : list){
sb.append(i).append(" ");
}
}
System.out.println(sb);
}
}
풀이
문자열 비교 알고리즘 중 하나인
KMP 알고리즘
으로 한 풀이입니다.
KMP (Knuth - Morris - Pratt) Algorithm
- 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행 - 시간 복잡도 : O(M+N)
꼬마 정민이는 이제 A + B 정도는 쉽게 계산할 수 있다. 이제 A + B + C를 계산할 차례이다!
제한사항
첫 번째 줄에 A, B, C (1 ≤ A, B, C ≤ 10^12)이 공백을 사이에 두고 주어진다.
입출력 예
77 77 7777
7931
코드
package com.home;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class JUN11382 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long sum = 0;
for (int i = 0; i < 3; i++) {
sum += Long.parseLong(st.nextToken());
}
System.out.println(sum);
}
}
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
제한사항
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
입출력 예
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] map;
static StringBuilder sb;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
sb = new StringBuilder();
N = Integer.parseInt(br.readLine()); //맵의 크기
map = new int[N][N];
for(int i = 0; i < N;i++) { // 배열에 입력
char[] temp = br.readLine().toCharArray();
for(int j =0; j < N; j++) {
map[i][j] = temp[j]-'0';
}
}
check(0, 0, N);
System.out.println(sb);
}
public static void check(int x, int y, int size) {
if(zip(x, y, size)) {
sb.append(map[x][y]);
return;
}
int half = size/2;
sb.append("(");
check(x, y, half); // 1사분면
check(x, y+half, half); // 2사분면
check(x+half, y, half); // 3사분면
check(x+half, y+half, half); // 4사분면
sb.append(")");
}
public static boolean zip(int x, int y, int size) {
int color = map[x][y]; // 배열의 맨 처음 값 저장
for (int i = x; i < x+size; i++) {
for (int j = y; j < y+size; j++) {
if(color != map[i][j]) { // 모두가 같은 값이 아니면
return false;
}
}
}
return true; //모두가 같은 값이면
}
}
풀이
처음에 map의 값이 모두 0 or 1이라면
0 or 1로 압축이 되고
끝나지만 그렇게 쉽게 끝나지 않겠죠?
압축이 되지 않는 경우라면
위의 그림 처럼 4개의 공간으로 나눠서 봅니다.
그런데 그렇게 해도 해결이 안되면 또 나눠서 봐야 됩니다.
어떻게?
이렇게 말입니다.
map을 쓰~윽 봅니다.
map을 봤는데 0 과 1이 섞여 있으니까 4/1 크기로 공간을 나눠줍니다.
4/1 로 나뉜 공간에서도 0과 1이 섞여 있으니까 또 4/1 크기로 공간을 나눠줍니다.
0으로만, 1로만 이루어진 공간은 0 또는 1로 압축합니다.
아닌 공간은 또 나눠 줍니다.
이제 1칸 만 남으니 그 공간은 압축된 것과 같으니 값을 적어줍니다.
남은 공간들에서도 위의 과정을 반복합니다.
그 공간이 다 같은 값으로 이루어져 있어
압축 할 수 있는지 검사하는 부분
public static boolean zip(int x, int y, int size) {
int color = map[x][y];
for (int i = x; i < x+size; i++) {
for (int j = y; j < y+size; j++) {
if(color != map[i][j]) {
return false;
}
}
}
return true;
}
압축되지 않는다면
4/1 공간으로 나눠서 검사하기 위해
분리되는 부분
int half = size/2;
check(x, y, half); // 1사분면
check(x, y+half, half); // 2사분면
check(x+half, y, half); // 3사분면
check(x+half, y+half, half); // 4사분면
