99클럽 코테 스터디 7일차 TIL [04/08]

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

⏳ 코테 스터디 진행도 🧱 : [▰▰▰▰▰▰▰▰▰▰▰▰▰░                                     ] 8/29일 (28%)

본 글에서 다룬 문제 : 백준 3986번_좋은 단어

문제 푸는 데 걸린 시간 : 11분

오늘의 문제 풀기 눌러놓고 블로그 글 적느라 시간이 오버해 버렸다.

리셋하고 그때부터 문제 풀었음

 

 

 

 

[오늘의 문제]

 

 

 

[문제 해석 및 분석]

보고서의 모든 글자가 A와 B로 바뀌었다

보고서에서 '좋은 단어'를 세어보려 하는데

이때 '좋은 단어'가 무엇일까? 문제의 설명은 다음과 같다.

단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 짓는다.

(A는 A끼리, B는 B끼리)

만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는

같은 글자와 짝 지을 수 있다면, 그 단어는 '좋은 단어'이다.

 

이게 무슨 말인가 싶어서 한 3번은 읽었다.

그리고 이해완료

직접 만든 그림을 보면 이해하기 무척 쉽다.

 

그러면 이 말은 즉, 문자열에서 짝지어진 문자쌍을 모두 제거했을 때

문자가 하나도 남지 않으면 '좋은 단어'라고 해석할 수 있겠다.

이러한 과정을 구현하려면 스택 구조로 풀면 좋을 것 같다는 생각이 들었다.

왜?

스택은 항상 바로 앞에 들어온 문자만 비교할 수 있으니까.

 

문자열 AABB를 스택으로 풀어보면 다음과 같다.

1. A
   1. 스택에 넣음
   2. [A]
2. A
   1. 스택의 top이 A
   2. 짝이 맞음
   3. pop
   4. []
3. B
   1. push
   2. [B]
4. B
   1. 스택의 top이 B
   2. pop
   3. []
5. 끝났는데 스택이 비었음
   1. 좋은 단어!

 

이러한 과정을 코드로 구현하면 다음과 같다.

1. 단어의 개수 N 입력
2. 단어 문자열 입력
3. 단어 스택으로 검사하는 함수
   1. 스택이 비어있지 않고 맨 위랑 문자가 같으면 pop
   2. 아니면 push
   3. 다 지워졌으면? '좋은 단어'
4. 전체 단어에 대해 함수 적용
   1. '좋은 단어'가 몇 개인지 카운트도 해야 함
5. 결과 출력

 

 

 

[코드]

# 스택을 이용해서 해결 시도
import sys
input = sys.stdin.readline

N = int(input())
count = 0

def good_word(word):
    stack = []
    for char in word.strip():
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

for _ in range(N):
    word = input()
    if good_word(word):
        count += 1

print(count)

 

 

 

[제출 결과]

 

 

 

[시간복잡도]

입력 부분에서부터 살펴보자

N을 입력받는 건 1줄 입력이니 O(1)

 

for _ in range(N): 이 부분은 단어 N개를 처리하니까 N번 반복함

 

내가 사용한 함수 부분을 보면

문자열의 길이가 L이라면 각 문자를 한 번씩 훑고 지나가니까 O(L) 임

stack.pop()이랑 stack.append()도 있잖아요? 그럼 이건 뭐에요라고 묻는다면

리스트의 끝에서만 처리하니까 둘 다 O(1) 임

 

함수 부분은 단어 하나에 대해서만 처리하는데 O(L)이니까

N번 반복하면? O(L1 + L2 + L3 + ... + LN) 이렇게 될 거임

 

그런데 문제 조건에서 단어의 개수 1 <= n <= 100이고

각 단어 길이의 합 <= 1,000,000이므로

최악의 경우 O(1,000,000)이 된다.

문제없다는 의미.

근데 저렇게 계산되는데 시간 복잡도를 O(N)이라고 해도 되는 건가 싶다.

이 코드의 시간복잡도 : O(L1 + L2 + L3 + ... + LN) 이렇게 해야 하는 건가..?

 

 

 

[다른 접근 방법]

저번에 다른 문제 풀 때에도 이렇게도 풀리겠는데? 하고 생각한 건데

덱(deque) 사용하는 방법이다.

이걸로 이 문제를 풀어보진 않았는데

다른 문제를 풀어본 결과 스택만 사용하는 것보다 코드가 짧아졌었다.

시간은 조금? 더 걸렸는데 자료구조 차이인 듯

그리고 deque는 양방향 삽입/삭제를 할 때 주로 사용하는 거라

이 문제처럼 한 방향만으로 해결할 때는 스택만 사용해도 충분하다 생각함

 

 

 

[회고]

내가 이 문제를 어떻게 해석했는지 과정을 정리하고

코드로 구현하기 위한 과정을 정리하니까 머리에 기억이 잘 남는 느낌이다.

사실 곡선이 교차...? 이게 무슨 소리지 하면서 노트에 그려보고 아하! 했음

고수분들이 문제 풀 때 노트에 생각한 구현 과정을 작성하는 건 다 이유가 있는 거였다.