프로그래머스 올바른 괄호

김희진·2023년 8월 7일

프로그래머스

프로그래머스 코딩테스트

목록 보기

3/6

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예시

입출력 예 설명

입출력 예 #1,2,3,4

문제의 예시와 같습니다.

문제 풀이

조건 1. 문자열 “(” “)” 의 갯수가 일치해야 한다.
조건 2. 첫번째 글자가 “(”로 시작해야한다.
조건 3.() 짝이 맞아야하며 짝이 맞은 후에는 다시 “(”로 시작해야한다.
“(” 와 “)” 는 split 을 사용할 수 없음 > 언어에서 문자로 인식하지 않고 괄호를 해석하려고 하기 때문 ex) String[] words = s.split(" \)");
ArrayList a = new ArrayList<>(); 형식은 a.add(substring); 형식으로 넣어주기

오답 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        ArrayList<String> a = new ArrayList<>();
        ArrayList<String> b = new ArrayList<>();
        int countA = 0;
        int countB = 0;

        for (int i = 0; i < s.length(); i++) {
              if (s.charAt(0) == ')') {
                answer = false;
                break; 
              }else {
            String substring = s.substring(i, i + 1);
            if (substring.equals("(")) {
                a.add(substring);
                countA++;
            } else if (substring.equals(")")) {
                 if (countA != 0 && countA - countB == 0) {
                    answer = false;
                    break; 
                 }
                else {
                b.add(substring);
                countB++;
                 }
            }
            if (a.size() == b.size()) {
             return true;
            }
              }
        }

        return answer;
    }
}

정답 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false; 
                }
            }
        }
        
        return stack.isEmpty(); // 괄호 안이 올바른지 확인 
    }
}

개념 정리

[Java] 자바 Stack 클래스 사용법 & 예제 총정리

Stack 클래스

Stack이란?

자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

Stack의 특징

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조

2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함

3. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임

4. 그래프의 깊이 우선 탐색(DFS)에서 사용

5. 재귀적(Recursion) 함수를 호출 할 때 사용

Stack 사용법

Stack 선언

import java.util.Stack; //import
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
Stack<String> stack = new Stack<>(); //char형 스택 선언

**Stack 값 추가**

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가

**Stack 값 삭제**

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.pop();       // stack에 값 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

**Stack의 기타 메서드**

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)