P-coding

오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.
가장 기본적인 구조로 선입선출 ( FIFO, First In First Out ) 방식을 가진다.
먼저 온 사람이 나가는 흔히 매장에 줄 서는 과정이라 볼 수 있다.
( Queue 단어 자체가 표 같은 것을 구매하기 위해 줄 서는 것을 의미 )

큐 ( Queue )

• 선입 선출 ( FIFO, First In First Out )
• 데이터가 들어오는 위치는 가장 뒤 Rear or Back 에서 이루어지고, 데이터가 나가는 위치인 가장 앞 Front, 양쪽에서 삽입 삭제가 이루어진다.
• BFS ( 너비 우선 탐색 ), 프로세서 핸들링 ( CPU 헤드링 ) 등에 사용.

class Queue{
    private LinkedList<Integer> queue;

    public Queue(){
        queue = new LinkedList<>();
    }
    ....
}

큐의 기본 연산

1. Enqueue(value): 데이터 삽입

• 큐의 맨 뒤(back)에 데이터를 추가하는 연산

    public void enQueue(int x){
        queue.addLast(x);
    }

2. Dequeue(): 데이터 제거

• 큐의 맨 앞(front)에 있는 데이터를 제거하고 반환하는 연산

    public int depQueue(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.removeFirst();
    }

3. peek() : 최상단 데이터 확인

• 큐의 맨 앞(front)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.getFirst();
    }

4. isEmpty(): 큐이 비어 있는지 확인

• 큐가 비어 있으면 true, 아니면 false 반환

    public boolean isEmpty(){
        return queue.isEmpty() ? true : false;
    }

로직 예시)

1. 빈 큐다

2. Enqueue ( 2 ) 를 통해 가장 앞 부터 채워 넣는다.

3. Enqueue ( 4 ) 를 통해 2 다음에(뒤에서부터) 채워 넣는다.

4. Dequeue 릍 통해 가장 앞에 있는 2를 꺼내고 4를 앞으로 옮긴다.

추가 - JAVA의 큐 관련 클래스

자바에서 큐는 Interface로 구현되어 ArrayDeque, LinkedList, PriorityQueue로 직접 구현할 수 있다.

그 밖에도 Blocking 즉 고정된 크기의 배열을 사용하는 큐도 존재한다.

이는 자바에서 원형 큐의 고정된 크기를 구현하기 위함으로 보인다.

이 글에서는 LinkedList로 정의된 큐와 달리 양쪽에서 삽입과 삭제가 이루어질 수 있는 양방향 큐이며, 메모리 동적인 요소를 가지고 있다.

ArrayDeque도 비슷하나 LinkedList와는 다르다. 배열로 사용되며 동적으로 변하긴 하지만, 배열을 다시 늘려야하는 번거로움이 있다. 추후 ArrayList와 LinkedList의 차이에 대해 포스팅할 예정이다.

DeQueue

 양방향에서 삽입/삭제가 이루어 질 수 있는 양방향 큐를 의미한다.

원형 큐

blocking으로 정의된 큐는 원형 큐라고 할 수 있으며 다음과 같은 형태을 가진다.

데이터가 삽입/삭제 됨에 따라 front와 back(rear)를 가리키는 위치가 계속 변하지만, 크기는 고정된 상태로 이루어진다.

다음과 같이 예시를 볼 수 있다.

PriorityQueue

우선순위 큐로 우선순위 비교는 Comparable interface를 활용하여 구현하거나 Comparator를 사용하여 설정할 수 있다.

중복 요소를 허용하고, 정렬된 순서로 요소를 처리하기 때문에 성능에 영향이 줄 수 있는 큐다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);

System.out.println(queue.poll());  // 1 (가장 작은 값이 먼저 출력됨)

PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
queue.add(1);
queue.add(3);
queue.add(2);

System.out.println(queue.poll());  // 3 (가장 큰 값이 먼저 출력됨)

이미 많고 다양한 큐가 만들어져 있기 때문에
편한 방법과 편한 클래스가 자바처럼 다양하게 존재하지만,
기본 자료구조를 이해하지 못한다면 활용하기가 어렵다.
때문에 그걸 사용하기 이전에 기본에 대한 이해를 점검하고 사용하도록 하자.
( ctrl + 클릭 을 통해 자바 클래스 내부를 확인 할 수 있다. )

취업 준비하면서 공부를 하다 개발자로써는 사실 거의 의미 없다고들 하지만,
네트워크 관련 흥미가 생겨 공부하다 겸사겸사 하게 되었습니다.
준비해서 나쁠것도 없고, 시험이 쉬운편이라고 하니 한 번 해보시길 바랍니다.

네트워크 관리사 2급

• 네트워크 관리사 2급은 네트워크 관련 업무 수행을 위한 일반적인 운용지식과 구축기술, NOS운영, Packet분석, Monitoring, 인터넷 기술, Protocol 등 기초 이론과 실무능력 검정 기준으로 한다.
• 2급은 공인 민간 자격으로 국가공인 자격이다.
• 자격발급기관은 한국정보통신자격협회에서 주관합니다.
• 1급은 기준이 있으나 2급은 제한없이 응시 할 수 있습니다.
• 필기 시험시간은 1급 60분 2급 50분입니다.

