https://www.acmicpc.net/problem/1992
시간 2초, 메모리 128MB
input :
- N (1 ≤ N ≤ 64(2^6))
output :
- 영상을 압축한 결과를 출력
조건 :
- 모두 0으로만 되어 있으면 압축 결과는 "0"
- 모두 1로만 되어 있으면 압축 결과는 "1"
- 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며
만약 현재 보는 화면에서 1개라도 다른 값이 존재한다면. 현재 보는 화면을 4분할 하여야 한다.
이 때의 기저 사례는 내가 보는 픽셀이 1개일 떄, n == 1일 때 graph[x][y]값을 리턴 하는 것.
그 외의 경우에는 quadtree() 메소드를 이용해서 4분할 한다.
시작점은 x, y 현재 체크하는 픽셀의 크기는 n
이를 4분할 하면.
1사분면의 경우 x, y, n // 2
2사분면의 경우 x, y + n // 2, n // 2
3사분면의 경우 x + n // 2, y, n // 2
4사분면의 경우 x + n // 2, y + n // 2, n // 2
로 나누어 주어야 한다.
그리고 분할 되는 경우엔 앞뒤로 () 괄호가 생기므로 추가해 주어야 한다.
append를 쓸 때와 extend를 쓸 때는
현재 quadtree는 리스트를 리턴 한다.
이를 append를 이용해서 추가할 경우에는
[] 이 괄호를 포함한 리스트가 추가되는데 이는 2차원 리스트르르 만드는 것과 비슷하다고 생각하자.
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011
['(', ['(', '1', '1', '0', ['(', '0', '1', '0', '1', ')'], ')'], ['(', '0', '0', '1', '0', ')'], '1', ['(', '0', '0', '0', '1', ')'], ')']extend 를 이용하면 []안의 아이템들을 하나씩 추가해주는 것과 동일하다.
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011
['(', '(', '1', '1', '0', '(', '0', '1', '0', '1', ')', ')', '(', '0', '0', '1', '0', ')', '1', '(', '0', '0', '0', '1', ')', ')']extend를 이용해서 내부에 리스트가 존재하지 않게 하면 join을 이용할 수 있다. 문자열도 리스트니까 취급을 해 주는 것 같다.
append의 경우엔 2차원 ? 몇 차원 이상이니ㅏㄲ 문자열로 취급이 불가해서 입력이 리스트라는 에러를 출력한다.
import sys
n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().strip())) for i in range(n)]
ret = []
def quadtree(x, y, n):
if n == 1:
return str(graph[x][y])
result = []
for i in range(x, x + n):
for j in range(y, y + n):
if graph[x][y] != graph[i][j]:
part = n // 2
result.append('(')
result.extend(quadtree(x, y, part))
result.extend(quadtree(x, y + part, part))
result.extend(quadtree(x + part, y, part))
result.extend(quadtree(x + part, y + part, part))
result.append(')')
return result
return str(graph[x][y])
ret.extend(quadtree(0, 0, n))
print("".join(ret))
