코딩 테스트 합격자 되기 스터디 2주차 : 스택과 큐

스택

스택의 개념

• LIFO (Last In First Out), 가장 최근에 들어간 원소가 가장 먼저 나오는 자료구조
• 코딩테스트 특정 문제에서 스택을 필요로 하는 경우 스택을 선택할 수 있어야 한다.

ADT란?

• ADT(Abstract Data Type): 추상 데이터 타입
• 세부 사항을 숨기고 사용자에게 필요한 기능만 명시
  • 세부 사항(내부 자료구조, 프로그래밍 언어, 저장 공간의 크기)
  • 사용자에게 필요한 기능(연산, 입력, 출력)
• ADT를 사용하면, 복잡한 자료구조의 내부 구현을 감추고, 필요한 연산만 정의함으로써 자료구조 동작 자체에 집중할 수 있음

구분	정의	설명
연산	boolean isFull()	가득 차 있으면 true, 아니면 false 반환
연산	boolean isEmpty()	데이터가 하나라도 있으면 false, 아니면 true 반환
연산	void push(ItemType Item)	스택에 데이터 푸쉬
연산	ItemType pop()	스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환
상태	int top	스택에서 최근에 푸시한 데이터의 위치 기록
상태	ItemType data[maxsize]	스택의 데이터를 관리하는 배열, 최대 maxsize개의 데이터를 관리

• 자바의 Stack 클래스는 크기를 동적으로 관리하므로, max_size나 isFull() 메서드는 없다.

스택의 사용예시(괄호 짝 맞추기)

• {.{.}.)로 이뤄진 문자열이 주어질 때, 괄호의 짝이 맞는지 확인

큐

큐의 개념

• FIFO(First In First Out), 가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환
연산	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환
연산	void add(ItemType Item)	큐에 데이터를 add
연산	ItemType poll()	큐에서 처음에 add한 데이터를 poll하고, 그 데이터를 반환
상태	int front	큐에서 가장 마지막에 poll한 위치를 기록
상태	int rear	큐에서 최근에 add한 데이터의 위치를 기록
상태	ItemType data[maxsize]	큐의 데이터를 관리하는 배열

• rear는 가장 최근에 들어온 원소의 위치, front는 가장 먼저 들어온 원소의 위치

큐의 사용 예시(요세푸스 문제)

• N명의 사람들이 원형으로 둘러앉고, 각 사람들 번호를 1~N로 매김
• 시작 위치부터 K번째 사람 제거
• 제거한 위치부터 다시 K번째 사람 제거
• 앞 과정을 한명이 남을 때까지 반복

큐 구현하기

큐를 간단하게 구현하는 방식

Queue 인터페이스를 활용

• 덱(ArrayDeque) 클래스를 활용Queue 인터페이스
• add(), poll() 메서드 활용
  • add() 연산은 offer() 메서드로도 할 수 있다, add()와 offer()는 내부적으로 같은 로직 수행
  • 자바 컬렉션 프레임워크에서 Queue는 인터페이스로 구현, Queue의 구현체로 ArrayDeque와 LinkedList가 있음
  • 일반적인 코딩테스트에서는 ArrayDeque를 더 많이 사용덱을 큐처럼 활용

Queue<Integer> queue = new ArrayDeque<>(); 
queue.add(1); 
int first = queue.poll();

 

덱 (Double Ended Queue) 양 끝에서 삽입이나 삭제할 수 있는 큐
ArrayDeque<Integer> queue = new ArrayDeque<>();

queue.addLast(1);

int first = queue.pollFirst(); // 큐의 맨 앞 데이터를 제거하면서 반환

정리

• 스택: LIFO, 함수 호출 관리, 페이지 탐색, 괄호 짝 맞추기
• 큐: FIFO, 줄 서기, 요세푸스
• 스택의 경우 가장 최근 원소를 봐야하는 경우에 사용
  • 추후 DFS, 백트래킹에서 사용
• 큐는 들어온 순서대로 나갈 때 사용
  • 추후 BFS에서 사용

문제

문제 10: 괄호 회전

문제 링크: [https://school.programmers.co.kr/learn/courses/30/lessons/76502]

    public static void main(String[] args) {
        // 괄호 정보를 저장함, 코드를 간결하게 할 수 있음
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        // s 입력
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        int n = s.length(); // 원본 문자열 길이
        s += s; // 원본 문자열 뒤에 원본 문자열을 이어 붙여서 2번 나오도록 만들어줌
        int answer = 0;

        // 확인할 문자열의 시작 인덱스를 0부터 n까지 이동
        A:for (int i = 0; i < n; i++) {
            ArrayDeque<Character> stack = new ArrayDeque<>();
            for (int j = i; j < i + n; j++) {
                char c = s.charAt(j);
                if (!map.containsKey(c)) {
                    stack.push(c);
                } else {
                    if (stack.isEmpty() || !stack.pop().equals(map.get(c)))
                        continue A;
                }
            }
            if (stack.isEmpty()) {
                answer++;
            }
        }

        System.out.println(answer);
    }

문제 12: 주식가격

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584

before

자료형만 스택일 뿐, 스택의 성질을 사용하지 않고 풀었던 로직

import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;

        // prices 길이만큼 반복
        int[] answer = new int[n];
        answer[n - 1] = 0;

        for (int i = 0; i < n - 1; i++) {
            int i1 = prices[i];
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            for (int j = i + 1; j < n; j++) {
                if(i1 <= prices[j]) {
                    // 현재 값보다 클경우 stack에 push
                    stack.push(prices[j]);
                } else {
                    // 현재 값보다 작을 경우 +1하고 종료
                    stack.push(prices[j]);
                    int size = stack.size();
                    answer[i] = size;
                    break;
                }
            }
            int size = stack.size();
            answer[i] = size;
        }

        return answer;
    }
}

after

스택의 성질을 이용하여 푼 로직

import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
                int n = prices.length;
        int[] answer = new int[n];
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 가격이 떨어지는 시점을 찾는다.
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            stack.push(i);
        }

        // 끝까지 가격이 떨어지지 않은 경우를 처리한다.
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            answer[idx] = n - idx - 1;
        }

        return answer;
    }
}

문제 32: 영어 끝말잇기

    public static void main(String[] args) {

        // given
        int n = 3;
        String[] words = {"tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"};

        HashSet<String> usedWords = new HashSet<>();
        char prevWord = words[0].charAt(0);

        for (int i = 0; i < words.length; i++) {
            if (usedWords.contains(words[i]) || words[i].charAt(0) != prevWord) {
                System.out.println(Arrays.toString(new int[]{(i % n) + 1, (i / n) + 1}));
            }
            usedWords.add(words[i]);
            prevWord = words[i].charAt(words[i].length() - 1);
        }

        System.out.println(Arrays.toString(new int[]{0,0}));

    }

 

 

[출처] 코딩테스트 합격자 되기 - C++

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런