Lv2. 짝지어 제거하기

코딩테스트 연습 > 짝지어 제거하기

1. 풀이 설명

1. stack 변수를 정의하고, s 를 하나씩 for문 돌면서

2. stack이 비어있거나 stack의 마지막 아이템과 현재 값이 다르면 stack 에 현재 값을 추가하고

3. stack의 마지막 아이템과 현재 값이 같다면, stack의 마지막 아이템을 pop() 한다.

4. stack이 비어있으면 1, 비어있지 않다면 0을 반환한다.

2. 나의 풀이

python

def solution(s):
    stack = []    
    for c in s:
        if len(stack) == 0:
            stack.append(c)
        else:
            if c == stack[-1]:
                stack.pop()
            else:
                stack.append(c)
    if stack:
        return 0
    else:
        return 1

3. 배운점

1. Stack을 활용해야 하는 문제라는 것을 인지하기까지 시간이 걸려서 아쉬웠던 문제. 입력 문자열의 길이가 최대 1,000,000 임에도 앞에서부터 차례로 현재 index와 다음 index의 값이 같으면 pop() 하는 방법을 시도했었다. (current) 결과는 일부 테스트케이스 시간초과 Fail 이었다.

def solution(s): # 시간초과
    current = s
    count = 0
    while True:
        if current == '':
            return 1
        
        result = ''
        count = 0
        i = 0
        while i < len(current):
            if i < len(current) - 1 and current[i] == current[i+1]:
                i += 2
                count += 1
            else:
                result += current[i]
                i += 1
        current = result
        
        if count == 0:
            return 0
    return 0

비슷한 문제 (같은 문자일 때 삭제 등)를 다시 만난다면, 또는 입력 값이 커서 위와 같은 탐색방법으로 문제가 풀리지 않는다면
stack, queue 등 자료구조를 하나씩 떠올리며 사용할 수 있을지 점검해 봐야겠다.

2. 리스트가 비어있는지 검사: if not list:

if stack: 		# 으로 stack 이 비어있지 않음을 검사한 거 처럼

if not stack: 	# stack 이 비어있음을 검사한다.