[백준] 19799_ 자료구조

✔︎문제: https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

✏️ 나의 풀이

- ()인 레이저인 경우와, 막대기인 경우 두가지로 나뉘는데 레이저인 경우 지금까지 쌓여있는 막대기를 수직으로 자른다.

ex) (()) : 막대기 한개 레이저 한개로 두동강 남 -> 답: 2

- 막대기인 경우 stick 리스트에 쌓아주고, 레이저인 경우 stick에 쌓인 막대기개수 더해준다. 그리고 막대기가 끝나는 지점이라면 리스트에서 빼주고 +1 한다.

- 현재와 앞에 값을 비교하며 레이저인지, 막대기인지 확인하는 코드를 구현했다.

st = input()
stick = []
result = 0
bomb = False

for i in range(len(st)-1):
    if st[i] == "(":
        if st[i+1] == ")":
            bomb = True
        if st[i+1] == "(":
            stick.append("(")
            bomb = False
    else:
        if not bomb:
            stick.pop()
            result += 1
        else:
            result += len(stick)
            bomb = False

if len(stick) > 0:
    print(result + 1)
else:
    print(result)

 

📌 다른 풀이

- 이게 더 직관적이고 깔끔하다.

- "("인 경우는 모두 리스트에 넣어주고 ")"일 때 이게 레이저인지, 막대기가 끝나는 지점인지 확인해주는 코드이다.

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

for i in range(len(arr)):
    if arr[i] == '(':
        stack.append("(")
    
    else:
        if arr[i-1] == "(":
            stack.pop()
            answer += len(stack)
        else:
            stack.pop()
            answer += 1
print(answer)

• 스택을 이용
• “(” 라면 스택에 넣는다
• “)” 라면
  • 이전 문자가 “(” 라면 레이저이다. stack에서 마지막 문자 빼주고 스택에 쌓인 개수(막대기 개수)만큼 더해준다
  • 이전 문자가 “)”라면 stack에서 마지막 문자 빼주고 1 더해준다. (막대기 끝자락)

 

구현 문제는 코드가 직관적이고 깔끔해야 코딩테스트때 실수하지 않는다.

같은 알고리즘이라도 헷갈리지 않게 구현하자.