파이썬 알고리즘 163번 | [백준 2800번] 괄호 제거 - STACK

163. 괄호 제거

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

import sys
from itertools import combinations

inp=list(map(str,sys.stdin.readline().rstrip()))
save=[] #인덱스 순서쌍 저장 
stk=[] #"(" 저장할 공간 
for i in range(len(inp)) :
    if inp[i]=="(" :
        stk.append(i)
    elif inp[i]==")" :
        save.append([stk.pop(),i])

res=[] #결과 담을 리스트 

for i in range(1,len(save)+1): #나온 순서쌍 갯수만큼 돌면서 
    #세쌍의 괄호 순서쌍이 있다면 
    # 하나 뽑을 때, 두개 뽑을 때, 세개 뽑을 때,,각 조합의 경우 구하기
    aftercombination= list(combinations(save, i))
    #print(list(aftercombination))
    for j in aftercombination : # 조합의 경우를 돌면서, 해당 인덱스를 발견한다면 
        #print(j)
        inpcpy2 = inp.copy()
        #원본 인풋을 복사해놓은 인풋의 값에서 조합 인덱스 해당하는 괄호 없애주기
        #print(inpcpy)
        for e,s in j :
            #print(e,s)
            inpcpy2[e]=""
            inpcpy2[s]=""
            res.append("".join(inpcpy2))

#print(res)
res=list(set(res)) 
#중복 제거해주기 위해 집합으로 바꿨다가
#정렬 위해 다시 리스트로 변경
res.sort()
#사전 순 정렬을 위해 진행 (안해주면 틀리더라)
for i in res:
    print(i)

• 처음에 순서쌍 찾는 것을 틀렸었나 보다.
• 스택을 사용해서 바꿔주었다.

<내 틀렸던 풀이, 문제점>

import sys
from itertools import combinations

inp=list(map(str,sys.stdin.readline().rstrip()))
save=[] #인덱스 순서쌍 저장 

#1) 인덱스 나오는 위치 순서쌍으로 저장 
inpcpy0=inp.copy()
for i in range(len(inp)-1,-1,-1) : 
    if inpcpy0[i]==")" : # i번째에서 "(" 를 발견하면 
        for j in range(i-1) :
            if inpcpy0[j]=="(" : #")" 가장 처음부터 i-1까지 돌면서 최초의 "(" 만나면 순서 저장
                save.append([i,j])
                inpcpy0.pop(j)
                inpcpy0.insert(j,'-1')
                break

res=[] #결과 담을 리스트 

for i in range(1,len(save)+1): #나온 순서쌍 갯수만큼 돌면서 
    #세쌍의 괄호 순서쌍이 있다면 
    # 하나 뽑을 때, 두개 뽑을 때, 세개 뽑을 때,,각 조합의 경우 구하기
    aftercombination= list(combinations(save, i))
    #print(list(aftercombination))
    for j in aftercombination : # 조합의 경우를 돌면서, 해당 인덱스를 발견한다면 
        #print(j)
        inpcpy2 = inp.copy()
        #원본 인풋을 복사해놓은 인풋의 값에서 조합 인덱스 해당하는 괄호 없애주기
        #print(inpcpy)
        for e,s in j :
            #print(e,s)
            inpcpy2[e]=""
            inpcpy2[s]=""
            res.append("".join(inpcpy2))

#print(res)
res=list(set(res)) 
#중복 제거해주기 위해 집합으로 바꿨다가
#정렬 위해 다시 리스트로 변경
res.sort()
for i in res:
    print(i)

• 6퍼만 가면 틀렸대,

<반성 점>

<배운 점>