[자료구조] 백준 9012 괄호

9012번: 괄호

https://www.acmicpc.net/problem/9012

 

# 코드

import java.io.*;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트 케이스의 개수 T
        long t = Long.parseLong(br.readLine());

        // "(" 를 스택에 넣고 ")" 가 나타나면 pop 하는 방식
        // 스택으로 사용할 LinkedList
        LinkedList<String> s_list = new LinkedList<>();

        // T만큼 반복
        for (long i = 0; i < t; i++) {
            String line = br.readLine();
            boolean flag = true;

            // 각 라인의 길이만큼 반복 (NO일 경우 중도 탈출)
            for (int j = 0; j < line.length(); j++) {
                // "(" 인지 ")" 인지 구분
                if (line.substring(j, j + 1).charAt(0) == '(') {
                    s_list.add("(");
                } else {
                    // 스택 size가 0인데 ")" 가 나타날 경우 : NO
                    if (s_list.size() == 0) {
                        bw.write("NO\n");
                        flag = false;
                        break;
                    } else {
                        // 스택 size가 0이 아니라면
                        // removeLast() : 마지막 노드를 제거하는 메소드
                        s_list.removeLast();
                    }
                }
            }

            // 각 라인 for문 종료 후 flag가 여전히 true라면 실행
            if (flag == true) {
                // - 스택 size가 0이 아닐 경우 [=스택에 "("가 남았을 경우] : NO
                // - 스택이 모두 비워졌다면 비로소 해당 라인은 YES
                if (s_list.size() != 0) {
                    bw.write("NO\n");
                } else {
                    bw.write("YES\n");
                }
            }

            // clear() : LinkedList 를 완전히 비우는 메소드
            s_list.clear();
        }

        // Reader 버퍼 닫기
        br.close();

        // Writer 버퍼 비운 뒤 닫기
        bw.flush();
        bw.close();
    }
}

• 스택을 활용해 올바른 괄호인지 판단할 수 있는 문제였다.
• "(" 이면 스택에 삽입하고, ")" 가 나타나면 pop을 하며 짝을 맞추면 된다.
• 스택이 빈 상태에서 ")" 가 나타나는 경우 NO를 출력하고 flag를 false로 변경한 후 break으로 내부 for문을 빠져나온다. 이미 괄호의 짝이 맞지 않기 때문이다.
• 내부 for문 종료 후 flag가 여전히 true라면 스택이 모두 비워졌는지 한 번 더 검사한다. 스택이 모두 비워졌다면 비로소 해당 라인이 YES라고 출력한다.
• cf) 스택으로 사용하는 s_list 는 반복문의 마지막에서 꼭 비워주어야 한다. s_list 의 값이 남으면 다음 반복에 지장을 주기 때문이다. clear() 메소드를 사용해 LinkedList를 완전히 비울 수 있다.

 

if (line.substring(j, j + 1) == "(") // XXX
if (line.substring(j, j + 1).charAt(0) == '(') // OOO

// charAt() : String으로 저장된 문자열 중에서 한 글자만 선택해서 char타입으로 변환해주는 메소드

• 이번 문제에서 가장 흥미로웠던 것은 String 과 char 의 차이였다.
• 분명 substring으로 문자열을 잘랐는데도 "(" 처럼 String으로 비교하려 하니 모두 false를 외치며 else문으로 넘어갔기 때문이
• 이유는 근본적인 String의 특성에 있었다. 문자열, 즉 String은 ==으로 비교할 수 없다. ==를 사용할 경우 각자 참조하는 주소를 비교하기 때문이다.
• 이에 반해 char은 단 1개의 문자를 값으로 가지며 ==를 사용해 동등 비교를 수행할 수 있다.
• char은 문자 타입으로 분리되지만 사실 2byte의 정수이며, 내부적으로는 아스키코드에 따라 숫자로 치환되어 저장되는 특성을 가지고 있다. 이 때문에 char은 동등 비교 연산자로 ==를 사용할 수 있는 것이다.

 

• 하지만 char로 변환하는 것이 번거롭고 String만으로 동등 비교를 하고 싶다면 메소드를 사용하면 된다.
• 다음과 같이 equals() 메소드를 사용하면 정상적으로 비교할 수 있다.

if (line.substring(j, j + 1).equals("("))

 

아래가 char로 변환하여 비교한 결과이고 위가 equals() 메소드를 사용한 결과이다.