시험일정

1급은 서울에서만 응시할 수 있고 2회만 존재합니다.

2급은 매년 4회 응시할 수 있고 여러 지역에서 응시 가능합니다.

준비물

• 신분증, 볼펜
• 신분증이 없으면 응시가 절대 불가합니다.

가격

2급은 필기은 43,000원, 실기는 78,000원입니다.

합격

합격은 모두 100점 만점에 60점 이상입니다.

필기 공부법

• 교재는 사실상 필요없는 수준입니다.
• 만약 컴퓨터 관련과가 아닌상태여서 이론이 부족하시다면 교재사서 공부하시면 될 것 같습니다.
• CBT 에서 문제 풀고 틀린 문제 위주로 공부했습니다.

필기 합격률은 평균 30% 정도지만, 많은 풀이와 개념을 이해한다면 아주 쉬운 시험입니다.
예를 들어 SSH에 대해 물어본다면 SSH가 무엇인지 무슨 포트를 사용하며 무슨 목적으로 사용되는지..

물론 시험을 통과하기만을 위한 공부법도 있지만,
저는 공부하면서 시험보는 만큼 문제에 나온 설명을 통해 유추하여 푸는 과정으로 공부했습니다.
그렇다고 시험 자체 난이도는 매우 쉬운편으로 속했기 때문에 시험 시간은 10분정도였습니다.

모두 합격하시길 바라며 다음에는 실기 합격으로 돌아오겠습니다.

이번 글에서는 4949번 문제를 통해 스택을 활용,
괄호의 균형을 맞춰완벽한 문장을 나타내 보자.

---

문제 핵심

• 문자열은 ( ),  [ ] 이 두 소괄호와 대괄호가 짝을 이루어야 한다.
• 1 : 1 매칭만 가능하다.
• 공백 이후의 . 과 같은 괄호가 없는 문장도 균형 잡힌 문자열이다.
• (, [ 이 나온 후에 ), ] 가 나와야 짝이 이루어 진다. 
  • ] [ 은 짝이 아닌 경우 

풀이 과정

먼저 우리가 찾아야 할 것은 괄호들이다.

이는 StringTokenizer를 활용해 볼 예정이다. ( 물론 chatAt()을 사용하면 더 빠르다. )

다음 자료구조 스택에 대한 글과 split과 StringTokenizer비교에 관한 글을 참고하면 좋을 것 같다.

1. 괄호 문자 저장

먼저 StringTokenizer를 통해 소괄호, 대괄호를 기준으로 문자를 나눈다.

그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.

true로 설정하면 구분자도 Token에 포함된다.

stringTokenizer = new StringTokenizer(sentence,"([)]",true);

2. 괄호 문자 찾아 균형확인하기

1. 구분자에 포함된 토큰 중에 괄호를 찾는다.

2. (, [ 라면 스택에 넣는다

3 - 1. ], ) 라면 스택에서 꺼내 비교한다

3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리

while(stringTokenizer.hasMoreTokens()) {

    String token = stringTokenizer.nextToken();

    if (token.equals("(") || token.equals("[")) {
        push(token);
    }
    else if (token.equals(")")) {
        if (!pop().equals("(")) {
            isPerfect = false;
            break;
        }
    }
    else if (token.equals("]")) {
        if (!pop().equals("[")) {
            isPerfect = false;
            break;
        }
    }
}

3. 스택에 남아있는 값 확인

마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.

if (!delimStack.isEmpty()) isPerfect = false;

스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때,
다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다.
이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이
다양한 방법으로 풀어보는 것을 추천한다.

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    private static LinkedList<String> delimStack;

    private static void push(String delim){
        delimStack.addLast(delim);
    }

    private static String pop(){
        return delimStack.isEmpty() ? " " : delimStack.removeLast();
    }


    public static void main(String[] args) throws IOException {
        delimStack = new LinkedList<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        boolean isPerfect;
        StringTokenizer stringTokenizer;

        while (true) {
            isPerfect = true;
            delimStack.clear();
            String sentence = bufferedReader.readLine();

            if(sentence.equals(".")) break;

            stringTokenizer = new StringTokenizer(sentence,"([)]",true);


            while(stringTokenizer.hasMoreTokens()) {

                String token = stringTokenizer.nextToken();

                if (token.equals("(") || token.equals("[")) {
                    push(token);
                }
                else if (token.equals(")")) {
                    if (!pop().equals("(")) {
                        isPerfect = false;
                        break;
                    }
                }
                else if (token.equals("]")) {
                    if (!pop().equals("[")) {
                        isPerfect = false;
                        break;
                    }
                }
            }

            if (!delimStack.isEmpty()) isPerfect = false;


            stringBuilder.append(isPerfect ? "yes\n" : "no\n");
        }

        System.out.println(stringBuilder);
    }
}