상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다.
F: 한 눈금 앞으로
B: 한 눈금 뒤로
L: 왼쪽으로 90도 회전
R: 오른쪽으로 90도 회전
L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다.
상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다.
아래 그림에서 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 컨트롤 프로그램이 FLFRFLBRBLB인 경우에 거북이는 아래와 같이 움직인다. 회색으로 빗금친 부분이 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형이다. 넓이는 4가 된다.
거북이가 지나간 영역이 직사각형을 만들지 않는 경우도 있다. 예를 들어, FFLLFF인 경우에 거북이는 y축의 위로만 지나다닌다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생각할 수 있다. 따라서, 선분의 경우에 넓이는 0이 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 있고, 길이는 500을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class JUN8911 {
/* 거북이
F : 한 눈금 앞으로
B : 한 눈금 뒤로
L : 왼쪽으로 90도 회전(전진 X)
R : 오른쪽으로 90도 회전(전진 X)
다 이동한 후에 가장 왼쪽, 가장 오른쪽 차가 가로 길이
가장 상단, 가장 하단의 차가 세로 길이니까
그 둘을 곱한다
* */
static int[][] map;
static int top, bottom, left, right, d;
static int hight, width; // 가로 세로
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine()); // 거북이 조작 횟수
String[] commands = new String[N];
for(int i = 0; i < N; i++){
top = 0;
bottom = 0;
left = 0;
right = 0;
d = 0; // 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽
hight = width = 0;
commands[i] = br.readLine();
tuttle(commands[i]);
sb.append(countArea()).append("\n");
}
System.out.println(sb);
}
// 거북이가 움직인다.
public static void tuttle(String c){
char[] command = c.toCharArray();
for(int i = 0; i < command.length; i++){
char temp = command[i];
if(temp == 'F' || temp == 'B'){
// 명령어가 F와 B 일때만 움직인다
move(command[i]);
} else if(temp == 'L' || temp == 'R'){
// 명령어가 L 과 R 일때는 방향만 바꿔준다.
changeD(command[i]);
}
}
}
// 직사각형 크기 구하기
public static int countArea(){
return (Math.abs(top-bottom)) * (Math.abs(left-right));
}
// 방향 바꿔주기
public static void changeD(char c){
if(c == 'L'){
d++;
} else{
d--;
}
// 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽 범위 넘어가면 수정 해주기
if(d == 4){
d = 0;
} else if(d == -1){
d = 3;
}
}
public static void move(char c){
switch (d){
case 0: // 위 보고 있음
if(c == 'F'){
hight++;
top = Math.max(top, hight);
} else{
hight--;
bottom = Math.min(bottom, hight);
}
break;
case 1: // 왼쪽 보고 있음
if(c == 'F'){
width++;
left = Math.max(left, width);
} else{
width--;
right = Math.min(right, width);
}
break;
case 2: // 밑에 보고 있음
if(c == 'F'){
hight--;
bottom = Math.min(bottom, hight);
} else{
hight++;
top = Math.max(top, hight);
}
break;
case 3: // 오른쪽 보고 있음
if(c == 'F'){
width--;
right = Math.min(right, width);
} else{
width++;
left = Math.max(left, width);
}
break;
}
}
}
풀이
거북이 로봇은 명령을 받아 움직인다.
명령어는 F, B, L, R 이 있다.
그 움직임이 멈춘 후 그 범위를 포함하는
직사각형의 넓이를 구하는게 이 문제이다.
직사각형의 넓이를 구하는 공식은 다들 아시다시피
사각형의 넓이 = 너비 x 높이
그렇죠?
너비는 어떻게 구하죠?
가장 맨 왼쪽부터, 가장 맨 오른쪽까지의 거리겠죠?
높이는 어떻게 구하죠?
가장 위에서, 가장 아래까지의 거리겠죠?
그러면 우리에게 필요한건,
가장 위, 가장 아래, 가장 왼쪽, 가장 오른쪽의 값이 겠죠?
뭘 구해야 할지 알았으니 시작해봅시다.
1. 거북이 로봇을 명령에 따라 움직인다.
뭐 움직이게 하면 다 끝이긴 합니다.
움직임은 크게
1) 전진(F) 과 후진(B)
2) 방향 전환(왼 : L, 오 : R)
입니다.
1) 전진과 후진
public static void move(char c){
switch (d){
case 0: // 위 보고 있음
if(c == 'F'){
hight++;
top = Math.max(top, hight);
} else{
hight--;
bottom = Math.min(bottom, hight);
}
break;
case 1: // 왼쪽 보고 있음
if(c == 'F'){
width++;
left = Math.max(left, width);
} else{
width--;
right = Math.min(right, width);
}
break;
case 2: // 밑에 보고 있음
if(c == 'F'){
hight--;
bottom = Math.min(bottom, hight);
} else{
hight++;
top = Math.max(top, hight);
}
break;
case 3: // 오른쪽 보고 있음
if(c == 'F'){
width--;
right = Math.min(right, width);
} else{
width++;
left = Math.max(left, width);
}
break;
}
}
눈치가 빠른 학생들은 선생님의 초콜릿을 훔쳐 먹었다! 이를 알아챈 선생님은 포스트잇에 현재 초콜릿의 남은 개수를 적어 놓아 학생들이 먹는 일이 없도록 하려고 한다. 다만, 이 숫자를 학생들이 바꿔버릴 수 있기 때문에 특정한 규칙으로 초콜릿의 개수를 적으려고 한다.
초콜릿의 종류는 총 5개 있으며 각각 한라봉(H), 감귤(T), 백년초(C), 키위(K), 녹차(G)이다.
남은 초콜릿의 개수를 적는 규칙은 다음과 같다.
첫 번째 줄에 남아있는 초콜릿의 총 개수를 적고, 바로 뒤에7H(개를 아스키 문자로 형상화한 단어)를 적는다.
초콜릿의 총 개수를 적을 때에는 바로 전 단계에 남아있던 초콜릿의 총 개수의 일의 자리의 값을 진법으로 하여 적는다.
단, 바로 전 단계에 남아있던 초콜릿의 총 개수의 일의 자리의 값이 0 또는 1이라면, 10진법으로 적는다.
두 번째 줄에 남아있는 개수가 많은 순으로 각 초콜릿의 종류에 대응하는 알파벳을 공백 없이 적는다.
남아있는 개수가 0개인 초콜릿의 종류에 대응하는 알파벳은 적지 않는다.
남아있는 개수가 동일한 초콜릿의 종류가 여러 개일 경우에는 알파벳 순으로 먼저 오는 것이 앞으로 오도록 적는다.
남아있는 초콜릿의 총 개수가 0개일 경우에는NULL을 적는다.
이제 선생님을 도와서 포스트잇에 적어야 할 초콜릿의 개수를 출력하는 코드를 작성하자!
제한사항
각 종류별 먹는 초콜릿 수의 합은 처음에 있던 종류별 개수보다 작거나 같음이 보장된다.
입출력 예
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
public class JUN27535 {
/* 제주 초콜릿 지키키
* 이번 단계의 총 갯수를 이전 단계의 총 갯수의 일의 자리 진법으로 바꿔야 함
* 이전 단계의 일의 자리가 0, 1이면 그냥 씀
* 끝에 7H 를 붙임
*
* 그 후 많이 남은 순으로 정렬
* 같은 개수면 알파벳 순으로 정렬
* */
// H : 한라봉, T : 감귤, C : 백년초, K : 키위, G : 녹차
static class Choco implements Comparable<Choco> {
char name;
int num;
public Choco(char name, int num) {
this.name = name;
this.num = num;
}
@Override
public int compareTo(Choco o1) {
// 초콜릿 갯수가 같으면 이름 순
if(this.num == o1.num){
//이름은 오름차순
return this.name - o1.name;
}
// 초콜릿 개수별 내림차순
return o1.num - this.num;
}
}
static int N; // 먹는 횟수
static int sum = 0; // 현재 초콜릿 총합
static StringBuilder sb = new StringBuilder(); // 정답 저장
static ArrayList<Choco> list = new ArrayList<>(); // 초콜릿 저장
static ArrayList<Choco> copied = new ArrayList<>(); // 정렬을 위한 리스트
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 초콜릿 입력
list.add(new Choco('H', Integer.parseInt(st.nextToken())));
list.add(new Choco('T', Integer.parseInt(st.nextToken())));
list.add(new Choco('C', Integer.parseInt(st.nextToken())));
list.add(new Choco('K', Integer.parseInt(st.nextToken())));
list.add(new Choco('G', Integer.parseInt(st.nextToken())));
// 현재 초콜릿 총합 구하기, 50일텐데 그냥 구해주자
for(Choco c : list){
sum+=c.num;
}
// 초콜릿 먹을 횟수 입력
N = Integer.parseInt(br.readLine());
int last = sum%10; //일의 자리 구하기
// 초콜릿 먹기 시작
for(int i =0; i < N; i++){
st = new StringTokenizer(br.readLine());
sum = 0;
// 초콜릿 먹으면서 남아있는 초콜릿 갯수 세기
for(int j = 0; j < 5; j++){
list.get(j).num-=Integer.parseInt(st.nextToken());
sum += list.get(j).num;
}
// 이전 총합의 일의 자리 진법으로 바꾸기
sb.append(change(last, sum)).append("7H").append("\n");
// 정렬 하기
if(sum == 0){
// 남아있는 초콜릿이 없으면 NULL 출력해야함
sb.append("NULL").append("\n");
}else{
sortChoco();
for(Choco c : copied){
// 남아 있지 않으면 체크할 필요가 없음
if(c.num == 0) continue;
sb.append(c.name);
}sb.append("\n");
}
// 현재 총합의 일의 자리 저장
last = sum%10;
}
System.out.println(sb);
}
// 이전 총합의 일의 자리로 진법 바꾸기
public static String change(int last, int sum){
StringBuilder num = new StringBuilder();
if(last == 0 || last == 1){
// 전의 총합의 일의 자리가 0, 1이면 10진법으로 하니까 변환 필요 없음
num.append(sum);
return num.toString();
}else{
if(sum == 0){
return "0";
} else{
// 진법 변환 해주기
while(sum != 0){
num.append(sum%last);
sum/=last;
}
}
// 거꾸로 돌려주기 위해 StringBuilder 사용
return num.reverse().toString();
}
}
// 정렬하기: 초콜릿 많은 순으로 정렬
public static void sortChoco(){
// 원본을 정렬하면 뒤에 초콜릿 먹을때 복잡해지니까 복사해서 사용
copied = (ArrayList<Choco>) list.clone();
Collections.sort(copied);
}
}
풀이
진행 순서를 보면
1. 초콜릿 값 넣기
2. 초콜릿을 먹음.
3. 먹고 남은 초콜릿의 총합을
이전 단계의 초콜릿 총합의 일의 자리 진법으로 변환한 후
'7H'를 붙여서 출력
4. 현재 초콜릿의 개수별로 내림차순으로 정렬,
개수가 같을 경우 알파벳 순으로 정렬
1. 초콜릿 저장하기
저는 우선 초콜릿의 이름과 개수를 저장할 클래스를 만들었습니다.
static class Choco implements Comparable<Choco> {
char name;
int num;
public Choco(char name, int num) {
this.name = name;
this.num = num;
}
}
그 후 ArrayList를 만들어서 초코릿을 이름과 개수를 저장했습니다.
2. 초콜릿 먹기
아까 초콜릿을 저장한 list 에서
초콜릿 개수가 저장된 변수에 먹은 만큼 빼주고
합계를 구했습니다.
3. 현재 남아 있는 초콜릿을 전 단계의 총합의 일의 자리 진법으로 변환하기
이건 글 보다는 그림으로 보시면 편하실 것 같아서 열심히 그려왔습니다.
4. 초콜릿 개수로 정렬하기
현재 남아있는 초콜릿 개수가 많은 순으로 정렬을 하면 됩니다.
다만 초콜릿 개수가 같을 때는
알파벳 순으로 정렬을 해주면 됩니다.
평소에 자주 사용하는 정렬은
그냥 비교 대상이 하나였는데
이번에는 비교 조건이 2개가 되어버렸네요 ㅠㅠ
게다가 비교하는게 List.....
어떻게 해야할까요?
이럴때 자주 사용하는게 바로
CompareTo<T>
static class Choco implements Comparable<Choco> {
char name;
int num;
public Choco(char name, int num) {
this.name = name;
this.num = num;
}
// 이 부분입니다!!!!!
@Override
public int compareTo(Choco o1) {
// 초콜릿 갯수가 같으면 이름 순
if(this.num == o1.num){
//이름은 오름차순
return this.name - o1.name;
}
// 초콜릿 개수별 내림차순
return o1.num - this.num;
}
}
static ArrayList<Choco> list = new ArrayList<>();
public static void main(String[] args){
Collections.sort(copied); // 이렇게 사용하시면 됩니다.
}
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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사분면
