[LeetCode/Easy] 20. Valid Parentheses

20. Valid Parentheses

easy 문제는 아직까지 모르는 개념은 거의 없고, 이 문제를 어떤 자료 구조로 풀어야 효과적일지가 포인트인 것 같다. 따라서 내가 아는 알고리즘 중에 풀 수 없을까 고민해보자!!!

내 풀이 vs. 답안 풀이

---

	내 풀이	답안 풀이
주어진 test case 외의 case {()}[] 에 대한 이해 (= 문제 이해)	{()}[] 와 같은 예시는 invalid하다 생각함. 왜냐하면 바로 닫혀야 한다고 문제를 잘못 이해했기 때문. 주어진 예시 외에도 valid한지 invalid한지 판단할 수 있어야 하는데.. -> 근거에 대해서도 설명할 수 있어야 함. 생각만 하지 말고 말로 설명해보기! 설명할 수 없으면 아닌 것.	{()}[]와 같은 예시는 valid함. 왜냐하면 꼭 연속해서 바로 닫혀야 한다는 말은 없었으니깐.
주어진 test case 외의 case ({)} 에 대한 이해 (= 문제 이해)	({)} 와 같은 예시는 valid하다 생각함 왜냐하면 문제를 제대로 이해하지 못했기 때문. -> 조건 읽고 이해했다고 넘기지 말고 조건에 따른 예시를 생각해보고 설명해보자!	invalid 왜냐하면 2번 조건에 따르면 열린 {는 }로 먼저 닫혀야 하고 그 다음에 )로 닫히는게 correct order이기 때문. 따라서, 괄호 종류마다 counter를 두는 방법은 통하지 않음.
hash map 구현	key : 모든 괄호, value : 해당 괄호에 대한 count 괄호 종류마다 counter를 두는 방법을 사용했는데 위의 케이스에 대한 이해가 잘 됐다면 이 방법을 사용하지 않았을 것.	key : 열린 괄호, value : 닫힌 괄호

내 답안

class Solution:
    def isValid(self, s: str) -> bool:
        hash_map = {'(':0, ')':0, '{':0, '}':0, '[':0, ']':0, '()':0, '{}':0, '[]':0}
        
        for i in range(len(s)):
            hash_map[s[i]] += 1
        if (hash_map['('] != hash_map[')']) | (hash_map['{'] != hash_map['}']) | (hash_map['['] != hash_map[']']):
            return False
        
        if len(s) > 1:
            for i in range(0, len(s), 2):
                if s[i:i+2] in ['()', '{}', '[]']:
                    hash_map[s[i:i+2]] += 1
                if i+2 >= len(s): 
                    break
            if (hash_map['('] != hash_map['()']) | (hash_map['{'] != hash_map['{}']) | (hash_map['['] != hash_map['[]']):
                return False
        else:
            return False
        return True

 

01

문제 풀면서 작성한 메모

답안 예시

Stacks

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        # The stack to keep track of opening brackets.
        stack = []

        # Hash map for keeping track of mappings. This keeps the code very clean.
        # Also makes adding more types of parenthesis easier
        mapping = {")": "(", "}": "{", "]": "["}

        # For every bracket in the expression.
        for char in s:

            # If the character is an closing bracket
            if char in mapping:

                # Pop the topmost element from the stack, if it is non empty
                # Otherwise assign a dummy value of '#' to the top_element variable
                top_element = stack.pop() if stack else '#'

                # The mapping for the opening bracket in our hash and the top
                # element of the stack don't match, return False
                if mapping[char] != top_element:
                    return False
            else:
                # We have an opening bracket, simply push it onto the stack.
                stack.append(char)

        # In the end, if the stack is empty, then we have a valid expression.
        # The stack won't be empty for cases like ((()
        return not stack

• Time complexity : $O(n)$
  • for문 1개이기 때문
• Space complexity : $O(n)$
  • 최악의 경우 n개를 모두 스택에 담을 수 있기 때문

개념 정리

---

스택(Stack)

• 프링글스 -> LIFO (Last in First Out)
• push, pop
• top이라고 하는 한쪽 끝에서 모든 삽입과 삭제가 일어나는 순서리스트

해시맵(Hash Map), 해시 테이블(Hash Table) (>>출처)

• Key-value pairs를 저장하는 data structure가 필요하면 딕셔너리 떠올리기!
  (Python의 해시맵으로 구성된 자료구조는 딕셔너리이기 때문)
• 특징
  • 순차적으로 데이터를 저장하지 않습니다.
  • Key를 통해서 Value값을 얻습니다.
  • Value값은 중복가능 하지만 Key는 중복될 수 없습니다.
  • 수정 가능합니다.(mutable)