2020. 3. 19. 15:47ㆍ낙서장
문제
먼저는 로그인을 해야 문제를 보고 풀 수 있다
문제 요약
현재 줄에서 괄호 갯수 차이에 따라 다음 줄 왼쪽에 " . " 이 붙는 갯수가 달라진다.
현재까지 줄에서 ( 개수를 a, ) 개수를 b, { 개수를 c, } 개수를 d, [ 개수를 e, ] 개수를 f 라고 할 떄
소괄호에는 R, 중괄호에는 C, 대괄호에는 S 를 ( 0 <= R, C, S <= 20 ) 각각 곱해서
R*(a-b) + C*(c-d) + S*(e-f) 를 들여쓰기하는 것이다.
마스터가 스타일리쉬하게 " . " 으로 들여쓰기를 한 것을 보고
"나"도 따라하려고 한다.
내가 쓴 글의 줄마다 " . " 으로 들여쓰기 해야하는 숫자를 출력해야한다.
마스터의 글을 보고 들여쓰기를 따라 할 수 없는 줄은 -1 을 출력한다.
전체 코드
from itertools import product
for t in range(1,int(input())+1):
# 기본 입력
p,q = map(int,input().split())
Master = [input() for _ in 'a'*p]
Me = [input() for _ in 'a'*q]
# Master . 갯수, (){}[] 갯수
a=b=c=0
Master_dot=[]
Master_bracket=[[0,0,0]]
for i1 in Master:
Master_dot.append(len(i1)-len(i1.lstrip('.')))
for j1 in i1:
if j1=='(':a+=1
if j1==')':a-=1
if j1=='{':b+=1
if j1=='}':b-=1
if j1=='[':c+=1
if j1==']':c-=1
Master_bracket.append([a,b,c])
# R,C,S 가능성 있는 것들
candidate=[]
# 가능한 모든 R,C,S
for i2 in product(range(1,21), repeat=3):
R1,C1,S1=i2
for j2 in range(1,p):
a1,b1,c1=Master_bracket[j2]
if R1*a1+C1*b1+S1*c1!=Master_dot[j2]:
break
else:
candidate.append([R1,C1,S1])
# Me (){}[] 갯수
d=e=f=0
Me_bracket=[]
for i3 in Me:
for j3 in i3:
if j3=='(':d+=1
if j3==')':d-=1
if j3=='{':e+=1
if j3=='}':e-=1
if j3=='[':f+=1
if j3==']':f-=1
Me_bracket.append([d,e,f])
# 가능성 있는 것들에 대해서 나올 수 있는 점들
Me_dot=[set() for _ in'a'*q]
for i4 in range(q):
d1,e1,f1=Me_bracket[i4]
for j4 in candidate:
R2,C2,S2=j4
Me_dot[i4].add(R2*d1+C2*e1+S2*f1)
if candidate==[]:
Me_dot[i4]=-1
elif len(Me_dot[i4])==1:
Me_dot[i4]=Me_dot[i4].pop()
else:
Me_dot[i4]=-1
# Me_dot 중 마지막 갯수는 필요 없다
# 처음에는 0 이 온다
Me_dot=[0]+Me_dot[:-1]
print('#%i'%t,*Me_dot)문제 해설 1
마스터의 현재 줄까지 괄호 갯수를 처리해도 들여쓰기는 다음 줄에 적용되므로 한 번에 적용할 수 없다.
현재 줄까지의 괄호 갯수를 다음 줄의 들여쓰기한 . 개수와 비교해야 한다.
그래서 쉽게 비교할 수 있도록 첫 들여쓰기가 괄호 갯수가 없는 것이므로 0, 0, 0 을 초기값에 넣어준다.
# Master . 갯수, (){}[] 갯수
a=b=c=0
Master_dot=[]
Master_bracket=[[0,0,0]]
for i1 in Master:
Master_dot.append(len(i1)-len(i1.lstrip('.')))
for j1 in i1:
if j1=='(':a+=1
if j1==')':a-=1
if j1=='{':b+=1
if j1=='}':b-=1
if j1=='[':c+=1
if j1==']':c-=1
Master_bracket.append([a,b,c])문제 해설 2
가능한 R, C, S 를 구해야 한다.
가지고 있는 조건을 가지고 여러가지 공식을 대입하여 구할 수도 있으나 (ex 크래머 공식 등)
너무 복잡하고
가능한 R, C, S 가 각각 1 ~ 20 까지 총 8000 개 이므로
브루트포스로 해결하기로 한다
from itertools import product
# R,C,S 가능성 있는 것들
candidate=[]
# 가능한 모든 R,C,S
for i2 in product(range(1,21), repeat=3):
R1,C1,S1=i2
for j2 in range(1,p):
a1,b1,c1=Master_bracket[j2]
if R1*a1+C1*b1+S1*c1!=Master_dot[j2]:
break
else:
candidate.append([R1,C1,S1])for R1 in range(1,21):
for C1 in range(1,21):
for S1 in range(1,21):
# 이렇게 해도 가능하다문제 해설 3
가능한 R, C, S 를 알고 있으니
"내"가 쓴 글에서 괄호 갯수를 파악해야 한다.
# Me (){}[] 갯수
d=e=f=0
Me_bracket=[]
for i3 in Me:
for j3 in i3:
if j3=='(':d+=1
if j3==')':d-=1
if j3=='{':e+=1
if j3=='}':e-=1
if j3=='[':f+=1
if j3==']':f-=1
Me_bracket.append([d,e,f])문제 해설 4
가능한 R, C, S 를 가지고 얼마나 들여쓰기 해야하는지 계산해보자
값이 유일하면 그대로 저장하고 유일하지 않다면 -1 을 저장한다
# 가능성 있는 것들에 대해서 나올 수 있는 점들
Me_dot=[set() for _ in'a'*q]
for i4 in range(q):
d1,e1,f1=Me_bracket[i4]
for j4 in candidate:
R2,C2,S2=j4
Me_dot[i4].add(R2*d1+C2*e1+S2*f1)
if candidate==[]:
Me_dot[i4]=-1
elif len(Me_dot[i4])==1:
Me_dot[i4]=Me_dot[i4].pop()
else:
Me_dot[i4]=-1문제 해설 5
마무리를 짓는다
첫 문장은 들여쓰기를 하지 않고 마지막 들여쓰기는 필요없으므로 이를 각각 처리한다
# Me_dot 중 마지막 갯수는 필요 없다
# 처음에는 0 이 온다
Me_dot=[0]+Me_dot[:-1]
print('#%i'%t,*Me_dot)후기
머리를 써서 쉽게 구하려 하니 자꾸 반례가 생겨서 힘들었다.
상황이 복잡하다면 브루트 포스를 활용하는 것도 문제를 해결 할 때 좋은 것 같다.
아직 알고리즘 공부가 어렵다.