[구현] 괄호의 값, 문자열 압축, 자물쇠와 열쇠

1. 괄호의 값

링크 - https://www.acmicpc.net/problem/2504

코드

import sys
input = sys.stdin.readline
s = list(input().rstrip())
stack=[]
answer=0

for i in s:
    if i==')':
        t=0
        if len(stack)==0:
            print(0)
            exit(0)
        while len(stack)!=0:
            top = stack.pop()
            if top=='(':
                if t==0:
                    stack.append(2)
                else:
                    stack.append(2*t)
                break
            elif top=='[':
                print(0)
                exit(0)
            else:
                t = t+int(top)
    elif i==']':
        t=0
        if len(stack)==0:
            print(0)
            exit(0)
        while len(stack)!=0:
            top = stack.pop()
            if top=='[':
                if t==0:
                    stack.append(3)
                else:
                    stack.append(3*t)
                break
            elif top=='(':
                print(0)
                exit(0)
            else:
                t = t+int(top)
    else:
        stack.append(i)


for i in stack:
    if i=='(' or i=='[':
        print(0)
        exit(0)
    else:
        answer+=i
print(answer)

어제 조금 고민하다가 포기하고 다시 풀었다.
(())의 경우에는 2*2로 계산을 해줘야 하는데 어떻게 체크해야할 지 모르겠어서 구선생님의 도움을 받았다. 반복문을 2번 사용해서 풀어야 했었다.

stack에 괄호 뿐만 아니라 숫자 값도 넣어서 계산을 해준다.
처음에 나는 문제를 풀 때 괄호안에 숫자가 있을 때만 고려를 해주었는데 t 변수를 사용해서 괄호가 겹칠 때는 곱하기 연산을 할 수 있도록 구현을 했다.(그렇게 푸셨더라고요..)

꼭 다시 풀어봐야 되... (맞춤법 틀림)

2. 문자열 압축

코드

def solution(s):
    answer = 1000000000
    if len(s)==1:
        return 1
    #문자열 자르는 단위 (최대 절반까지 자를 수 있음)
    for i in range(1,len(s)//2+1):
        tmp=''
        substring=s[0:i]
        count = 1
        #단위로 문자열 개수 세기
        for j in range(i,len(s),i):
            if substring==s[j:j+i]:
                count+=1
            else:
                if count==1:
                    tmp+=substring
                else:
                    tmp+=str(count)+substring
                substring=s[j:j+i]
                count=1
        if count==1:
            tmp+=substring
        else:
            tmp+=str(count)+substring
        answer=min(len(tmp),answer)
        
    return answer

저번에는 뭔 말인지 잘 모르겠어서 포기했는데, 글을 다시 읽어보니까 그대로 구현하면 되는 문제였다.

예외처리도 해주는게 관건~

3. 자물쇠와 열쇠

코드

def rotate (key):
    m = len(key)
    key_copy = [[0]*m for _ in range(m) ]
    #90도 회전 행->열 열->행
    for i in range(m):
        for j in range(m):
            key_copy[j][m-1-i] = key[i][j]
    return key_copy

def attach(x,y,key,lock):
    m = len(key)
    for i in range(m):
        for j in range(m):
            lock[x+i][y+j]+= key[i][j]
def check(lock,m,n):
    #가운데가 모두 1인지 체크하기
    for i in range(m,m+n):
        for j in range(m,m+n):
            if lock[i][j]!=1:
                return False
    return True

def detach(x,y,key,lock):
    m = len(key)
    for i in range(m):
        for j in range(m):
            lock[x+i][y+j]-=key[i][j]

def solution(key, lock):
    answer = False
    n = len(lock)
    m = len(key)
    #2m+n 크기의 자물쇠 리스트를 만듦
    lock_3 = [[0]*(2*m+n) for _ in range(2*m+n)]
    #가운데에 자물쇠 복사하기
    for i in range(m,m+n):
        for j in range(m,m+n):
            lock_3[i][j] = lock[i-m][j-m]
    #이동하면서 확인하기
    for k in range(4):
        for i in range(0,m+n):
            for j in range(0,m+n):
                #자물쇠 맞춰보기
                attach(i,j,key,lock_3)
                if check(lock_3,m,n):
                    return True
                detach(i,j,key,lock_3)
        key = rotate(key)
    return answer

이것도 attach 부분에서 구선생님의 도움을 좀 받았다.
이동-> 키와 자물쇠 합치기 ->체크-> 키와 자물쇠 분리-> 회전의 순으로 알고리즘을 짰는데,이동하는 방법에서 도움을 받았다..ㅎ
빡치지만 재밌었다.