Stack
1.stack이란?
- 데이터(data)를 순서대로 쌓는 자료구조
- LIFO(last In, First Out)
- 스택은 아래의 두가지 연산을 가진 요소들의 집합인 추상 자료형
- js에서는 배열의 push,pop,splice 등 을 이용해 구현할 수 있다.
2. stack을 이용해보았던 문제들
1.브라우저 뒤로 가기 앞으로 가기
조건
- 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
- 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
- 앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.
- 브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않습니다.
입력
- 인자 1: actions
String과 Number 타입을 요소로 갖는 브라우저에서 행동한 순서를 차례대로 나열한 배열- 인자 2: start
String 타입의 시작 페이지를 나타내는 현재 접속해 있는 대문자 알파벳출력
- Array 타입을 리턴해야 합니다.
주의사항
- 만약 start의 인자로 string 자료형이 아닌 다른 자료형이 들어온다면 false를 리턴합니다.
- 새로운 페이지 접속은 알파벳 대문자로 표기합니다.
- 뒤로 가기 버튼을 누른 행동은 -1로 표기합니다.
- 앞으로 가기 버튼을 누른 행동은 1로 표기합니다.
- 다음 방문할 페이지는 항상 현재 페이지와 다른 페이지로 접속합니다.
- 방문한 페이지의 개수는 100개 이하입니다.
- 반환되는 출력값 배열의 첫 번째 요소 prev 스택, 세 번째 요소 next 스택은 배열입니다. 스택을 사용자 정의한다면 출력에서는 배열로 변환해야 합니다.
입출력 예시
const actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1]; const start = "A"; const output = browserStack(actions, start); console.log(output); // [["A"], "B", ["A", "D"]] const actions2 = ["B", -1, "B", "A", "C", -1, -1, "D", -1, 1, "E", -1, -1, 1]; const start2 = "A"; const output2 = browserStack(actions2, start2); console.log(output2); // [["A", "B"], "D", ["E"]]내 풀이
function browserStack(actions, start) { // TODO: 여기에 코드를 작성합니다. if(typeof start!=='string') return false let prev = []; //stack let next = [];//stack let nowPage = start; for (let i = 0; i < actions.length; i++) { if(prev.length===0&&actions[i]===-1){ //prev가 빈경우 continue } if(next.length===0&&actions[i]===1){//next가 빈경우 continue } if(typeof actions[i]==='string'){//새로운 페이지인경우 prev.push(nowPage); nowPage= actions[i] next =[]; } if(actions[i]===-1){//뒤로가기인 경우 next.push(nowPage); nowPage=prev.pop() } if(actions[i]===1){//앞으로가기인 경우 prev.push(nowPage); nowPage =next.pop() } } return [prev,nowPage,next]//제출 }
2.Queue
1.Queue란?
- 자료구조 Queue는 Stack과 반대되는 개념으로
- FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있다
- js에서 배열의 unshift와 push,splice등 을 이용해 구현할 수 있다
2. Queue를 이용해보았던 문제들
1.박스포장
문제
- 마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.
- 불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.
- 뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.
- 만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.
- 이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.
입력
- 인자 1 : boxes
- Number 타입을 요소로 갖는, 포장해야 하는 박스가 담긴 배열
1 ≤ 사람 수 ≤ 10,000
1 ≤ 박스 ≤ 10,000출력
- Number 타입을 리턴해야 합니다.
주의 사항
- 먼저 포장을 전부 끝낸 사람이 있더라도, 앞사람이 포장을 끝내지 않았다면 나갈 수 없습니다.
예시
- 만약 5, 1, 4, 6이라는 배열이 왔을 때, 5개의 박스를 포장하는 동안 1, 4 개의 박스는 포장을 끝내고 기다리게 되고, 6 개의 박스는 포장이 진행 중이기 때문에, 5, 1, 4 세 개가 같이 나가고, 6이 따로 나가게 됩니다. 그렇기에 최대 3 명이 같이 나가게 됩니다.
const boxes = [5, 1, 4, 6]; const output = paveBox(boxes); console.log(output); // 3 const boxes2 = [1, 5, 7, 9]; const output2 = paveBox(boxes); console.log(output2); // 1나의 풀이
function paveBox(boxes) { //몇명이 나가는지 값들 저장하기 let result =[] //몇명인지 세는 함수 만들기 function howManypeople(boxes){ let howManypeople = 0 for(let el of boxes){ if(boxes[0]>=el){ howManypeople += 1 }else{ break } } return howManypeople } //박스의 선입 선출 조정 for(;boxes.length>0;){ result.push(howManypeople(boxes)); boxes.splice(0,howManypeople(boxes)); } // 최대값 리턴 return Math.max(...result) }2.프린터
문제
프린터의 인쇄 작업 목록의 크기와 최대 용량을 가정하고 각기 다른 용량의 문서를 차례대로 인쇄하여 모든 문서가 인쇄되는데 최소 몇 초가 걸리는지 테스트하기로 했습니다.
린터의 제한사항인 인쇄 작업 목록의 크기 bufferSize, 최대 용량 capacities가 주어집니다. 인쇄할 문서의 크기가 나열된 배열 documents가 모두 인쇄되는데 걸리는 최소 시간을 반환하는 솔루션을 만들어 주세요.
입력
- 인자1: bufferSize
- Number 타입의 인쇄 작업 목록 크기
- 인자 2: capacities
- Number 타입의 인쇄 작업 목록에 추가될 수 있는 최대 용량
- 인자 3: documents
- Number 타입을 요소로 갖는 문서 크기가 나열된 배열
출력- Number 타입을 리턴해야 합니다.
제한사항- 인쇄 작업 목록은 칸으로 이루어져 있습니다.
- 각 칸에는 한 개의 문서만 위치할 수 있습니다.
- 문서는 1초에 한 칸만 이동할 수 있습니다.
- 인쇄 작업 목록의 크기는 bufferSize이고 최대 용량 capacities 만큼 문서를 담을 수 있습니다.
주의사항- bufferSize는 1 이상 100 이하입니다.
- capacities는 100Kib 이하입니다.
- 인쇄할 문서의 개수(배열의 길이) 1이상 100 이하입니다.
- 문서 하나의 크기는 capacities를 초과하지 않습니다.
1초가 지나면 인쇄 작업 목록에는 7Kib 크기의 문서가 추가됩니다.
예시- 1초가 지나면 인쇄 작업 목록에는 7Kib 크기의 문서가 추가됩니다.
- 2초일 때 인쇄 작업 목록의 최대 용량이 10Kib이기 때문에 4Kib 문서는 작업 목록에 들어갈 수 없습니다. 동시에 7Kib 문서는 작업 목록에서 1칸 앞으로 이동합니다.
- 3초일 때 7Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 4Kib 문서는 인쇄 작업 목록에 추가됩니다.
- 4초일 때 4Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다. 동시에 5Kib 문서는 인쇄 작업 목록에 추가됩니다.
- 5초일 때 4Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 5Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다. 최대 용량 10Kib 제한으로 6Kib 문서는 인쇄 작업 목록으로 추가될 수 없습니다.
- 6초일 때 5Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 6Kib 문서가 인쇄 작업 목록에 추가됩니다.
- 7초일 때 6Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다.
- 8초일 때 6Kib 문서가 마지막으로 인쇄됩니다.
입출력 예시let bufferSize = 2; let capacities = 10; let documents = [7, 4, 5, 6]; let output = queuePrinter(bufferSize, capacities, documents); console.log(output) // 8나의 풀이
function queuePrinter(bufferSize, capacities, documents) { //업데이트변수 let count = 0; //worklist (queue) const worklist = new Array(bufferSize).fill(null); //worklist에 null만있는지 확인하는함수 function isallNull() { let allNull = true; for (let i = 0; i < worklist.length; i++) { if (worklist[i] !== null) { allNull = false } } return allNull } //재귀시킬함수 function replay(capacities, documents) { //재귀종료조건 if (isallNull() && documents.length === 0) return; //카운트 없데이트 count += 1; //현재 worklist의 용량 worklist.shift(); let nowWorklistCapacities = worklist.reduce((pre, cur) => pre + cur,0); //작업수행 if (nowWorklistCapacities + documents[0] <=capacities) { worklist.push(documents[0]); return replay(capacities, documents.slice(1)) } else { worklist.push(null); return replay(capacities, documents) } } replay(capacities, documents);//재귀함수 실행 return count//업데이트된 카운트 제출 }
