코딩 테스트 합격자 되기 - 스택 & 큐

스터디 : 코딩테스트 합격자 되기 - 2주 차 
강의 출처 : 인프런 코딩 테스트 합격자 되기 - 스택과 큐

 

ADT(Abstract Data Type)

추상 데이터 타입이란 내부에 복잡한 구현과 자료구조를 간단한 연산으로 명시한다.

 

---

 

스택

스택은 LIFO(Last In First Out) 후입선출 구조로 되어있다. 스택에 push 연산으로 자료를 넣고 pop 연산으로 자료를 꺼낼 때 가장 나중에 넣은 자료 순으로 꺼낼 수 있다.

 

스택의 ADT

구분	정의	설명
연산	boolean isFull()	스택에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean값을 반환한다.
	boolean isEmpty()	스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환한다.
	void push(itemmType item)	스택에 데이터를 넣는다.
	item Type pop	스택에 최근에 push한 데이터를 꺼내서 반환한다.
상태	int top	스택에 최근에 push한 데이터 위치를 기록한다.
	item Type data(maxsize)	스택의 데이터를 관리하는 배열이다. 최대 maxsize 데이터를 관리한다.

 

스택의 사용예시

함수 호출

함수 호출 시, 현재 함수의 실행 상태를 저장, 새로운 함수로 제어 이동

void A() {
	printf("start A\n")
    B() 
    printf("end A\n") 
}

void B() {
	printf("start B\n") 
    printf("end b\n") 
}

int main() { 
	A() 
    return 0 
}

 

스택에 push 되는 순서 : main() -> A() -> B()

스택에 pop 되는 순서 : B() -> A() -> main()

 

이전 페이지로 가기

페이지를 이동할 때 스택에 push, 이전 페이지로 갈 때 pop

페이지 A

페이지 B

페이지 C

뒤로가기

뒤로가기

		C	C (pop)
	B	B	B	B
A	A	A	A	A

 

 

괄호 짝 맞추기

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

 

{

}

(

{

}

)

 

1. 여는 괄호 push

2. 닫흰 괄호가 나오면 pop을 하고, 괄호 짝이 맞는지 확인

  2-1. 맞는 괄호가 아닐 경우 exit

  2-2. 맞는 괄호면 계속 진행

3. 문자열 끝까지 수행 후 스택에 남아있는게 없으면 success, 있으면 fall

 

{

}

(

{

}

)

			{ (push)	{ (pop)
{ (push)	{ (pop)	( (push)	(	(	( (pop)

 

---

큐

큐는 FIFO(First In First Out) 선입선출 구조로 되어있다. 큐에 push 연산으로 자료를 넣고 pop 연산으로 자료를 꺼낼 때 가장 먼저 들어간 자료순으로 꺼낼 수 있다.

 

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환한다.
	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다.
	void push(itemType item)	큐에 데이터를 push 한다.
	itemType pop()	큐에서 처음 push한 데이터를 pop한 뒤 반환한다.
상태	int front	큐에서 가장 마지막에 pop한 위치를 기록한다.
	int rear	큐에서 최근에 push한 데이터 위치를 기록한다.
	itemType data(maxsize)	큐의 데이터를 관리하는 배열이다. 최대 maxsize개의 데이터를 관리한다.

 

큐의 사용예시

줄 서기

한 명씩 줄을 설 때, rear은 가장 최근에 줄을 선 위치고, front는 가장 먼저 줄을 선 위치이다.

 

				A(front)
		->	B(rear)	A(front)
	->	C(rear)	B	A(front)
->	D(rear)	C	B	A(front)
E(rear)	D	C	B	A(front)

 

 

pop을 할 경우 front부터 차례대로 삭제된다.

 

E	D	C	B	A(front) -> pop
	E	D	C	B(front) -> pop
		E	D	C(front) -> pop
			E	D(front) -> pop
				E(front) -> pop

 

요세푸스 문제

1. N명의 사람들이 원형으로 둘러 앉고, 각 사람들 번호를 1~N으로 매김

2. 시작 위치부터 K번째 사람 제거

3. 제거한 위치부터 다시 K번째 사람 제거

4. 3번 과정을 한명이 남을 때까지 반복

 

N = 5, K = 2

5

4

3

2

1

 

K번째 사람이 아닐 경우 pop 한 뒤 다시 push 해준다.

 

1

5

4

3

 

요소가 하나도 남지 않을 때까지 반복한다.

 

---

 

스택, 큐 문제 풀기

괄호 회전하기

function solution(s) {
    let answer = 0;
    let stack = [];
    let isCorrect = true;
    
    for(let i = 0; i < s.length; i++) {
        let arr = s.slice(i) + s.slice(0 , i)
        isCorrect = true
        if(s.length % 2 === 1) return 0
        
        for(str of arr) {
            if(str === '{' || str === '[' || str === '(') {
                stack.push(str)
            } else {
                let top = stack.pop()
                if(top === '(' && str === ')') continue;
                if(top === '{' && str === '}') continue;
                if(top === '[' && str === ']') continue;
                isCorrect = false
                break;
            }
        }
        if (isCorrect) answer++;
    }
    return answer;
}

 

주식 가격

function solution(prices) {
    var answer = [];
    
    for(let i = 0; i < prices.length; i++) {
        let stack = 0;
        
        for(let j = i + 1; j < prices.length; j++) {
            stack++
            if(prices[i] > prices[j]) {
                break;
            }
        }
        answer.push(stack)
    }
    return answer;
}

 

영어 끝말잊기

function solution(n, words) {
    let stack = []
    
    for(let i = 0; i < words.length; i++) {
        let play = Math.ceil(( i + 1) / n)
        let player = (( i + 1 ) % n === 0 ? n : ( i + 1) % n)

        if(stack.includes(words[i])) {
            return [player, play]
        }
        
        if(stack.length && stack[stack.length - 1].slice(-1) !== words[i].slice(0,1)) {
            return [player, play]
        }
        stack.push(words[i]);
    }

    return [0,0]
}