Algorithm Study - 001

Problem

---

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

 

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

먼저 적힌 괄호는 나중에 닫히는 이른바 FILO 방식의 알고리즘을 요구하는 문제.

Stack이 제일 먼저 떠오른다면 반은 먹고 들어갔다고 할 수 있다.

 

Solution

---

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        Stack<Character> stack = new Stack<>();
        
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        
        for(Character c : s.toCharArray()) {
            if(c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else if(stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }
                
        return stack.isEmpty();
    }
}

Map과 Stack을 이용한 소스.

더욱 최적화가 가능해 보이지만 이 이상의 퍼포먼스 차이는 체감이 어려울 것으로 판단.

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

제약 조건은 위와 같으므로 s.length가 0일 경우 Exception code는 생략.

 

Learn Point

---

1. Map의 of 사용법, 위의 소스에서는 없지만 아래처럼 쓸 수 있다. 가독성은 잘 모르겠지만 뭔가 간결해보인다.

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = Map.of(')', '(', ']', '[', '}', '{');
        Stack<Character> stack = new Stack<>();
        
        for(Character c : s.toCharArray()) {
            if(c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else if(stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }
                
        return stack.isEmpty();
    }
}

2. Stack의 FILO 특징과 push, pop, peek 와 같은 함수 (Map의 get도 역시)들에 대한 리마인딩