[백준][스택] 99클럽 코테 스터디 7일차 TIL + 쇠막대기

오늘의 학습 키워드

스택, 문자열

 

 

오늘의 회고

🌱 오늘의 문제

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

오직 소괄호만을 이용하여 쇠 막대기와 레이저의 위치를 나타낸 입력이 주어진다. 입력의 길이는 최대 10만이다.

 

 

🌱 나의 시도

이 문제에서 중요한 포인트는 레이저가 한 번 등장할 때마다 현재 겹쳐져 있는 쇠 막대기의 개수만큼이 잘리게 된다는 것이다.

조금 더 구체적으로 로직을 정리해 보면 아래와 같다.

 

1. 현재 들어온 입력에 대해 쇠 막대기인지 레이저인지 판단한다.

2. 만약 쇠 막대기라면 현재 쇠 막대기 개수를 1 증가시킨다.

3. 만약 레이저라면 현재 저장되어 있는 쇠 막대기 개수만큼 정답 값에 더해준다.

4. 위 과정을 반복한 후 최종적으로 몇 개의 쇠 막대기가 잘렸는지 판단해준다.

 

 

1. 스택을 이용한 풀이

참고로 파이썬은 별도의 라이브러리를 사용하지 않고 리스트를 이용하여 스택을 구현할 수 있다.

리스트의 append() 메소드를 이용하면 가장 뒤에 값이 추가되고, pop() 메소드를 이용하면 마지막 값을 추출하기 때문이다.

 

(1) 여는 괄호

여는 괄호는 새로운 쇠 막대기(혹은 레이저)가 추가되는 것을 의미한다.

나는 닫는 괄호에서 쇠 막대기와 레이저를 구분해주었기 때문에, 여는 괄호가 나올 경우 우선은 구분 없이 인덱스 값을 스택에 추가해준다.

그리고 이렇게 새로운 쇠 막대기가 추가되는 경우 answer에 1을 추가해준다. 레이저로 자르지 않더라도 한 개가 존재하기 때문이다.

(2) 닫는 괄호

닫는 괄호는 쇠 막대기(혹은 레이저)가 끝나는 부분을 의미한다.

pop()을 하면 마지막 값이 반환된다. 마지막 값이 i-1, 즉 바로 이전 인덱스라는 것은 여는 괄호가 현재 닫는 괄호와 인접해 있었다는 것, 즉 레이저라는 것을 의미한다. 따라서 레이저인 경우에는 현재 레이저 개수만큼 추가해준다.

여기서 주의할 점은 레이저의 여는 괄호에서도 새로운 쇠 막대기로 간주하고 1을 증가시켜 주었으므로, 이 값을 빼주어야 한다.

 

코드를 살펴보면 아래와 같다.

s = input()
stack = [] # 현재 겹쳐진 쇠 막대기의 개수
answer = 0 # 최종적으로 잘려진 쇠 막대기의 개수

for i, c in enumerate(s):
    if c == '(': 
        stack.append(i)
        answer += 1
    else:
        prev = stack.pop()
        if prev == i-1: # 쇠 막대기일 때 (이전 인덱스가 여는 괄호일 때)
            answer = answer + len(stack) - 1 # 레이저 개수 1 제외
    
print(answer)

 

파이썬에서 리스트의 append(x), pop(), len(arr)은 O(1)을 따르므로 리스트를 활용하여도 시간 복잡도가 커지지 않는다.

현재 코드는 문자열을 순회하면서 O(1) 연산들을 반복하므로, 순회에서 고려되는 O(n)이 가장 큰 시간 복잡도가 된다.

따라서 이 코드의 시간 복잡도는 O(n)이다.

 

 

 

2. 스택의 원리만을 이용한 풀이

위와 같이 코드를 짜고 보니 쇠 막대기의 개수만을 활용하므로 쇠 막대기의 위치 값(인덱스)를 스택에 넣을 필요가 없다는 생각이 들었다.

문자열이 최대 10만이라 크게 많은 메모리를 사용하지는 않는다.

다만, 길이값을 저장하는 정수형 변수 하나만 활용한다면 문자열이 아무리 길어지더라도 메모리 효율을 지킬 수 있을 것이다.

 

s = input()
current_pipes = 0 # 현재 겹쳐진 쇠 막대기 개수
answer = 0 # 최종적으로 잘려진 쇠 막대기 개수

for i, c in enumerate(s):
    if c == '(': 
        current_pipes += 1
        answer += 1
    else:
        current_pipes -= 1
        if i != 0 and s[i-1] == '(': # 레이저인 경우
            answer = answer + current_pipes - 1 # 레이저 개수 1 제외

print(answer)

 

 

위와 같이 코드를  수정해보았다.

로직은 그대로이며, 리스트의 삽입/삭제/길이 조회 메소드가 O(1)이기 때문에 시간 복잡도 측면에서도 크게 달라지지 않았다.

다만 이 코드는 가독성이 스택을 사용한 것에 비해서는 좋지 않은 것 같다.

 

 

🌱 새롭게 알게 된 점

Stack을 활용한 문제 유형을 이해하게 되었다.

자료구조 공부를 하며 개념만 이해했는데 오늘 문제를 풀어보면서 코드로 활용할 수 있게 되었다.

 

 

오늘의 후기

오늘 코드를 보며 스스로 어떻게 개선할 수 있을지 고민해 보았고, 작게나마 기여할 수 있는 부분이 있어 재밌었다.

또한 개념에서 코드로, 또 오늘은 그것을 응용한 문제로 나아갔다. 점차 지식이 확장되고 있다는 생각이 들어 뿌듯하다.

코테 공부를 하기 싫다며 외면할 때엔 할 게 많다는 생각에 더 멀리했는데, 오히려 시작하고 나니 여기까지 금세 온 것 같다.

역시 공부는 해야 재밌고, 할수록 재밌는 일인 것 같다.

 

학습 부채 만들지 말고 할 일을 꾸준히 해 나가자! 화이팅!