[백준/파이썬]10799 쇠막대기

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

해설 참고

https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/dashboard

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의

 

위 강좌에도 있고, 백준에도 있는 정보올림피아드 문제다.

 

문제

 

 

처음 문제를 봤을 때, 어려워 보였다. 그런데 어렵게 생각한 것치곤 실버 2에 정답률 64%.. 나만 어렵게 생각하는 문제인가 싶었다.

 

총 2번 코드를 짜고 풀었다.

 

하나는 시간 초과로 오답이 떴다.

 

첫번째 풀이

 

스택을 쓰는 건 똑같았다. 우선 레이저의 시작과 끝 인덱스를 저장하는 리스트와 쇠막대기의 시작과 끝 인덱스를 저장하는 리스트를 각각 만들고, 쇠막대기 시작과 끝 인덱스 안에 포함되어 있는 레이저의 수를 카운트하고 그 합을 출력해 줬다.

 

알고리즘 강좌에 있는 예제 입출력도 모두 잘 나와줘서 백준에서도 정답을 맞을 줄 알았으나. 반복이 많다 보니 시간 초과가 나왔다.

 

오답

bar = input()

stack = []

r_idx = []
b_idx = []

for i in range(len(bar)) :
    if bar[i] == '(' :
        stack.append(i)
    else :
        left_idx = stack.pop()

        if i - left_idx == 1 :
            r_idx.append([left_idx, i]) # 레이져 시작, 끝 인덱스
        else :
            b_idx.append([left_idx, i]) # 쇠박대기 시작, 끝 인덱스

ans = 0
for b in b_idx :
    count = 0
    for r in r_idx :
        if b[0] < r[0] and b[1] > r[1] : # 하나의 쇠 막대기 안에 몇개의 레이져가 있는지 판단
            count += 1
    ans += count + 1 # 잘린 쇠막대기 수는 레이져 수 + 1

print(ans)

두 번째 풀이 (정답)

 

어떻게 풀까 고민하다 결국 강의 풀이를 봤다.

 

생각보다 너무 간단해서 놀랐다. 난 왜 저런 생각은 못했지 하는 자괴감이 든다.

 

정답 풀이는 레이저를 찾았을 때, 스택에 들어있는 '('의 수만큼 계속 더해주면 된다. 그리고 쇠막대기가 끝났을 때도 1만큼 더해주면 된다.

 

정답

bar = input()

stack = []

ans = 0
for i in range(len(bar)) :
    if bar[i] == '(' :
        stack.append(i)
    else :
        left_idx = stack.pop()

        if i - left_idx == 1 : # 레이져 일때
            ans += len(stack)
        else :
            ans += 1


print(ans)