[programmers] Java Lv. 2 - 올바른 괄호

문제

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

예를 들어

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

 

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

 

제한사항

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

 

입출력 예

---

풀이

주어진 문자열을 탐색할 때 '('를 만나면 queue에 enqueue하고, ')'를 만나면 dequeue를 해서 queue가 비어있으면 true, 아니면 false를 반환한다.

단, ')'를 만났을 때 queue의 크기가 0이라면 바로 false를 반환한다.

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    boolean solution(String s) {
        Queue<Character> que = new LinkedList<Character>();
        for(char x : s.toCharArray()) {
            if(x=='('){
                que.add(x);
            }
            else{
                if(que.size()>0) que.poll();
                else return false;
            }
        }
        if(que.size()==0) return true;
        else return false;
    }
}

스택으로도 풀이가 가능하다! 

queue대신 stack을 선언한 다음, enqueue(add() or offer())와 dequeue(poll() or remove())를 각각 push()와 pop()으로 변경하면 된다.

---

Queue

큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

Java에서 Queue 사용

1. Queue 선언

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
Queue<String> queue = new LinkedList<>(); //String형 queue 선언
Queue<Character> queue = new LinkedList<>(); //char형 queue 선언

2. 초기화: clear()

queue.clear();

3. Enqueue: add(), offer()

Queue<String> queue = new LinkedList<>(); //String형 queue 선언
queue.add("first");   // queue에 "first" 추가
queue.add("second");   // queue에 "second" 추가
queue.offer("third"); // queue에 "third" 추가

4. Dequeue: poll(), remove()

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
int pollValue = queue.poll();       // queue에 첫번째 값을 반환하고 제거
// pollValue == 1
int removeValue = queue.remove();   // queue에 첫번째 값을 반환하고 제거
// removeValue == 2

- poll()과 remove() 차이점

queue.clear();
queue.poll();   // queue가 비어있으면 null 반환
queue.remove(); // queue가 비어있으면 NoSuchElementException 발생

5. Queue의 크기: size()

int queSize = queue.size();

6. 첫번째 값 반환: peek(), element()

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
int firstQueVal1 = queue.peek(); // firstQueVal1 == 1
int firstQueVal2 = queue.element(); // firstQueVal2 == 1

- peek()과 element() 차이점

queue.clear();
queue.peek();    // queue가 비어있으면 null 반환
queue.element(); // queue가 비어있으면 NoSuchElementException 발생

 

참고: https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0), https://coding-factory.tistory.com/602