문제 : 백준 10799. 쇠막대기
처음 문제를 접했을 때, 이 문제는 자료구조로 접근해야겠다는 생각은 했다.
문제 자체는 단순해보이는데, 아니 실제로 풀이도 단순하긴 하다. 내가 한 가지 생각을 못해서 해결이 잘안됐을 뿐이지...
여하튼 문제는 이렇다 '('로 시작해서 ')'로 끝나는 쇠막대기가 있다. 그리고 '()'가 나오면 레이저인데, 레이저로는 쇠막대기를 절단한다.
예를 들어, '(())' 가 있으면 쇠막대기는 하나고, 레이저도 하나다.
절단되어 잘려진 조각의 수는 2개가 될 것이다.
처음 풀이는
1. '('가 입력으로 들어오면 스택에 추가한다.
2. ')'가 들어오면 이전에 스택에 추가된 값이 '('이면 레이저로 간주해서 레이저 변수의 개수를 증가시키고, 스택의 마지막 값인 '('는 레이저의 일부분이기 때문에 pop한다.
그리고 부터 막혔다. ')'가 들어왔는데, 2번이었다면 ')'는 입력이 되지 않았으므로 ')'은 들어올 때마다 레이저로 간주되어서 pop하게 되는 것이다. 이러면 stack에 있는 값들은 모두 레이저로 pop 되어 사라질 것이다.
입력된 값의 이전 값은 필요하고, stack에서 pop을 하면 안되고...
결국 다른 사람들 풀이를 찾아봤다. 소스 코드까지는 보지 않았고, 해설만 보는데 아차차... 왜 바보같이 stack에 있는 값에만 집중했을까...
stack으로 푸는 것도 맞지만, stack에만 집중한 나머지 입력값이었던 문자열을 아예 생각 못했다...
현재 인덱스에서 이전 인덱스를 가지고 입력 문자열에 접근하여 판단하면 되는 것을 알고 나니까 문제는 손쉽게 풀렸다.
파이썬 풀이
pipe = input() #입력
res = 0 # 결과
stack = [] # 스택
for i in range(len(pipe)): #입력받은 문자열을 전부 순회
if pipe[i] == '(': # 여는 괄호이면 스택에 추가
stack.append(pipe[i])
else: # 닫는 괄호인 경우
if pipe[i-1] == "(": # 이전 문자가 여는 괄호이면 레이저로 판단
stack.pop() # 쇠막대기가 아닌 레이저의 일부이기 때문에 pop
res += len(stack) # 현재 저장된 스택의 크기만큼을 더해준다.
else:
stack.pop() # 이전 문자가 닫는 괄호이면 쇠막대기가 닫힌 것이므로
res += 1 # 쇠막대기를 pop해주면서 개수를 하나 더해주고 종료
print(res)