3986번 - 좋은 단어

💡 문제의 핵심을 빠르게 이해하는 것도 중요하다!

import sys

input = sys.stdin.readline

N = int(input())
cnt = 0

for _ in range(N):
    
    word = list(input().rstrip())
    stack = []
    
    # A든 B든 홀수개가 들어오면 Pass
    if word.count('A') % 2 != 0 or word.count('B') % 2 != 0:
        continue
    
    for val in word:
        
        if stack and stack[-1] == val:
            stack.pop()
        else:
            stack.append(val)
            
    if not stack:
        cnt += 1
    
print(cnt)

• 문제 자체는 그렇게 어렵지 않은 문제였다.. 다만.. 문제를 이해하는데 시간이 조금 걸렸다..ㅋㅋㅋㅋㅋ
• 우선 Stack을 사용하여 stack이 비어있으면 넣어주고, stack의 가장 윗부분 (즉, 직전에 넣어준 알파벳)과 비교하여, 동일하면 넣지않고 stack의 가장 윗부분을 pop()하면서 짝이 맞는 것들을 제거해주었다.
• 위 과정을 반복하면서 stack이 전부 비어있게 되면, 짝이 모두 맞는 것이고, 남아있으면 짝이 안맞는 것임으로, 비어있을 경우엠만 cnt에 +1을 해주어서 "좋은 단어"의 갯수를 구하였다.
• 추가적으로 처음 list를 전체 탐색하기 전에, count()를 사용해서 A나 B의 갯수가 홀수이면 탐색을 하지 않고, continue 시켜주는 작업을 하여 진행하였다.
  => 생각해보니, Count()가 2번 돌아가게 되면서 전체 순회를 총 3번이 일어나야 하였다..
  => 그래서 저 부분을 아예 뺴는 것이 더 시간복잡도 측면에서 빠르다고 생각했다.

<수정된 코드>

import sys

input = sys.stdin.readline

N = int(input())
cnt = 0

for _ in range(N):
    
    word = list(input().rstrip())
    stack = []
    
    for val in word:
        
        if stack and stack[-1] == val:
            stack.pop()
        else:
            stack.append(val)
            
    if not stack:
        cnt += 1
    
print(cnt)

• 위와 같이 수정한 후 결과를 넣어 보았더니 실제로 시간에 차이가 발생하였다.