[99클럽 코테 스터디_ DAY 8] 올바른 괄호

yewon·2024년 7월 30일
0

스터디

목록 보기
8/22
post-thumbnail

올바른 괄호

✏️오늘의 문제



💡나의 풀이


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

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    return false; 
                }
                stack.pop(); 
            }
        }

       
        return stack.isEmpty();
    }

작동 원리

  1. Stack 초기화: Stack<Character> stack = new Stack<>();를 통해 괄호를 쌓아둘 Stack을 초기화합니다. Stack은 후입선출(LIFO) 구조로, 가장 최근에 추가된 요소가 가장 먼저 제거됩니다.

  2. 문자열 반복: for (char c : s.toCharArray())를 사용하여 문자열 s의 각 문자를 순회합니다.

  3. 여는 괄호 처리: 문자가 여는 괄호 '('일 경우, stack.push(c);를 통해 Stack에 추가합니다.

  4. 닫는 괄호 처리: 문자가 닫는 괄호 ')'일 경우:

    • 먼저 Stack이 비어 있는지 확인합니다. 비어 있다면, 여는 괄호가 없으므로 return false;를 통해 잘못된 괄호 문자열임을 반환합니다.
    • Stack이 비어 있지 않다면, stack.pop();을 통해 가장 최근에 추가된 여는 괄호를 제거합니다.
  5. 결과 반환: 반복이 끝난 후 return stack.isEmpty();를 통해 Stack이 비어 있으면 모든 여는 괄호가 짝을 이루었으므로 true를 반환하고, 그렇지 않으면 false를 반환합니다.


💡다른 사람의 풀이

 boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }

        return answer;
    }

작동 원리

  1. 변수 초기화

    • boolean answer = false;는 최종 결과를 저장할 변수를 초기화합니다. 기본값은 false로 설정되어 있습니다.
    • int count = 0;는 여는 괄호의 개수를 세기 위한 카운터를 초기화합니다.
  2. 문자열 반복: for(int i = 0; i < s.length(); i++)를 사용하여 문자열 s의 각 문자를 순회합니다.

  3. 여는 괄호 처리

    • if(s.charAt(i) == '(')의 조건이 참이면, count++;를 통해 여는 괄호의 개수를 증가시킵니다.
  4. 닫는 괄호 처리

    • if(s.charAt(i) == ')')의 조건이 참이면, count--;를 통해 여는 괄호의 개수를 감소시킵니다.
    • 이때 if(count < 0) 조건을 통해 닫는 괄호가 여는 괄호보다 많아지는 상황(즉, 잘못된 괄호 문자열임)을 감지합니다. 이 경우 break;를 통해 반복문을 종료합니다.
  5. 결과 결정

    • 반복이 끝난 후 if(count == 0) 조건을 통해 여는 괄호와 닫는 괄호의 개수가 같으면 answer = true;로 설정합니다. 이는 모든 여는 괄호가 짝을 이루었다는 것을 의미합니다. 그렇지 않으면 answer는 여전히 false입니다.
  6. 결과 반환: 최종적으로 return answer;를 통해 괄호 문자열의 유효성을 반환합니다.


➕Stack이란?


스택(Stack)은 데이터 구조의 일종으로, 후입선출(LIFO, Last In First Out) 방식으로 작동합니다. 즉, 가장 마지막에 추가된 데이터가 가장 먼저 제거되는 구조입니다. 스택은 일상생활에서도 쉽게 찾아볼 수 있는 개념으로, 접시를 쌓아 놓았을 때 위에 쌓인 접시를 먼저 꺼내는 것과 유사합니다.

스택의 기본 연산

  1. 푸시(Push): 스택에 데이터를 추가하는 연산입니다. 새로운 데이터는 스택의 가장 위에 쌓입니다.

  2. 팝(Pop): 스택에서 데이터를 제거하는 연산입니다. 가장 위에 있는 데이터가 제거되고 반환됩니다.

  3. 피크(Peek): 스택의 가장 위에 있는 데이터를 제거하지 않고 확인하는 연산입니다. 스택의 상태를 변경하지 않습니다.

  4. isEmpty: 스택이 비어 있는지를 확인하는 연산입니다. 비어 있다면 true, 그렇지 않다면 false를 반환합니다.

스택의 특징

  • LIFO 구조: 가장 최근에 추가된 데이터가 가장 먼저 제거됩니다.
  • 고정된 크기: 스택은 고정된 메모리 공간을 사용할 수 있으며, 크기를 초과하면 오버플로우가 발생할 수 있습니다.
  • 동적 크기: 동적으로 크기를 조절할 수 있는 스택도 있으며, 이 경우 메모리 할당이 필요합니다.

스택의 활용

스택은 다양한 분야에서 유용하게 사용됩니다:

  1. 함수 호출 관리: 프로그램에서 함수가 호출될 때, 스택에 호출된 함수의 정보를 저장합니다. 함수가 종료되면 해당 정보가 스택에서 제거되어 원래 상태로 돌아갑니다.

  2. 수식 계산: 후위 표기법과 같은 수식 연산에 사용됩니다. 연산자와 피연산자를 스택에 저장하여 계산할 수 있습니다.

  3. Undo 기능: 텍스트 편집기와 같은 프로그램에서 마지막 작업을 취소하는 기능은 스택을 이용하여 구현됩니다.

  4. 괄호 검사: 괄호의 유효성을 검사할 때, 여는 괄호를 스택에 저장하고 닫는 괄호가 나올 때마다 스택에서 제거하여 쌍을 확인합니다.

예제

다음은 자바를 이용한 간단한 스택 구현 예시입니다:

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 푸시 연산
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 피크 연산
        System.out.println("Top element: " + stack.peek()); // 3

        // 팝 연산
        System.out.println("Popped element: " + stack.pop()); // 3
        System.out.println("Top element after pop: " + stack.peek()); // 2

        // 스택이 비어 있는지 확인
        System.out.println("Is stack empty? " + stack.isEmpty()); // false
    }
}

0개의 댓글