[백준] #2800 괄호 제거 (python)

2800번: 괄호 제거 (acmicpc.net)

2800번: 괄호 제거

 

그놈의 괄호 미쳐버리겠는데 여전히 못 푼다. ㅋ

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

 

예제 입력1

(0/(0))

예제 출력1

(0/0)
0/(0)
0/0

예제 입력2

(1+(2*(3+4)))

예제 출력2

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

 

---

 

# Code

 

sol1 - result를 처음부터 set으로 생성한 후 마지막에 list 형태로 바꿔 줌

from itertools import combinations

data = list(input())

stack = []
index = []
result = set() # ((2)) 같은 경우 중복 문자열 발생. 중복 제거
for i in range(len(data)):
    if data[i] == '(':
        stack.append(i)
    elif data[i] == ')':
        index.append((stack.pop(),i))

for i in range(1, len(index)+1):
    com = list(combinations(index, i)) # 조합 사용해서 제거할 괄호 쌍 뽑아내기
    for c in com:
        temp = data[:] # 문자열 복사
        for x,y in c:
            temp[x] = '' # 해당 인덱스 값(즉, 제거할 괄호) 공백 처리
            temp[y] = ''
        result.add(''.join(temp)) # 괄호 제거한 문자열들을 result에 집어 넣음  

result = list(result) # set 형태에선 sort를 쓸 수 없어서 list로 바꿔줌
result.sort()
for i in result:
    print(i)

 

sol2 - result를 list로 생성한 후 마지막에 set 형태로 바꿔 줌

from itertools import combinations

data = list(input())

stack = []
index = []
result = []
for i in range(len(data)):
    if data[i] == '(':
        stack.append(i)
    elif data[i] == ')':
        index.append((stack.pop(),i))

for i in range(1, len(index)+1):
    com = list(combinations(index, i)) # 조합 사용해서 제거할 괄호 쌍 뽑아내기
    for c in com:
        temp = data[:] # 문자열 복사
        for x,y in c:
            temp[x] = '' # 해당 인덱스 값(즉, 제거할 괄호) 공백 처리
            temp[y] = ''
        result.append(''.join(temp)) # 괄호 제거한 문자열들을 result에 집어 넣음  

result = set(result) # ((2)) 와 같은 경우 중복된 문자열이 생기기 때문에 이를 제거해주기 위해 set 형태로 바꿔줌
for i in sorted(result): # set에서는 result.sort()와 같이 쓸 수 없고 sorted(result) 와 같은 형태로 써야 함
    print(i)

 

# Comment

그냥 set으로 선언했냐 list로 선언했냐 그 차이인데 sort() 라던지 sorted 라던지 배열 형태에 따라서 각 함수의 사용법을 알게 되어서 나중에도 보려고 같이 올려놨다.

list 의 경우 list.sort() 형태로 사용 가능한데, set 의 경우 sorted(set) 으로 사용해야 한다.

아.. 알고 보면 그렇게 막 어렵지는 않은데 조합을 사용할 생각을 못했다.

처음에 삭제 할 괄호의 index를 뽑아서 제거해야 한다는 것 까지는 생각했는데, 예시와 같은 출력 형태가 되도록 하려면 어떻게 짜야 할지 정말 고민했는데.. 모르겠어서 다른 분들 코드를 참고했다. 근데 조합을 써야겠다는 생각을 1도 못해서..(수포자 우짤래미) 포기하고 참고하길 잘한 것 같다.. ㅎㅎ..

data : 입력 받은 문자열

stack : 입력 문자열을 검사할 때 괄호가 나오면 해당 인덱스를 저장하는 배열

index : 제거 할 괄호들의 인덱스 쌍을 저장하는 배열

temp : data 배열을 복사하여 해당하는 괄호 쌍들을 제거한 문자열

result : 괄호 쌍이 제거된 문자열들을 저장한 배열

1. 입력 문자열을 data 배열에 받아서 ' ( ' 가 나올 경우 stack 배열에 "인덱스" 를 넣어주고, ' ) ' 가 나올 경우엔 index 배열에 ' ( ' 의 인덱스와 ' ) ' 의 인덱스를 넣어준다. 만약 ' ( 0 / ( 0 ) ) ' 이라면 index = [(3,5), (0,6)]

2. 1부터 index 배열의 크기만큼 괄호 쌍의 조합을 생성해서 입력받은 문자열을 복사한 temp에서 해당 인덱스(즉, 괄호)를 제거하고 그 문자열을 result에 추가해준다.

3. ((2)) 같은 경우 index = [(1,3), (0,4)] 두 쌍이 나오지만 결국 (1,3) 을 제거해도 '(2)', (0,4)를 제거해도 '(2)' 이므로 중복이 생기기 때문에 result를 set으로 바꿔서 중복을 제거해준다.

4. 오름차순으로 정렬해주기 위해서 sort 함수를 사용한다.

 

** 휴.. 과정 자체를 이해하는건 어렵지 않았는데.. 아직 파이썬 문법이 익숙하지 않은 탓인지 ㅠㅠ 

com = list(combinations(index, i))

 이 구간에서 i가 1일 경우를 출력해봤는데 ....

내가 생각할땐 [((3, 5)) , ((0, 6))] 가 나올 줄 알았는데 .. 으잉? [((3, 5),), ((0, 6),)]  .. 이게 뭐람 .. ? ,) 는 대체 왜 껴있는걸까.. 근데 도대체 이따구로 출력되는데 왜 잘 돌아가는 걸까.....

저 ) 는 알아서 빼고 숫자만 뽑아내서 괄호를 알아서 제거해주는 걸까..... 백준 질문 게시판에 검색해봤는데 아무 내용이 없어서... 아직 잘 이해가 안된다 이 부분이..... ㅠㅠ .... ㅋㅋㅋㅋ ㅠㅠ 파이썬 너무 어려운 것 같다.......