오늘의 문제 역시 쉽지 않았다... 그럼 바로 고!

10799: 쇠막대기

1. 내 풀이: 성공

바로 코드부터 공유하겠다.

laser = list(input())
answer = 0
stack = []

for i in range(len(laser)):
    if laser[i] == '(':
        stack.append('(')

    else:
        if laser[i-1] == '(':
            stack.pop()
            answer += len(stack)
        else:
            stack.pop()
            answer += 1
print(answer)

처음에는 문제 이해하면서 규칙을 찾으려고 했는데,,, 도저히 모르겠어서 아래 알고리즘 분류를 보았다. 스택으로 분류 되어 있길래 스택 ?! 이라고 생각했는데, 또 나름 잘 생각하니까 스택으로 풀 수 있을 것 같았다.

코드를 설명하면,

laser = list(input())
answer = 0
stack = []

먼저 laser가 포함된 문자열을 받아 바로 list로 만들어준다. 이렇게 문자를 하나하나 판단해야 할 때는 바로 리스트로 만들어주어 요소로 구분하는 게 더 빠르고 간편한 것 같다.
그리고 answer 변수를 정의해 쪼개지는 쇠막대기의 개수를 저장할 수 있도록 하고, 문자 하나하나의 값을 저장하고 판단할 stack 리스트를 만들어준다.

for i in range(len(laser)):
    if laser[i] == '(':
        stack.append('(')

    else:
        if laser[i-1] == '(':
            stack.pop()
            answer += len(stack)
        else:
            stack.pop()
            answer += 1
print(answer)

이제 stack과 laser를 통해 판단해보자.
먼저 laser 길이만큼 for문을 돌려준다. '('는 특별한 의미를 가지지 않으므로 바로 stack에 append 해준다. 하지만 ')'의 경우, 두 가지로 분류할 수 있다.

1. 만약 이 바로 전에 '('가 나왔다면?
   : 이는 레이저를 의미하므로 해당 여는 괄호 ('(')를 stack에서 빼주고, 지금까지 stack에 쌓인 길이만큼 answer에 더 해준다.

2. 만약 이 바로 전에 ')' 라면?
   : 쇠막대기의 끝을 의미하므로, stack에서 해당 값을 빼준 후 answer에 1을 더해준다.

이렇게 하면 끝!

계속해서 stack, queue를 이용하는 문제가 등장하는데,

'쌓으면서 판단하자' 가 필요하면, stack을 쓰자!

고 할 수 있지 않을까...? 안그래도 오늘 leetcode에서도 stack 이용하는 문제가 있었는데 고것도 잘 분석해봐야겠다...!

2. 참고

나는 sys 모듈이 영원히 나의 동반자일 줄 알았다... 그런데 sys.stdin.readline()을 쓰니까 출력 초과가 났다...! 앞으로는

sys.stdin.readline() -> input() 순

으로 입력값을 받아야겠다.

오늘도 신기한 알고리즘의 세계 끝!