[묘공단] 코딩 테스트 합격자 되기 - 스택, 큐

코딩 테스트 합격자 되기 자바편

 

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

 

스택

개념 : 쌓는다는 의미를 갖고있으며 먼저 입력한 데이터가 제일 늦게 나온다. FILO(first in last out) 선입후출로 동작하며

스택에 데이터를 삽입하는 연산을 push 꺼내는 연산을 pop이라하며 최근 데이터를 반환하지만 꺼내지 않을 경우 peek을 사용 한다.

 

데이터의 순서와 상관없이 임의 접근을 위주로 작업시에는 배열을 사용하면 유리

스택의 경우 최근에 사용한 데이터를 대상으로 뭔가 연산하는 경우 유리

 

스택의 개념은 쉽지만 어느 문제에 적용해야할지 모르기때문에 문제를 활용해서 적응해야한다.

 

스택 예제 문제

 

문제 설명 : 괄호가 정상적으로 닫히는지 여부를 판단 하여 정상 또는 비정상으로 출력

예시 )

1. ()()(()) 정상적으로 괄호가 닫혀있기때문에 정상 출력

2. )() 괄호가 정상적으로 닫히지않은 케이스가 존재하기 때문에 비정상 출력

import java.util.*;

public class Main {
    public static void main(String[] args){
    	// 정상 여부 확인할 괄호
        String values = "(())()";
		// 메서드 호출 후 참,거짓 판별 후 출력
        System.out.println(stackPractice(values) ? "정상" : "비정상");
    }

    public static boolean stackPractice(String s) {
		// 스택 생성
        Stack<Character> stack = new Stack<>();
		
        // 문자열을 문자로 쪼개어 하나씩 검증
        for (char charItem : s.toCharArray()) {
        	// 좌측 괄호가 나오면 stack에 넣는다.
            if (charItem == '(') {
                stack.push(charItem);
            } else {
            	// 우측 괄호가 나오면 stack에 넣은 좌측괄호를 꺼낸다.
                // stack이 빈경우는 짝이 맞지 않기 때문에 비정상 괄호
                // stack.pop() == ')'은 pop을 위한 구문
                if (stack.isEmpty() || stack.pop() == ')') {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

 

큐

개념 : 줄을 서다라는 뜻을 가지고있으며 먼저 들어간 데이터가 먼저 나오는 자료구조이다. 선입선출 구조로 FIFO (first in first out)

이라고 한다. 큐에 삽입하는 연산을 Enqueue(Add), 꺼내는 연산을 Dequqeue(Poll)이라고한다.

큐는 보통 선형구조인데 poll시 데이터를 삭제하는게 아니라 front가 가르키는 인덱스만 다음칸으로 이동한다.

따라서 데이터를 삭제하지 않았지만 삭제한것처럼 관리하게 된다. 이 부분은 메모리 낭비도 일어난 상황이라고 볼 수 있다.

 

단 자바에서 ArrayDequeue를 사용하여 pollFirst 메서드를 호출하면 맨앞에 데이터를 제거하면서 반환할 수 있다.

만일 ArrayDequeue에 addFirst로 넣고 pollFirst로만 꺼낸다면 스택의 push pop과 같이 사용이 가능하다.

 

큐 예제문제

문제 설명 : N명의 사람이 원형태로 서 있고 각 사람 부터 1 ~ N 까지 번호표를 갖고있다.

K숫자가 주어졌을때 K번 사람을 기준으로 반복해서 K만큼 건너뛰어 사람을 제거해 나간후 마지막에 남는 번호를 출력한다.

import java.io.IOException;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) throws IOException {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        int k = 2;
        int index = 0;

        // 큐에 5개의 숫자를 넣는다.
        for (int i = 1; i <= 5; i++) {
            queue.add(i);
        }

        // 큐에서 k번째 숫자를 반복하여 제거해 나간다.

        while (1 < queue.size()) {
            // 1번째 방법 
            // 반복문으로 k만큼 poll && add 후 적용
            for (int i = 0; i < k - 1; i++) {
                queue.add(queue.pollFirst());
            }
            queue.pollFirst();
            // 2번째 방법
            /** 매 반복 마다 조건 확인
            if (++index == k) {
                queue.pollFirst();
                index = 0;
            } else {
                queue.add(queue.pollFirst());
            }
             *
             */
        }
        System.out.println(queue.pollFirst());
    }
}