자바 - Stack 및 Vector로 코테 푸는 법

자~ 코딩 테스트에서 Stack 쓸 경우를 좀 파악해 봅시다.

1. 코테에서 스택을 사용해야 하는 때

스택은 후입선출(Last In First Out, LIFO) 구조로, 가장 마지막에 들어온 요소가 가장 먼저 나가는 특성을 가집니다. 이 특성은 특정 유형의 알고리즘 문제에서 매우 유용하며, 스택을 사용해야 하는 몇 가지 상황은 다음과 같습니다:

• 괄호 검사: 코드에서 괄호의 짝이 맞는지 확인하는 문제 <- 괄호 나오면 스택으로 풀자!!!
• 역순 문자열: 문자열을 역순으로 뒤집거나 순서를 조작해야 하는 경우 <- 무조건 스택 쓰는 건 아니지만 스택부터 생각하자!
• 후위 표기법 계산: 수식이 주어진 경우, 이를 계산하기 위해 스택 사용
• 재귀 알고리즘의 반복적 구현: 재귀 함수를 스택을 사용하여 반복적으로 풀기
• 깊이 우선 탐색(DFS): 그래프의 깊이 우선 탐색을 구현할 때

2. 코테에서 스택을 사용해야 하는 문제의 특징

스택을 사용해야 하는 문제는 일반적으로 다음과 같은 특징을 가지고 있습니다:

• 후입선출(LIFO) 처리가 필요: 문제의 요소들이 마지막에 추가된 것부터 처리되어야 할 때.
• 중간 요소의 접근이 불필요: 중간 요소에 임의로 접근할 필요가 없고, 오직 가장 최근에 추가된 요소만을 다루면 충분한 경우.
• 재귀적 특성: 문제가 재귀적 특성을 갖고 있으며, 이를 스택을 사용하여 반복적으로 해결할 수 있는 경우.
• 컨텍스트 백업: 현재 상태나 위치를 저장했다가 다시 돌아와야 하는 경우.

많이 복잡하지 않은 문제라면 굳이 ArrayDeque 쓸 것 없이 스택으로 간단하게 풀어도 될 것 같다.

---

그럼 Vector 문제부터 좀 보자.

 

...GPT가 생성을 못 해서 백준에서 확인하니 Vector 문제 자체가 없네.
그럼 그냥 대충 느낌만 느끼고 가자.

문제: 공유된 자원에 대한 스레드 안전한 접근

문제 설명: 여러분은 다수의 스레드가 동시에 접근하여 데이터를 추가하고 읽을 수 있는, 스레드 안전한 로깅 시스템을 구현해야 합니다. 이 로깅 시스템은 로그 메시지를 저장하는 역할을 하며, 스레드 간의 데이터 경쟁이 없도록 보장해야 합니다. Vector 클래스를 사용하여 이를 구현하십시오.

요구 사항:

1. LogManager 클래스를 구현합니다.
2. LogManager는 내부적으로 Vector<String>를 사용하여 로그 메시지를 저장합니다.
3. addLog(String log) 메서드를 통해 로그 메시지를 추가합니다. 이 메서드는 스레드 안전해야 합니다.
4. getLogs() 메서드를 통해 현재까지의 모든 로그 메시지를 반환합니다. 이 메서드 역시 스레드 안전해야 합니다.

import java.util.Vector;

public class LogManager {
    private Vector<String> logs = new Vector<>();

    // 스레드 안전한 로그 추가
    public synchronized void addLog(String log) {
        logs.add(log);
    }

    // 스레드 안전한 로그 리스트 조회
    public synchronized Vector<String> getLogs() {
        return new Vector<>(logs); // 복사본 반환으로 원본 데이터 보호
    }

    public static void main(String[] args) {
        LogManager logManager = new LogManager();
        // 여러 스레드에서 로그 추가 시뮬레이션
        Thread thread1 = new Thread(() -> logManager.addLog("Thread 1: Log entry"));
        Thread thread2 = new Thread(() -> logManager.addLog("Thread 2: Log entry"));
        Thread thread3 = new Thread(() -> logManager.addLog("Thread 3: Log entry"));

        thread1.start();
        thread2.start();
        thread3.start();

        try {
            thread1.join();
            thread2.join();
            thread3.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("All logs:");
        Vector<String> allLogs = logManager.getLogs();
        allLogs.forEach(System.out::println);
    }
}

---

자! 이제 Stack 문제로 가자!

문제: 유효한 괄호

문제 설명: 주어진 문자열이 유효한 괄호로 이루어져 있는지 판별하세요. 유효한 괄호란 각 여는 괄호 '('가 닫는 괄호 ')'와 정확하게 짝을 이루고, 이러한 짝이 제대로 닫혀야 합니다.

 

예시:

• 입력: "()"
• 출력: true
• 입력: "(]"
• 출력: false
• 입력: "([)]"
• 출력: false
• 입력: "{[]}"
• 출력: true

import java.util.Stack;

public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String s1 = "()";
        String s2 = "(]";
        String s3 = "([)]";
        String s4 = "{[]}";
        System.out.println(isValid(s1)); // true
        System.out.println(isValid(s2)); // false
        System.out.println(isValid(s3)); // false
        System.out.println(isValid(s4)); // true
    }
}

 

😄