수 많은 우문은 현답을 만든다

(Medium) Valid Parentheses 본문

코딩테스트/Level 3 (deprecated)

(Medium) Valid Parentheses

aiden.jo 2023. 6. 10. 02:47

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 

An input string is valid if: 

Open brackets must be closed by the same type of brackets. 

Open brackets must be closed in the correct order. 

Every close bracket has a corresponding open bracket of the same type. 

 

Example 1: 

Input: s = "()" 

Output: true 

 

Example 2: 

Input: s = "()[]{}" 

Output: true 

 

Example 3: 

Input: s = "(]" 

Output: false

 

* 단순히 괄호가 열리고 닫히기만 하면 된다

Example 4: 

Input: s = "([)]" 

Output: false

 

문제 :

https://leetcode.com/problems/valid-parentheses/


풀이

더보기

# 핵심은 괄호 쌍을 맵핑하는것

# 추가 핵심은 스택을 써야한다는 것
 
dic = {')':'(', '}':'{', ']':'['} 
stack = []
 
for char in s: 
    if char in dic:
        if len(stack) == 0: # case : "]" 
            return False
        else:
            if dic[char] == stack[-1]: # 스택의 마지막 값을 의미
                stack.pop()
            else:                    # case : "(])" 
                return False
    else:
        stack.append(char)
 
return len(stack) == 0

 

# 아래와같이 리팩토링 가능.

for char in s:
    if char in dic:
        if stack and dic[char] == stack[-1]:
            stack.pop()
        else:
            return False
    else:
        stack.append(char)
return not stack

 

만약 모든 Example 4 도 True여야 한다면 코드는 아래와같이 짜야한다.

        dic = {'(':')','{':'}','[':']'}
        idx = len(s) - 1
        stack = []
        temp = ''

        for el in s:
            stack.append(el)

        if len(stack) % 2 == 1:
            return False

        while stack:
            
            temp = stack.pop()
            print(stack)
            for i in range(len(stack)-1, -1, -1):                
                if stack[i] in dic.keys() and dic[stack[i]] is temp:
                    stack.pop(i)
                    break
                if stack[i] in dic.keys() and dic[stack[i]] is not temp:
                    return False                
        return True

'코딩테스트 > Level 3 (deprecated)' 카테고리의 다른 글

(Easy) Balanced Binary Tree  (0) 2023.06.18
Merge Two Sorted Lists  (0) 2023.06.15
Reverse Linked List  (0) 2023.06.14