백준 - 10799 쇠막대기 (스택)

 

 

알고리즘 문제 풀이시 규칙을 찾는 습관을 들여보자.

쇠막대기는 레이져를 만나면 그 개수만큼 잘리고 총 개수에 더해진다. 

 

쇠막대기의 시작은 '(' 

쇠막대기의 끝은 ')' 

레이져는 '()' 

 

쇠막대기가 몇개인지 파악해야 한다.

레이져를 만나면 현재까지 '(' 로 표시된 쇠막대기 만큼의 개수가 추가된다.

 

쇠막대기가 몇개인지 파악해야 하므로 '(' 를 어딘가에 저장해야 한다.

쇠막대기는 항상 끝나는 지점 ')' 이 존재하는데 끝이나면 해당 쇠막대기는 저장되어있는 곳에서 제거 되야 한다. 

 

어딘가에 저장해야 하고 제거 해야 한다면 stack과 queue를 떠올려야 한다.

쇠막대기가 제거 될때에는 저장되어있는 곳에서 가장 마지막에 저장된 '('가 제거 된다. (가장 인접한 '('가 방금 들어온 ')'의 한몸이므로)

가장 마지막에 저장된 자료가 제거 되므로 stack을 사용해야한다는 것을 알 수 있다.

 

여기서 다시 규칙으로 돌아가보면,

((( () () )))

이렇게 쇠막대기 3개와 레이져가 2개 존재한다면

쇠막대기 ((( 3개가 레이져 () 를 만나면 총 개수에 +3이 추가 된다. (0+3 = 3)

다시 한번 레이져를 만나서 +3이 추가된다. (3+3= 6)

이후 들어오는 )는 하나당 +1이 추가된다. (6+1=7, 7+1=8, 8+1=9)

이를 통해 위의 입력은 총 9개의 쇠막대기로 분리되는 것을 알 수 있다.

 

위 규칙을 코드로 적용 해보면 다음과 같다.

 

입력값이 '(' 라면 스택에 저장한다.

입력값이 ')' 라면 경우의 수가 나뉜다.

 

입력값 ')' 의 바로 이전 인덱스 '(' 일 경우  ->  () 형태이므로 이는 레이져가 된다.

입력값 ')' 의 바로 이전 인덱스 ')' 일 경우  ->  )) 형태이므로 이는 레이져가 아닌 쇠막대기의 끝을 의미한다.

 

입력값이 이전 인덱스와 비교했을때 레이져라면 스택에 저장되어있는 '(' 의 개수만큼 총 count에 더한다.

입력값이 이전 인덱스와 비교했을때 쇠막대기의 끝이라면 +1 추가 후 스택의 최상단에 저장된 '(' 을 제거한다. (제거 하지않으면 계속해서 쇠막대기가 존재하는 것으로 계산 되므로)

 

이를 코드로 구현 하면 다음과 같다.

word = list(input())

stack=[]
stick=0

for i in range(len(word)):
  if word[i] == '(':
    stack.append(word[i])
  else: ## ')' 여기선 다시 경우의 수가 나뉜다. 레이져 또는 쇠막대기의 끝
    if word[i-1] == '(':
      stack.pop()
      stick += len(stack)
    else:
      stack.pop()
      stick += 1

print(stick)

 

구현한 코드를 보면 아주 쉬운 문제같지만 규칙을 찾는대만 1시간이 걸렸다.

규칙을 찾으니 스택 또는 큐 자료구조를 이용해야 한다는 힌트를 얻었다.

입력값으로 주어진 괄호와 저장된 최상단의 괄호를 비교해야 한다. 

막대기의 끝을 만나면 더이상 저장된 곳에 계속해서 존재해서는 안된다.

막대기의 제거는 저장된 곳의 최상단부터 제거 해야 한다.

 

규칙을 찾고 구현 할 자료구조가 떠올랐다면 문제의 반은 푼것이라고 생각한다!