[프로그래머스] (파이썬)올바른 괄호-Level2-스택(Stack)활용

안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '올바른 괄호'문제를 풀어보도록 하겠습니다.

1. 문제 

programmers.co.kr/learn/courses/30/lessons/12909?language=python3

코딩테스트 연습 - 올바른 괄호

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

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

---

2. 슈도코드

1) 방을 생성합니다. '('는 남자 ')'는 여자로 생각해봅시다.
2) 문자열 s에서 성별 하나하나씩 차례로 탐색해줍니다
3) s탐색을 하면서 남자가 나오면 생성한 방에 저장해줍니다.
4) 조건문을 사용해 남자가 방에 있을 때, s탐색과정중 여자가 나오면 방에있던 남자를 빼내 데이트를 하러 나갑니다.♡

판별
5-1) 짝이 맞지 않아 방에 혼자 남아 있는 남자가 있다면 False입니다.
ex) s가 '남여남남남'인 경우, 여자는 없는데 남자만 방에 있습니다.
5-2) 짝이 맞지 않아 방에 남자가 없는데도 여자가 있다면 False입니다.
ex) s가 '남여여여여'인 경우 방에 아무도 없는데 여자가 있습니다.

5-3) 짝이 모두 맞아 방이 비어있다면 True입니다.

---

3. 문제풀이

1) 괄호를 저장할 '공간'(스택이 될겁니다. 파이썬에서는 스택이 없으니 그냥 [](리스트)을 생성합니다.
왜 하필 스택을 생성하는 지 뒤에 기술하겠습니다.
2) 문자열 s를 탐색합니다. 짝을 맞추어 주는 탐색과정

• 문자열 s를 탐색하면서 '('가 탐색과정중에 있다면 생성한 스택에 추가합니다. (앞으로 이 스택엔 '('만 추가합니다)
• for문을 사용해 문자열 s를 탐색하면서 ')'가 탐색과정중에 있다면
  • 이 때, 생성한 스택에 '('가 할당된 상태라면
  • 할당된 '('를 내보냅니다.
  • 그렇지 않다면 False를 출력합니다. (스택에 '('가 없다면 이말은 즉 '문자열 s가 ')'로 시작된 상태라면' 과 동일)
    따라서 ')'로 시작된 문자열이라면 무조건 False입니다.
• 위 for문을 거친 후 stack에 남아있는 것이 있다면 False. -->즉, 짝을 맞추지 못한 것이 있다는 말
• 위의 조건을 모두 통과하면 True를 출력합니다.

---

 

4. 알아야할 스킬셋

이 문제는 비교적 쉬운 문제라서 알아야할 스킬 셋은 없지만

if stack:

 

이라는 문법을 기억해주셨으면 합니다. 스택에 무언가가 있다면 True, 아무것도 없다면 False를 출력하는 문법입니다.

---

5. 문제풀이를 하면서 든 생각

비전공자의 입장에서 이 문제를 처음 딱 봤을 때, 왜 하필 스택을 사용하지? 라는 생각을 하게 되었습니다. 그냥 리스트에 '('를 저장해서 ')'가 나오때마다 list.remove() 쓰면 되지 않을까? 라고 생각했습니다. 

하지만 list를 사용할 시에는 for문을 한번 더 사용해야한다는 단점이 있었습니다. 우선 문자열 s를 탐색하고, 리스트의 원소를 지우기 위한 for문을 한번 더 사용해야합니다. 전 포스팅에 말씀드렸듯이 시간복잡도를 줄이는 것이 중요한데 스택을 사용하면 시간복잡도가 O(n)이지만 리스트를 사용하면 O(n^2)가 되어요! 그래서 스택을 사용합니다.

사실 이 문제는 굉장히 쉬운 문제입니다. 이 문제에서는 소괄호만 사용했지만 중괄호, 대괄호까지 짝을 맞추어야한다면 더 복잡해지겠죠? 나중에 그에 대한 문제풀이도 할 생각입니다. 그때는 Stack1(소괄호), Stack2(중괄호), Stack3(대괄호) 이렇게 사용하는 것도 있지만 해시라는 자료구조를 사용할 생각입니다.

오늘은 프로그래머스의 '올바른 괄호'문제를 파이썬을 사용해 풀어보았습니다.

진또배기 올림