문제: 46 쇠막대기
- 쇠 막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
-
레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
- (a) 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘()’으로 표현합니다. 또한 모든 ‘()’는 반드시 레이저를 표현합니다.
-
(b) 쇠막대기의 왼쪽 끝은 여는 괄호 ‘(‘로, 오른쪽 끝은 닫힌 괄호 ‘)’로 표현됩니다.
- 나누어진 쇠막대기의 조각을 구하라.
생각한 방법
- 스택의 대표 문제다.
- 괄호를 스택에 넣고.
- 닫힌 괄호를 만나면 스택에서 괄호를 하나 뺀다.
- ’(‘를 만나면 스택에 넣는다
- ’)’를 만나면 스택에서 pop을 한 뒤, 해당 스택에 남아있는 개수를 센다.
- 이 때 ‘(‘를 넣은 뒤 ‘)’가 아닌, 즉 ‘)’ 다음 또 ‘)’가 나왔을 경우, 스택에 남아있는 개수 +1을 더해줘서 센다.
틀린 이유
- 위 방법은 틀렸다. 레이저를 만날 때에만 계산을 해줘야 하는데, 스택의 닫힌 걸 기준으로 문제를 풀었기 때문이다.
- last라는 변수를 사용해서 index를 구분해줄 수도 있다.
- ”(“ 모양일 경우 하나씩 넣어주고, 그 길이를 결과값에 더해주는 방법이다.
def solution(arrangement):
answer = 0
stack = []
for i, x in enumerate(arrangement):
if x == '(':
stack.append('(')
else:
stack.pop(-1)
if arrangement[i-1] == '(':
answer += len(stack)
else:
answer += 1
return answer
print(solution("()(((()())(())()))(())"))
- 정리하자면
- ’(‘이면 스택에 넣어주고
- ’)’일 때, 이전이 ‘(‘, 즉 레이저였다면 스택의 길이를 더해주고
- 레이저가 아니었다면, 1을 더해준다.
- 레이저가 한개만 덜렁 나왔을 때는 스택이 비어있으므로 상관없고
- 레이저를 자른 뒤에 나타나는 )이므로, 끝나는 부분에는 +1을 해주면 된다.
참고자료 [프로그래머스]https://programmers.co.kr/learn/challenges