프로그래머스-올바른 괄호(파이썬, python)

SA Jung·2022년 9월 28일
0

Programmers 문제 풀이

목록 보기
1/14

https://school.programmers.co.kr/learn/courses/30/lessons/12909

[git]
https://github.com/JungSangA/Algorithm_Study/blob/main/%EC%8A%A4%ED%83%9D%26%ED%81%90/%EC%98%AC%EB%B0%94%EB%A5%B8%20%EA%B4%84%ED%98%B8.ipynb

1. count 변수 선언 후 갯수 비교

def solution(s):
    answer = True
    cnt = 0
    for i in s:
        if i =="(":
            cnt +=1
        elif i == ")":
            cnt -=1

        if cnt < 0:
            return False
    if cnt != 0:
        answer = False
    return answer

알고리즘 아이디어

  • 여는 괄호 "("가 열리면 닫히는 괄호 ")"가 있어야 하고, 마지막에 "("와 ")"의 갯수를 비교했을 때 같아야 한다.
  • cnt를 초깃값 0으로 설정하고, 문자열 s의 문자를 하나하나 비교하여 "("가 나오면 cnt를 1증가 시키고, ")"가 나오면 1 감소시키며 문자열의 마지막까지 진행한다.
  • 문자를 비교하는 도중에 cnt가 0보다 작아지는 경우 여는 괄호 "("가 없이 ")"가 나왔으므로 올바른 괄호식이 성립되지 않다고 판단하면 그 즉시 비교를 종료하고 False를 return하고 종료한다.
  • 모든 문자를 비교를 완료하고 최종 cnt가 0이라면 "("와 ")"의 갯수가 같다고 판단하고 True를 return하고, 최종 cnt가 0이 아니라면 올바르지 않는 괄호식이라고 판단하고 False를 return한다.

2. 스택을 통한 갯수 비교

(스택/큐)

def solution(s):
    stack = []
    for i in s:
        if i == "(":
            stack.append("(")
        elif len(stack) !=0 and i == ")":
            stack.pop()
        else:
            return False
    return True if len(stack)==0 else False
  • stack을 만들고, "("가 나오면 stack에 추가하고, ")"가 나오면 stack에서 "("를 1개 제거해준다.
  • 단, ")"이 나왔을 때 stack의 길이가 0인지 아닌지에 따라 에러메시지가 안뜨게 if문에 and 조건을 추가하고, ")"이 나왔지만 stack의 길이가 0 일때 올바른 괄호식이 아니라고 판단하고 for문을 종료하고 False를 return한다.
  • 모든 for문을 완료후에 stack의 길이가 0이라면 올바른 괄호식이라고 판단하고 True를 return, 아니라면 False를 return한다.
profile
Tomorrow will be better than yesterday :)

0개의 댓글