1.
분할 정복 문제
완전탐색으로 풀 수 있지만, 효율적으로 문제를 풀기 위한 방법을 고안하자.
2.
자세한 풀이는 책 참고 (p.193)
- 무식한 방법은 쿼드 트리 압축을 풀어 실제 그림을 만들고 이를 반전하고 다시 압축하는 것
- 그러나, N이 엄청 클 때 점 하나만 다른 색이라면 매우 비효율적
- 압축을 다 풀지 않고 뒤집는다면?
- 1, 2, 3, 4분면이 3, 4, 1, 2사분면으로 바뀌는 아이디어
문자열 입력 부분에서 에러가 나서 뭐가 문제인지 고민을 많이 했다.
sc.nextInt()에서 정수를 입력받은 뒤 엔터를 입력하면 개행 문자가 다음 sc.nextLine()의 입력으로 들어가 버린다.
이를 해결하기 위해 정수를 입력받고 나서 sc.nextLine()을 한번 실행 해주자.
3.
import java.util.Scanner;
public class QUADTREE {
static String quadtree;
static int it;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
sc.nextLine(); // 개행문자
for (int i = 0; i < c; i++) {
quadtree = sc.nextLine();
it = 0;
System.out.println(reverse());
}
sc.close();
}
static String reverse() {
char head = quadtree.charAt(it);
if (head == 'w' || head == 'b') {
return head + "";
}
it++;
String first = reverse();
it++;
String second = reverse();
it++;
String third = reverse();
it++;
String fourth = reverse();
return "x" + third + fourth + first + second;
}
/*
주어진 문자열을 가지고 그림을 그려보는 함수
그러나, N이 엄청 클 때 점 하나만 다른 색이라면 매우 비효율적이다.
static int decompress(String quadtree, int it, int y, int x, int size) {
char head = quadtree.charAt(it);
it += 1; // 교재에서는 iterator을 사용했으나 여기서는 it을 통해 참조할 위치를 정하기
if (head == 'w' || head == 'b') {
for (int dy = 0; dy < size; dy++) {
for (int dx = 0; dx < size; dx++) {
decompressed[y + dy][x + dx] = head;
}
}
} else {
int half = size / 2;
it = decompress(quadtree, it, y, x, half); // 1사분면
it = decompress(quadtree, it, y, x + half, half); // 2사분면
it = decompress(quadtree, it, y + half, x, half); // 3사분면
it = decompress(quadtree, it, y + half, x + half, half); // 4사분면
}
return it;
}
*/
}
4.
[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만)
'Algorithm' 카테고리의 다른 글
| [Java] 백준 14888 : 연산자 끼워넣기 (0) | 2021.02.01 |
|---|---|
| [Java] 알고스팟 : FENCE (0) | 2021.01.27 |
| [Java] 알고스팟 : CLOCKSYNC (0) | 2021.01.21 |
| [Java] 알고스팟 : BOARDCOVER (0) | 2021.01.19 |
| [Java] 알고스팟 : PICNIC (0) | 2021.01.15 |
