99클럽 코테 스터디 8일차 TIL [올바른 괄호]

- 오늘의 학습 키워드

스택(Stack)

- 공부한 내용 본인의 언어로 정리하기

- 스택이란?

컴퓨터 과학에서 자주 사용되는 자료구조 중 하나로, 데이터를 저장하고 관리하는 데 사용된다.
"쌓아 올리는" 구조를 가지고 있으며, Push와 Pop 연산을 통해 작동한다.
스택의 중요한 특징은 후입선출(LIFO) 방식으로, 가장 나중에 추가된 요소가 가장 먼저 제거된다.

- Push

새로운 요소를 스택의 맨 위에 추가

- Pop

스택의 맨 위에 있는 요소를 제거하고 반환

- 활용예시

1. 갈호 짝 맞추기
2. 역순 문자열 만들기 : 문자열을 뒤집을 때 스택을 사용하면 간단히 해결할 수 있다.
3. 실행취소(Undo)기능 : 프로그램에서 실행 취소 기능을 구현할 때, 
					이전 상태를 스택에 저장하여 가장 최근 상태를 쉽게 복원할 수 있다.

- 주요 연산

1. push(item) : 새로운 요초를 스택의 맨 위에 추가

def push(item) :
	items.append(item)

2. pop() : 스택의 맨 위에 있는 요소를 제거하고 반환, 비어있으면 'None' 반환

def pop() :
	if not is_empty():
    	return items.pop()
    else :
    	return None

3. is_empty() : 스택이 비어있는지 확인, 비어있으면 True, 아니면 False 반환

def is_empty():
	return len(items) == 0:

4. peek() : 스택의 맨 위에 있는 요소를 반환하지만 제거하지 않음, 비어있으면 'None' 반환

def peek():
	if not is_empty():
    	return items[-1]
    else :
    	retrun None

< 오늘의 회고 >

- 어떤 문제가 있었고, 나는 어떤 시도를 했는지

올바른 괄호 문자열인지 확인하는 문제에서 나는
주어진 문자열에서 "()"의 개수가 짝수이면 True를 반환하는 방법으로 시도했다.

def solution(s) :
	if s.count('()') % 2 == 0:
    	return True
    else :
    	return False

그 결과, 기본 테스트케이스는 통과가 되었지만 정확성 테스트에서 실패하였다.

- 어떻게 해결했는지

Chat GPT를 통해 스택구조를 활용하면 된다는 것을 알았다.

def solution(s):
	# stack 리스트를 사용하여 괄호를 저장
	stack = []
    
    # s를 순회하며
    for char in s:
    	# '('를 만나면 스택에 추가
    	if char == '(':
        	stack.append(char)
        # ')'를 만나면
        elif char == ')':
        	# 스택이 비어있는지 확인
        	if not stack:
            	# 비어있으면 False 반환
            	return False
            # 그렇지 않으면 스택에서 하나를 제거
            stack.pop()
    # 순회를 마친 후 스택이 비어있는지 확인하여 비어있으면 모든 괄호가 짝지어져 있는 것으로,
    # True를 반환하고 그렇지 않으면 False를 반환한다.
    retrun len(stack) == 0

이 방법은 시간복잡도가 O(n)으로 효율적이다.