정재영

1일 1문제 푸는 중

코딩테스트 고득점 Kit - 스택/큐 문제

✔️ 문제 설명

괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다. 예를 들어

”()()” 또는 “(())()” 는 올바른 괄호입니다.
“)()(“ 또는 “(()(“ 는 올바르지 않은 괄호입니다.
‘(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

  • 문자열 s의 길이 : 100,000 이하의 자연수
  • 문자열 s는 ‘(‘ 또는 ‘)’ 로만 이루어져 있습니다.
  • 👉 문제 보러가기

입출력 예

s answer
”()()” true
”(())()” true
”)()(“ false
”(()(“ false

입출력 예 설명

입출력 예 #1,2,3,4 문제의 예시와 같습니다.


✔️ 문제 풀이

(1) Pseudo-Code

  1. 괄호(입력값)을 for문으로 각각 하나씩 가져온다.
  2. 열린 괄호는 리스트에 넣는다. (닫힌 괄호가 들어온다면 하나씩 제거)
  3. 닫힌 괄호가 들어오면 리스트에 요소를 하나씩 제거한다. (이전에 열린 괄호가 들어와있는 경우)
  4. 닫힌 기호가 먼저 들어오는 경우는 바로 False를 반환하도록 설정한다.
  5. 최종으로 열린기호와 닫힌기호의 개수가 같으면 True가 반환되도록 설정한다.

(2) 코드 작성

def solution(s):
    """
    괄호가 열렸으면 무조건 닫혀야함
    ((())) 이런식으로 같은 괄호가 여러 번 반복될 수 있음
    열린 기호는 어느 경우에서도 올 수 있음 -> 끝에만 위치하지 않으면 됨
    닫힌 기호는 열린기호 뒤에만 올 수 있음 또는 닫힌 기호 뒤 -> 끝에 위치해야 함
    괄호 기호는 짝이 맞아야 함
    """
    s_list = []
    for b in s:
        if b == '(':
            s_list.append(b)
        # (, ) 가 만났을 때 ( 기호를 하나 를 뺀다. => 짝이 맞아야하기 때문
        elif b == ')' and len(s_list) >= 1:
            s_list.pop()
        else:
            return False
        
    return len(s_list) == 0

(3) 코드 결과

  • 성능요약 : 메모리 10.4 MB, 시간 9.85 ms
  • 채점결과 : 정확성 69.5, 효율성 30.5, 합계 100.0/100.0

(4) 코드 리뷰 및 회고

  • 처음에 문제를 풀 때, 짝이 맞아야한다는 생각을 고려하지 못해 pop 함수를 사용하지 않았다.
    • 개수를 맞추기 위해 append로 넣어준 것을 pop으로 제거하면 두 기호의 개수 동일 시 남아있는 요소는 없다는 점을 이용
  • 이번 문제를 통해 스택에 대해 이해할 수 있었던 것 같다.
  • 기억할 것 : 특정 요소들의 개수가 같아야 한다는 조건을 만족시킬 때, 스택 이용하기


댓글남기기