271. 쿼드트리
1) 어떤 전략(알고리즘)으로 해결?
2) 코딩 설명
<내 풀이>
import sys
n = int(sys.stdin.readline())
mapp = list( list(map(int,sys.stdin.readline().rstrip())) for _ in range(n))
lis = []
def is_it_all_zero(rowstart,colstart,leng) :
real = 0
for r in range(rowstart,rowstart+leng) :
for c in range(colstart, colstart+leng) :
real+=(mapp[r][c])
return real==0
def is_it_all_one(rowstart,colstart,leng) :
tobesame = 0
real = 0
for r in range(rowstart, rowstart+leng) :
for c in range(colstart, colstart+leng) :
real+=(mapp[r][c])
tobesame+=1
return real==tobesame
def chk(rowstart, colstart, leng) :
if leng==1:
print(mapp[rowstart][colstart], end="")
return
num = mapp[rowstart][colstart]
for r in range(rowstart, rowstart+leng) :
for c in range(colstart, colstart+leng) :
if num!=mapp[r][c]:
print("(", end="")
for i in range(2) :
for j in range(2) :
chk(rowstart+(i*leng//2) , colstart+(j*leng//2) , leng//2)
print(")", end="")
return
print(mapp[rowstart][colstart], end="")
return
if(is_it_all_one(0,0,n)) :
print(1)
exit(0)
elif (is_it_all_zero(0,0,n)) :
print(0)
exit(0)
chk(0,0,n)
< 내 틀렸던 풀이, 문제점>
16% 틀림
from collections import deque
import sys
n = int(sys.stdin.readline())
mapp = list( list(map(int,sys.stdin.readline().rstrip())) for _ in range(n))
lis = []
def is_it_all_zero(rowstart,colstart,leng) :
real = 0
for r in range(rowstart,rowstart+leng) :
for c in range(colstart, colstart+leng) :
real+=(mapp[r][c])
return real==0
def is_it_all_one(rowstart,colstart,leng) :
tobesame = 0
real = 0
for r in range(rowstart, rowstart+leng) :
for c in range(colstart, colstart+leng) :
real+=(mapp[r][c])
tobesame+=1
return real==tobesame
def chk(rowstart, colstart, leng) :
eachlis=[]
if is_it_all_one( rowstart , colstart , leng ) :
eachlis.append(1)
lis.append(eachlis)
elif is_it_all_zero( rowstart , colstart , leng ) :
eachlis.append(0)
lis.append(eachlis)
else :
for i in range(2) :
for j in range(2) :
chk(rowstart+(i*leng//2) , colstart+(j*leng//2) , leng//2)
lis.append(eachlis)
chk(0,0,n)
stack=deque()
e=0
reallist=[]
while e<len(lis) :
if len(lis[e])==0:
result = deque()
while e<len(lis) and len(lis[e])==0 :
if len(stack)>=4:
result.appendleft(list(stack)[len(stack)-4:len(stack)])
for s in range(4):
stack.pop()
else :
result.appendleft(list(stack)[0:len(stack)])
for s in range(len(stack)) :
stack.pop()
e+=1
reallist.append(list(result))
else :
stack.append(lis[e][0])
e+=1
print(str(reallist).replace(",","").replace("[", "(").replace("]",")").replace(" ", "").strip())
16%~~
from collections import deque
import sys
n = int(sys.stdin.readline())
mapp = list( list(map(int,sys.stdin.readline().rstrip())) for _ in range(n))
lis = []
def is_it_all_zero(rowstart,colstart,leng) :
real = 0
for r in range(rowstart,rowstart+leng) :
for c in range(colstart, colstart+leng) :
real+=(mapp[r][c])
return real==0
def is_it_all_one(rowstart,colstart,leng) :
tobesame = 0
real = 0
for r in range(rowstart, rowstart+leng) :
for c in range(colstart, colstart+leng) :
# print(r,c, rowstart, colstart)
real+=(mapp[r][c])
tobesame+=1
return real==tobesame
def chk(rowstart, colstart, leng) :
eachlis=[]
if is_it_all_one( rowstart , colstart , leng ) :
#eachlis.append(1)
lis.append(1)
elif is_it_all_zero( rowstart , colstart , leng ) :
#eachlis.append(0)
lis.append(0)
else :
for i in range(2) :
for j in range(2) :
# 0과 1 섞인 상황
chk(rowstart+(i*leng
lis.append(eachlis)
if(is_it_all_one(0,0,n)) :
print(1)
exit(1)
elif (is_it_all_zero(0,0,n)) :
print(0)
exit(1)
chk(0,0,n)
#print(lis)
stack=deque()
e=0
reallist=[]
while e<len(lis) :
if (lis[e])==[]:
result = deque()
while e<len(lis) and (lis[e])==[] :
if len(stack)>=4:
result.appendleft(list(stack)[len(stack)-4:len(stack)])
for s in range(4):
stack.pop()
else :
result.appendleft(list(stack)[0:len(stack)])
for s in range(len(stack)) :
stack.pop()
e+=1
#print(list(result) )
#print("hihi ",list(result)[1:len(result)])
# reallist.append(list(result))
before=[]
for r in result :
if len(r)==1:
before.append(r[0])
else :
before.append(r)
#print("before : ",before)
if len(before)==1:
reallist.append(before[0])
else :
for b in before :
if type(b)==int :
reallist.append(b)
before.remove(b)
if len(before)==1:
reallist.append(before[0])
else : reallist.append(before)
#else :
#reallist.append(before)
else :
stack.append(lis[e])
e+=1
#print(list(reallist))
reallist=(str(reallist).replace(",","").replace("[", "(").replace("]",")").replace(" ", ""))
print("".join(list(reallist))[1:len(reallist)-1])
<반성 점>
<배운 점>
