ฅ^._.^ฅ

배열과 리스트

배열(Array) 이란?

메모리 상에서 연속된 공간을 차지하는 데이터 구조

인덱스를 이용하여 O(1) 시간 복잡도로 접근 가능

배열 예제

 int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers[2]); // O(1) - 즉시 접근 가능

➡︎ 빠른 조회 가능

➡︎ 크기가 고정되어 있고, 삽입/삭제가 비효율적

연결 리스트(Linked List) 란?

노드(Node) 와 포인터(Pointer) 로 구성된 데이터 구조

시간 복잡도: 삽입/삭제는 O(1), 검색 속도는 O(N)

단일 연결 리스트 예제

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;
    
    void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(data);
    }
}

➡︎ 동적 크기 조절 가능

➡︎ 연속된 메모리 공간 사용하지 않아도 되지만, 노드 탐색 속도가 느림

배열 vs 연결 리스트 비교

스택과 큐

스택(Stack) 이란?

후입선출(LIFO, Last In First Out) 구조

재귀 함수 호출, 되돌리기(Undo), 괄호 검사 등에 활용

스택 예제

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 출력: 3 (후입선출)

➡︎ 마지막에 넣은 데이터가 가장 먼저 제거

큐(Queue) 란?

선입선출(FIFO, First In First Out) 구조

작업 대기열, 너비 우선 탐색(BFS) 등에 활용

큐 예제

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 출력: 1 (선입선출)

➡︎ 먼저 들어온 데이터가 먼저 제거

스택 vs 큐

[Level2] 프로세스

문제 이해

→ 프로세스의 값이 아님 위치로 판단해야 함

슈도 코드

1. 큐(queue)와 우선순위(priority queue)를 초기화한다.
   - queue: (인덱스, 우선순위) 형태로 저장
   - priorityQueue: 우선순위 값들만 저장 (내림차순 정렬)

2. 반복문을 실행하면서 다음을 수행:
   - queue에서 (현재 인덱스, 현재 우선순위)를 poll()
   - 현재 우선순위가 priorityQueue에서 가장 높은 값과 같은지 비교:
     - 같다면 실행 (answer += 1)
     - 목표 인덱스이면 종료하고 answer 반환
     - 다르면 다시 queue에 추가

참고한 부분

// 큐에 배열로 저장 가능
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{i, priorities[i]});


// 우선순위 큐
// 기본형: 우선순위가 낮은 숫자 먼저 (오름차순)
PriorityQueue<Integer> pQueue = new PriorityQueue<>();
 
// 우선순위가 높은 숫자 먼저(내림차순)
PriorityQueue<Integer> pQueue = new PriorityQueue<>(Collections.reverseOrder());

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<int[]> queue = new LinkedList<>();
        PriorityQueue<Integer> pQueue = new PriorityQueue<>(Collections.reverseOrder());
        
        // 큐 초기화
        for (int i = 0; i < priorities.length; i++) {
            queue.add(new int[]{i, priorities[i]});
            pQueue.add(priorities[i]);
        }
        
        while (!queue.isEmpty()) {
            int[] top = queue.poll();
            // 우선순위가 제일 높은 값이면
            if (top[1] == pQueue.peek()) {
                pQueue.poll();  // 실행했으므로 제거
                answer++;  // 실행 순서 증가
                // 현재 인덱스가 목표 위치의 값이면 return
                if (top[0] == location) {
                    return answer;
                }
            } else {
                queue.add(top);  // 우선순위가 아니면 다시 add
            }
        }
        return answer;
    }
}