[python] 3826 - 스타일리시

3826번: 스타일리시 (acmicpc.net)

3826번: 스타일리시

 

이해가 어려웠던 문제였다.

시간도 굉장히 오래 걸리고

시간초과로 애를 먹었던 문제였다.

 

일단 접근법은 다음과 같다.

 

1. RCS의 값을 어떻게 구하는가?

2. 주어진 스타일리시 프로그램의 인덴트 스타일을 다른 프로그램 Q에 어떻게 적용하는가?

3. 인덴트의 양을 유일하게 결정할 수 없는 줄은 어떤 경우인가?

 

 

1.

우선, 1번은 이해하는데 까지 굉장히 오래 걸렸다.

 RCS의 값은 정해져 있지 않았다는 것이 이 문제의 첫 번째 핵심이다.

문제를 보면 범위 값이 (1 ≤ R,C,S ≤ 20) 주어진다.

즉 모두 1부터 20까지 가능하다는 것이다.

그래서 중복 순열을 사용하여 모든 경우의 수를 구해보기로 하였다.

 

그리고 마스터 프로그램 각 줄의 인덴트 배열을 구한 후

위에서 구한 RCS 값을 적용하여 구한 인덴트 배열이 같다면

이 RCS는 마스터 프로그램의 인덴트 스타일이 될 수 있다는 뜻이다.

 

예를 들어, 마스터 프로그램의 각 줄의 인덴트 배열이 [0,2,5,1]이라고 치자.1부터 20까지 3개의 수 (RCS)를 구해 그 값으로 마스터 프로그램 각 줄의 인덴트 양을 파악하여 또 다른 배열에 저장한다.이때 두 배열이 같다면 구해진 RCS는 마스터 프로그램의 인덴트 스타일이다.

 

 

2 & 3.

1번을 통해 구한 인덴트 스타일(RCS)를 이용하여 프로그램 Q의 인덴트 배열을 구한다.여기서 주의할 점은 처음에는 인덴트 스타일이 하나만 존재하는 줄 알았는데그게 아니었다.

 

이 이슈는 3번과도 이어진다. 1) 조건을 만족하는 RCS 값은 여러개가 될 수 있다. 그리고 그 인덴트 스타일을 프로그램 Q에 적용하여 각 줄의 인덴트 양을 담은 배열을 구했을 때계속 값이 변하는 인덱스가 존재한다. 그럼 그 줄의 인덴트 양은 일정하지 않기 때문에 3번에서 말하는 조건에 해당하게 된다.

 

 

접근하기까지 오랜 시간이 걸렸으나위의 방식대로 코드를 짰는데 계속 시간초과가 났다.RCS 값이 여러개일 때, 이를 다른 프로그램 Q에 적용한다면두 가지 경우의 수가 있을 것이다.

1. 모든 RCS 값에 대한 인덴트 배열들이 모두 같다.

2. 모든 RCS 값에 대한 인덴트 배열들 중 다른 것이 존재한다. (= 계속 값이 바뀌는 인덱스가 존재한다.)

 

중복된 값들이 존재하기 때문에 그 값들은 계산하지 않도록 한다면

시간이 많이 단축될 것 같았다.

그런데 리스트랑 집합을 혼용해서 쓰다보니 쉽사리 해결이 되지 않았고

 

리스트 안에 집합을 넣어 계산하는 식으로 해결할 수 있었다.

자세한 부분은 코드를 보면 확인할 수 있다.

 

# 3826 스타일리시
from itertools import product
import sys
input = sys.stdin.readline


#인덴트 스타일 구하기
def get_indent():  
    all_indent=[] 
    for pro in product(range(1, 21), repeat=3):
        rcs=[0]
        r1,r2=0,0
        c1,c2=0,0
        s1,s2=0,0
        for i in range(len(master)):
            if i != 0:
                tmpRcs = pro[0]*(r1-r2)+pro[1]*(c1-c2)+pro[2]*(s1-s2)
                rcs.append(tmpRcs)
                
            # 원래 인덴트 스타일과 중복순열로 구한 인덴트 스타일 원소가 같다면 계속 진행
            if indentArr[i] == rcs[i]:
                for j in range(len(master[i])):
                    if master[i][j] == "(":
                            r1+=1
                    elif master[i][j] == ")":
                            r2+=1
                    elif master[i][j] == "{":
                            c1+=1
                    elif master[i][j] == "}":
                        
                            c2+=1
                    elif master[i][j] == "[":
                            s1+=1
                    elif master[i][j] == "]":
                            s2+=1
            else:
                break
        if indentArr == rcs:
            all_indent.append(list(pro))
    return all_indent


# q_indent 배열 구하기
def q_indent(all_indent):
    total=[set() for _ in range(q)]
    total[0].add(0)
    for i in range(len(all_indent)):
        r,c,s = all_indent[i]
        # rst_indent_arr=[0]
        r1,r2=0,0
        c1,c2=0,0
        s1,s2=0,0
        
        for i in range(len(other)):
            if i != 0:
                tmpRcs = r*(r1-r2)+c*(c1-c2)+s*(s1-s2)
                total[i].add(tmpRcs)
                
            for j in range(len(other[i])):
                if other[i][j] == "(":
                        r1+=1
                elif other[i][j] == ")":
                        r2+=1
                elif other[i][j] == "{":
                        c1+=1
                elif other[i][j] == "}":
                        c2+=1
                elif other[i][j] == "[":
                        s1+=1
                elif other[i][j] == "]":
                        s2+=1
    
    return total

## main
while True:
    p,q = map(int, input().split())
    
    if p==q==0:
        break
    
    master = [input().strip() for _ in range(p)]
    other=[input().strip() for _ in range(q)]
    
    #마스터의 인덴트 개수 배열
    indentArr=[]
    
    for line in master:
        cnt=0
        for j in line:
            if j == '.':
                cnt+=1
            else:
                break
        indentArr.append(cnt)
    
    # 모든 indent 스타일 [r,c,s] 배열
    indent=get_indent()
    total_indent=q_indent(indent)
 
 
    # 모든 indent 후보군에 대하여 유일성 검사
    rst=[]
    for i in total_indent:
        if len(i)>1:
            rst.append(-1)
        else:
            rst.append(list(i)[0])
    print(*rst)

 

 

 

 

불굴의 한국인!!

몇 시간을 들여 해결했는데 기분이 좋았다.

더 간단하게 코드를 짤 수 있는 방법을 알고 싶다.

 

 

 

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview