문제를 처음 봤을 때 든 생각은
.
.
.
이걸 어케 하노
처음 보는 유형의 문제였다. 이전에 풀어왔던 문제들처럼 문자열 순회하면서 조건문 따져주면 되나? 라는 생각도 해보고 특정한 규칙이 있나? 라는 생각도 해보고 .. 20분 동안 그냥 문제만 계속 쳐다봤다.
정현이 형 말이 떠올랐고 이대로 문제만 보고 생각만 하다가는 또 내일 아침에도 이걸 보고 있겠다 싶어서 문제 분류를 봤다.
(답지 보는 건 선 넘는거야 진짜... 절대 그러지 말자
딱 2시간, 맥시멈 2시간 잡고 그래도 못풀면? 그 때 답지 보는 걸로 하자)
이게 그 말로만 듣던 스택 문제구나 싶었다.
뭐 대충 짝 맞으면 pop 해주고 이런 느낌인가? 싶었다.
하지만..!!
계속 짱구를 굴리다 보니 개수를 세어주는 로직을 생각해냈고 !!
값을 실제로 넣고 빼고 (append, pop) 해줄 필요가 굳이.. 없지 않나? 라는 생각을 했고 !!
"(" -> push : int 변수 ++ 연산
"()" -> 계산 : 이전까지의 "(" 개수 (위에서의 int 변수) += 연산
")" -> pop : 마지막 슬라이스(끄트머리)가 될 거니까 answer ++ 연산
완벽하다 생각했다. 도저히 틀릴 수가 없다 생각했다.
코드로 옮기는데는 5분? 정도 걸린 것 같다.
내가 짠 코드
inputStr = input()
answer = 0
openCharCnt = 0
for i in range(len(inputStr)):
if i == len(inputStr)-1:
# i + 1 하면 에러, 젤 마지막은 무조건 ")" 이겠지
answer += 1
break
if inputStr[i] == "(":
# "(" 일 때
if inputStr[i+1] == ")":
# () 일 때
# print("계산하기")
answer += openCharCnt
# 계산하기
else:
# (( 일 때
# print("push")
openCharCnt += 1
else:
# ")" 일 때
if inputStr[i-1] == "(":
continue
# print("pop 하고 개수 1 추가")
openCharCnt -= 1
answer += 1
# print("openCharCnt = ",openCharCnt)
# print("answer = ", answer)
print(answer)바로 맞췄습니다!!! 가 나왔는데.. 똥 덜 닦은거 마냥 뭔가 아쉽다.
코드를 짤 때 자꾸 걸리는 부분?(예외라고 생각하는 부분)들을 if 조건문을 걸어주면서 계속 써내려간다. 결국 답은 맞추지만 코드가 좀 더럽다..ㅠ 이 모든걸 아울러서 한방에 정리되는? 그런 로직을 짜야 하는데.. 다른 사람들의 코드를 많이 보는 수 밖에 없나!!!
깔끔한 정답 코드
bar_razor = list(input())
answer = 0
stack = []
for i in range(len(bar_razor)):
if bar_razor[i] == '(': #스택 쌓기
stack.append('(')
else:
if bar_razor[i-1] == '(': #()라면 (를 pop하고 현재 스택에 들어있는 ( 수만큼 값을 더해준다.
stack.pop()
answer += len(stack)
else:
stack.pop()
answer += 1 #끄트머리 막대기 부분을 더해준다
print(answer)확실히 깔끔하다. 답지를 보고 나면 보통의 경우에 지이이인짜로 내가 짠 코드랑 딱 한 끗 차이다.
단적으로 예를 들자면, 나와 같은 if 문을 썼을지라도 그걸 어디에다가 둘건지? 어떤 조건을 넣을건지? 와 같은..
정답 코드랑 내가 짠 코드의 차별점을 꼽자면 !?
- 자잘한 예외처리 (if 조건문으로 걸러주는 작업) 없이 로직이 아주 깔끔하다. ( 이걸 잘하는게 진짜 알고리즘을 잘하는게 아닐까 싶다 )
- int 변수 하나 잡아두고 +- 연산을 해서 계산한 나와 달리 직접 stack 을 배열로 구현하여 직접 append, pop을 해서 마지막엔 스택의 길이(개수)를 세어 정답을 낸다.
문자 하나씩 실제로 append 또는 pop 해주면서 스택의 실제 길이를 재야한다고 생각을 못했다. 아니 필요없다 생각했다. 그냥 숫자 변수 하나 잡아두고 +- 해주면 될 거라 생각했다 (어차피 개수니까?)
너무 야매로..? 푼건가..
다음에 또 스택 관련 문제를 풀게 되면 그 땐 list 선언해주고 직접 스택을 구현해서 append, pop 까지 직접 해봐야겠다.
