99클럽 코테 스터디 3일차 TIL + Stack

✨ 문제 

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.

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

 

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

 

 

 

✨ 개념

Stack

- 후입선출을 구현한 자료구조

- 스택의 입출력은 맨 위에서만 가능하고, 중간에서는 데이터 삭제 불가.

 

 

 

✨ 최종코드

public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        // 여는 괄호일 경우 스택에 넣음
        if (c == '(' || c == '[' || c == '{')
            stack.push(c);

        // 닫는 괄호로 시작할 경우 false return
        if (stack.isEmpty()) return false;

        // 닫는 괄호일 경우 스택 최상단에 있는 괄호와 같은 타입이면 pop()
        // 다른 타입일 경우 false 리턴.
        if (c == ')') {
            if (stack.peek() == '(') 
            	stack.pop();
            else return false;
        }
        else if (c == ']') {
            if (stack.peek() == '[') 
            	stack.pop();
            else return false;
        }
        else if (c == '}') {
            if (stack.peek() == '{') 
            	stack.pop();
            else return false;
        }
    }

    return stack.isEmpty();
}

 

처음엔 문제 설명이 영어로 되어있기도 하고 예제가 부족해서 문제를 잘못 이해했다. 여는괄호와 동일한 타입의 닫는 괄호가 연속해서 나와야 하는걸로 코드를 작성해서 "([])" 이런 식의 테스트 케이스를 통과하지 못했다. 그래서 테스트 케이스에 맞게 다시 코드를 작성했다.

 

입력받은 문자열 s를 String 배열로 변환 후 forEach문을 통해 여는 괄호일 경우 스택에 push하고, 닫는 괄호일 경우 peek한 값이 닫는 괄호와 동일 타입이면 pop을 하고, 아닐 경우 false를 리턴하도록 했다. for문을 다 돌면 true를 리턴하도록 했다. 그런데 이번에도 통과하지 못한 테스트 케이스가 있었다. 입력받은 문자열에 여는 괄호 하나만 있는 경우였는데 어떻게 해결해야하나 생각하다가 마지막 return문에 stack.isEmpty값을 리턴하도록 수정하였다.

 

테스트 케이스는 통과했지만 런타임이 평균 이하로 나왔다. 다른 코드들을 참고해보니 입력받은 문자열 s를 String 배열이 아닌 Char 배열로 변환하여 사용하였다. 생각해보니 문자열을 한 글자씩 쪼개야하는거니까 char 배열을 사용하는게 더 적절했던 것 같다.

String 배열의 크기가 궁금해서 찾아보니 String 객체는 문자열 자체를 저장하는 메모리 외추가적인 객체 오버헤드가 있다고 한다. 자바에서 String 객체는 내부적으로 char 배열을 포함하고, 이 배열을 가리키는 참조와 기타 메타데이터를 저장한다. 그래서 일반적으로 String은 최소 40바이트 정도를 차지하므로 40 * 문자열 길이가 된다. char 배열은 글자 당 2byte씩이므로 2 * 문자열 길이이다.

그래서 char로 바꾼 뒤 실행 결과는

String 배열로 변환 시 Runtime 7ms, Memory 42.03MB

Char 배열로 변환 시  Runtime 1ms, Memory 41.17MB

이다. 실제로 메모리가 많이 차이나지 않는 이유는 JVM의 힙 메모리 관리 방식, 가비지 컬렉션 등의 영향이 있기 때문이다. 

 

오늘 배운점 : 변수 하나를 생성 할 때도 효율을 따져서 해야한다 . . 🕺🏼 🕺🏼 🕺🏼