스택 - 몸풀기 문제

문제 08 괄호 짝 맞추기

열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열이 주어졌을 때,
소괄호가 정상으로 열고 닫혔다면 True, 그렇지 않다면 False 구현
" 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄 "
가장 가까운 (최근) 이라는 키워드를 보고 스택을 떠올려야 !

시간복잡도 : O(N)

def solution(s):
	stack=[]
    for c in s:
    	if c="(":
        	stack.append(c)
        elif c=")":
        	if not stack:
            	return False
            else:
            	stack.pop()
    if stack:
    	return False
   else:
   		return True

cf ) if stack : 비어있지 않다는 것을, if not stack : 비어있다는 것을 의미
s를 순회하면서 괄호 쌍을 확인하니 O(N), append() 와 pop() 메서드 시간 복잡도는 O(1)

문제 09 10진수를 2진수로 변환하기

10진수를 입력받아 2진수로 변환해 반환
시간복잡도 : O(logN)

def solution(decimal):
	stack=[]
    while decimal>0:
    	remainder=decimal%2
        stack.append(str(remainder))
        decimal//=2
    binary=""
    while stack:
    	binary+=stack.pop()
return binary

# binary="".join(map(str,stack[::-1]))
# binary="".join(reversed(stack))
현재 stack 리스트 안에 요소들이 문자열이기 때문에 str map 안 해도 됨

cf ) 10진수를 2진수로 바꾸는 법
1. 숫자 N을 2로 나누었을 때 나머지를 따로 저장, N은 2로 나누기
2. 몫이 0이 될 때까지 계속 나누기
3. 나머지 저장해놓은 것을 역으로 꺼내서 붙이고 출력하기

N이 1이 될 때까지 2로 계속 나누므로 연산 횟수는 O(logN)
+= 연산자는 수행할 때마다 객체를 새로 생성하기 때문에 O((logN)^2)

cf ) 문자열에 계속해서 문자를 더할 때는 + 보다 join() 메서드가 더 효율적
join()으로 하면 O(logN)