문제

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.
3. Every close bracket has a corresponding open bracket of the same type.

Example

input

s = "()"

output

true

---

input

s = "()[]{}"

output

true

---

input

s = "(]"

output

false

제약조건

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

문제 분석

입력값으로는 괄호 문자(소/중/대 괄호)만 들어온다.
열린 괄호 문자 다음에는 같은 종류의 닫힌 괄호 문자가 와야한다.

손으로풀어보기

1. 들어온 입력값(문자열) 을 문자하나하나 순회한다.
2. 현재의 문자와 다음 문자를 비교해 같은 괄호인지 비교한다.
   어떻게? 현재 문자를 Map에 넣고 나온 문자와 다음 문자가 같다면? 다다음으로 이동
   같지않다면? 즉시, 종료
3. 순회가 정상적으로 끝나면 true 반환

위처럼 생각하고 아래와같이 구현해서 접근해보았지만 실패해버렸다.

public static boolean solution(String s) {  
    Map<Character, Character> mate = Map.of('(', ')', '{', '}', '[', ']');  
    
    for (int i = 0; i <= s.length() - 1; i = i + 2) {  
       char currChar = s.charAt(i);  
       char nextChar = s.charAt(i + 1);  
       
       if (mate.get(currChar) != nextChar)  
          return false;  
    }  
    
    return true;  
}

![[Pasted image 20240426095714.png]]

저런 케이스가 있을 수 있다는 생각을 왜 도출해내지 못했을까ㅠㅠ

문제를 다시 살펴보자
1. 열린 괄호는 같은 유형의 괄호로 닫아야 한다.
2. 열린 괄호는 올바른 순서로 닫아야 한다.
3. 모든 닫는 괄호에는 같은 유형의 열린 괄호가 있다.

열린 괄호는 올바른 순서로 닫아야 한다. -> 중첩된 구조를 처리한다. 라고 볼 수 있다.

자, 시작점에서 다시 시작해보자

균형 조정, 중첩 또는 순서 지정과 관련된 문제니깐...스택을 사용해 보자

1. 스택 초기화
2. 입력값으로 들어온 문자열을 순회한다.
3. 여는 괄호가 나오면 스택에 집어 넣는다.
4. 닫은 괄호가 나오면 스택에 마지막으로 들어간 요소와 비교 한다.
5. 짝이 맞다면 스택에서 꺼낸다.
6. 문자열을 모두 순회하고 난 후 스택이 비어있으면 true 반환 한다.

슈도코드

public static boolean solution(String s) {  
    스택 선언
    
    for(문자열순회) {
	    if(여는 괄호이면?) {
		    유형에 맞는 닫는 괄호를 스택에 넣는다.
	    } else if(닫는 괄호이면? 스택의 마지막 요소와 비교 후 같지 않으면)
		    false 반환
	    }
    }
    스택이 비어있으면? true 반환
}

구현

public static boolean solution(String s) {  
    Stack<Character> mate = new Stack<>();  
    
    for (char item : s.toCharArray()) {  
       if (item == '(') {  
          mate.push(')');  
       } else if (item == '{') {  
          mate.push('}');  
       } else if (item == '[') {  
          mate.push(']');  
       } else if (mate.isEmpty() || item != mate.pop()) {  
          return false;  
       }  
    }  
    
    return mate.isEmpty();  
}

Refactoring

내가 실수한 코드를 이용해 리펙터링 해보았다.

public static boolean solution(String s) {  
    Map<Character, Character> mate = Map.of('(', ')', '{', '}', '[', ']');  
    Stack<Character> stack = new Stack<>();  
    
    for (char item : s.toCharArray()) {  
       if (item == '(' || item == '{' || item == '[') {  
          stack.push(mate.get(item));  
       } else if (stack.isEmpty() || item != stack.pop()) {  
          return false;  
       }  
    }  
    
    return stack.isEmpty();  
}

• if문 사용시
  Map보다 낮은 시간 높은 메모리

• Map 사용시
  if문 보다 높은 시간 낮은 메모리