🍀TIL🍀[프로그래머스] Coding Test 스터디7

오늘은 자료 구조 중 스택과 큐 관련해서 공부하고 문제를 조금 풀어봤다!

스택(Stack)

• 스택은 후입선출(Last In First Out) 구조이다. (프링글스 같은..?)

• 즉, 자료구조 Stack의 특징은 입력과 출력이 하나의 방향, 즉 스택의 최상단에서만 이루어지며, 이를 제한적 접근이라고 한다.

• LIFO(Last In First Out) 혹은 FILO(First In Last Out)

• Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'

• 실생활에서는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 활용된다.

• 시간 복잡도

  • 삽입과 삭제 : O(1)
  • 탐색: O(n)

💟Stack 자료 구조의 장점

• 스택에 저장된 데이터를 가져오는 속도가 매우 빠르다

• 삽입과 삭제가 항상 스택의 맨 위에서 이루어지기 때문에 스택에서 데이터를 삽입하거나 삭제할 때, 다른 데이터의 위치를 변경할 필요가 없다!

  • 즉, 데이터를 삽입, 삭제하는데 모든 데이터를 순회할 필요가 없기 때문에 프로세스가 매우 빠르다.

💟Stack 자료 구조의 단점

• 당연하게도, 중간 요소의 접근이 제한된다

• 상단(top) 요소에만 직접적인 접근이 가능하며, 중간에 있는 요소에는 직접적인 접근이 불가능하다.

  • 즉, 중간 요소에 접근하려면 상단 요소를 계속 Pop하여 원하는 요소에 도달해야만 한다!

• 또한, 스택은 크기를 고정해서 사용하는 자료구조이므로 데이터 최대 개수를 미리 정해야 한다는 단점도 있다.

  • 스택의 크기를 초과하여 데이터를 저장하려고 하면
    "스택 오버플로우(Stack Overflow)"가 발생

큐(Queue)

큐(Queue)는 줄을 서서 기다리다, 대기열이라는 뜻

• 자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 특징으로 가지고 있다.

• 입력의 방향과 출력의 방향이 각각 고정되어 있으며, 데이터를 입력할 시에는 큐의 끝에서(rear), 데이터를 출력할 때는 큐의 맨 앞에서(front) 진행.

• Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고도 하며, 자료구조 Queue는 데이터(data)가 입력된 순서대로 처리할 때 주로 사용

• 각 처리 시마다 한 개의 데이터를 넣거나 뺄 수 있다. 즉, 큐에 한 개씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만을 뺄 수 있다,

• 선형 큐, 우선순위 큐, 원형 큐 세종류가 존재.

• BFS(Breadth First Search) 알고리즘에서 주로 사용

• 시간 복잡도는 스택과 동일하다!

• 큐랑 와일문은 짝꿍이다!

💟Queue 자료 구조의 장점

1. 데이터 처리나 작업 처리에서 순서가 중요한 경우에 유용

• 선입선출(First-In-First-Out, FIFO)의 특징 덕분에 처리해야 할 데이터나 작업을 순차적으로 처리할 수 있다.

• 큐의 가장 앞(front)에서는 가장 오래전에 삽입된 데이터가, 가장 뒤(rear)에는 가장 최근에 삽입된 데이터가 위치한다.
  즉, 데이터를 삽입하는 순서와 삭제하는 순서가 일치하게 유지!

• ex. 프린터에서 인쇄 요청이 들어온 순서대로 처리해야 하는 경우, 은행에서 대기 중인 고객 순서를 결정하는 경우, 채팅 시스템에서 메시지를 보내는 순서를 결정하는 경우

2. 다른 자료 구조에 비해 상대적으로 속도가 빠르다

• 큐의 삽입과 삭제는 각각 큐의 끝단에서 이루어지기 때문에, 중간에 위치한 데이터를 삭제할 수 없다.

• 큐에 데이터를 삽입할 때에는 큐의 끝단에서 새로운 데이터를 추가하는 것으로 끝나며, 데이터를 삭제할 때는 큐의 첫 번째 데이터를 삭제하는 것으로 끝난다.
  즉 큐에 요소를 삽입하거나 삭제할 시 단 한 번의 실행만으로 처리가능하다. (시간복잡도: O(1))

💟Queue 자료 구조의 단점

• 큐는 특정 위치의 데이터를 조회하거나 수정하는 상황에는 적합하지 않다.

• 큐는 다른 위치의 데이터에 직접 접근하여 데이터를 변경하는 연산이 불가능하며, 중간에 있는 데이터를 조회하는 것도 불가능하다.
  따라서 큐는 데이터를 순차적으로 처리하는 데 적합한 자료 구조이다.

스택과 큐의 공통점과 차이점

💟공통점

스택과 큐 모두 선형 자료구조로, 순차적으로 데이터를 저장하고 조작한다. 둘 다 데이터의 추가와 제거를 통해 동작하며, 데이터를 임시로 저장하는 데 사용되는 경우가 많다.

💟차이점

스택과 큐의 주요 차이점은 데이터의 추가와 제거 방식에서 나타난다. 스택에서는 데이터의 추가와 제거가 같은 곳에서 이루어지는 반면, 큐에서는 데이터의 추가가 한 쪽 끝에서, 제거가 반대 쪽 끝에서 이루어진다.

Q1. 올바른 괄호

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

🐣내 코드

function solution(s){
    const stack = [];
    
    if(s[0] === ')' || s[s.length-1] === '('){
        return false
    }
    
    s.split('').map((target) => {
        if(target === ')'){
            stack.pop()
        }
        else{
            stack.push(target)
        }
    })
    
    return stack.length === 0;
}

Q2. 기능개발

🐣내 코드

function solution(progresses, speeds) {
    let stack = [];
    let answer = [];
    
    for(let i = 0; i < progresses.length; i++){
        stack.push(Math.ceil((100 - progresses[i]) / speeds[i]))
    }

    let currentNum = stack[0]
    let complete = 0;   
    
    for(let i = 0; i < stack.length; i++){
        if(stack[i] <= currentNum){
            complete++;
        }else{
            answer.push(complete);
            complete = 1;
            currentNum = stack[i]
        }
    }
    
    answer.push(complete)
    
    return answer; 
}

그 외에 새로이 알게된 것 & 기억할 것

• 배열의 길이가 0이면 false이다. arr.length로 true, false 표현가능