[리마인드] 스택/큐 코딩테스트 문제

오늘의 학습 키워드

스택, 큐

 

다시 풀기 문제

1. 프로그래머스 Level 2 - 기능개발

• https://school.programmers.co.kr/learn/courses/30/lessons/42586
• Github 풀이보기

프로그래머스

Algorithm-Practice/프로그래머스/2/42586. 기능개발 at main · dev-jinius/Algorithm-Practice

 

2. 프로그래머스 Level 2 - 올바른 괄호

• https://school.programmers.co.kr/learn/courses/30/lessons/12909/
• Github 풀이보기

프로그래머스

Algorithm-Practice/프로그래머스/2/12909. 올바른 괄호 at main · dev-jinius/Algorithm-Practice

 

 

프로그래머스 Level 2 - 기능개발
다시 풀기 - 실패 

 

1. 어디까지 생각해봤나?

• 같은 날짜에 배포할 작업 개수를 스택 자료구조를 활용해 스택에 남아있는 개수만큼 반환하려고 생각했다.
• Java에서 기본 제공하는 Deque(ArrayDeque) 자료구조를 Stack으로 활용해보려고 했다.
• 각 작업마다 며칠 후에 배포할 수 있는지를 나눗셈, 나머지 연산을 통해 계산했다.

2. 핵심

• 각 작업이 완료되기까지 며칠이 걸리는지?
• 같이 배포할 작업들을 어떻게 묶을 수 있는지?

3. 어려웠던 부분

• 같이 배포할 작업들을 어떻게 묶을 수 있을까?
  • 앞의 작업 완료 날짜보다 뒤의 작업 완료 날짜가 작거나 같은 경우 => 같은 배포 날짜에 배포되어야 한다.
  • 즉, 작업의 완료 날짜를 기반으로 배포할 개수를 카운트한다. => 작업 그룹화, 작업 스케줄링
• 큐로 처리할 수 있는 것을 파악해야 했다.
  • 큐는 프로세스 우선순위 문제, 배포 및 그룹화 문제, 스케줄링 문제 등에 사용된다.
  • 데이터를 순서대로 처리하는 문제
  • 후입선출로 처리하는 문제

/**
    deque는 ArrayDeque 자료구조로, 각 작업이 배포하는 데 걸리는 날짜 수가 저장되어 있다.
    result는 카운트를 저장하는 List 자료구조이다.
**/

//같은 배포 날짜에 배포되는 작업 개수 카운트하기
while (!deque.isEmpty()) {
    int day = deque.poll(); //pollFirst()와 같은 기능.
    int count = 1;
    while (!deque.isEmpty() && deque.peek() <= day) {
        count++;
        deque.poll();
    }
    result.add(count);
}

 

 

프로그래머스 Level 2 - 올바른 괄호
다시 풀기 - 성공

 

1. 핵심

• 스택 자료구조를 활용해 순서대로 괄호를 묶고, '( )' 가 되면 스택에서 제거해서 빈 스택으로 만들기
• 스택이 비어있지 않으면 False

 

2. 처음에 푼 코드

 

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    boolean solution(String s) {
        
        Deque<Character> stack = new ArrayDeque<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                if (stack.isEmpty() || stack.peek() == ')') return false;
                stack.pop();
            } else {
            	if (!stack.isEmpty() && stack.peek() == ')') return false;
                stack.push(c);
            }
        }
			
        return stack.isEmpty();
    }
}

 

 

3. 정리한 코드

 

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    boolean solution(String s) {
        
        Deque<Character> stack = new ArrayDeque<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
                continue;
            }
            
            if (stack.isEmpty()) return false;
            
            stack.pop();
        }
			
        return stack.isEmpty();
    }
}

 

 

4. Stack 자료구조 대신 카운트 활용

 

class Solution {
    boolean solution(String s) {
        
        int count = 0; 
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count += 1;
            } else {
            	if (count == 0) return false;
            	count -= 1;
            }
        }
        
        if (count == 0) return true;
        else return false;
    }
}

 

Deque 자료구조

 

1. 왜 큐와 스택을 Deque(ArrayDeque)로 사용했나?

• Java의 Stack 클래스는 내부에서 Vector라는 자료구조를 사용하는데, Vector는 자바1.0 에서 개발된 자료구조로 오래전에 설계되어 성능적으로 좋지 않다.
• Java의 Deque는 스택과 큐 모두 사용할 수 있고, ArrayDeque는 원형 큐 자료구조를 사용한다.
• 시스템의 메모리 접근 패턴, CPU 캐시 최적화 등을 고려할 때 LinkedList보다 배열을 사용하는 ArrayQueue가 더 성능이 좋다.

2. Deque 설명 및 메서드 확인

java-practice/collections/src/deque at main · dev-jinius/java-practice