Stack, Queue 연습문제 - 브라우저, 박스 포장, 프린터
1. [Stack] 브라우저 뒤로 가기 앞으로 가기
문제
개발자가 되고 싶은 김코딩은 자료구조를 공부하고 있습니다. 인터넷 브라우저를 통해 스택에 대해 검색을 하면서 다양한 페이지에 접속하게 되었는데 "뒤로 가기", "앞으로 가기"를 반복하면서 여러 페이지를 참고하고 있었습니다.
그런데 새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었습니다. 이러기를 반복하다가 김코딩은 스택 자료구조를 떠올리게 되었습니다.
브라우저에서 "뒤로 가기", "앞으로 가기" 기능이 어떻게 구현되는지 궁금해진 김코딩은 몇 가지 조건을 아래와 같이 작성하였지만, 막상 코드를 작성하지 못하고 있습니다.
조건
- 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
- 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
- 앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.
- 브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않습니다.
인터넷 브라우저에서 행동한 순서가 들어있는 배열 actions와 시작 페이지 start가 주어질 때 마지막에 접속해 있는 페이지와 방문했던 페이지들이 담긴 스택을 반환하는 솔루션을 만들어 김코딩의 궁금증을 풀어주세요.
입력
인자 1: actions
- String 타입을 요소로 갖는 브라우저에서 행동한 순서를 차례대로 나열한 배열
인자 2: start
- String 타입의 시작 페이지를 나타내는 현재 접속해 있는 대문자 알파벳
출력
- Stack타입을 인자로 가지는 ArrayList 타입을 리턴해야 합니다.
주의사항
- 앞으로가기나 뒤로가기가 아닌 경우에 새로운 페이지로 취급을 한다
- 뒤로 가기 버튼을 누른 행동은 "-1"로 표기합니다.
- 앞으로 가기 버튼을 누른 행동은 "1"로 표기합니다.
- 다음 방문할 페이지는 항상 현재 페이지와 다른 페이지로 접속합니다.
- 방문한 페이지의 개수는 100개 이하입니다.
- 반환되는 출력값 ArrayList의 첫 번째 요소 prev 스택, 두번째 요소 current 스택, 세 번째 요소 next 스택을 사용해야 합니다.
풀이
String 배열을 순회시키며 값이 1/-1/알파벳인 경우로 나눠주었다.
코드
package com.codestates.coplit;
import java.util.*;
public class Solution {
public ArrayList<Stack> browserStack(String[] actions, String start) {
Stack<String> prevStack = new Stack<>();
Stack<String> nextStack = new Stack<>();
Stack<String> current = new Stack<>();
ArrayList<Stack> result = new ArrayList<>();
current.push(start);
for(String s : actions) {
if(s.equals("1")) {
if(!nextStack.isEmpty()) {
prevStack.push(current.pop());
current.push(nextStack.pop());
}
}
else if(s.equals("-1")) {
if(!prevStack.isEmpty()) {
nextStack.push(current.pop());
current.push(prevStack.pop());
}
}
else {
prevStack.push(current.pop());
current.push(s);
nextStack.clear();
}
}
result.add(prevStack);
result.add(current);
result.add(nextStack);
return result;
}
}
2. [Queue] 박스 포장
문제
마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.
불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.
뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.
만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.
이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.
입력
인자 1 : boxes
- int 타입을 요소로 갖는, 포장해야 하는 박스가 담긴 배열
- 1 ≤ 사람 수 ≤ 10,000
- 1 ≤ 박스 ≤ 10,000
출력
- int 타입을 리턴해야 합니다.
주의 사항
- 먼저 포장을 전부 끝낸 사람이 있더라도, 앞사람이 포장을 끝내지 않았다면 나갈 수 없습니다.
풀이
먼저 큐에 포장할 박스 수를 전부 담았다.
큐의 처음 요소를 start 변수에 넣어주고 그 뒤 값이 start보다 작은 경우 함께 나갈 수 있기 때문에 max++를 해준다.
만약 start보다 크다면 함께 나가지 못하기 때문에 지금까지 저장된 max 값을 ArrayList에 add한다.
큐가 비었을 때 ArrayList의 Max 값을 찾아 return한다.
코드
package com.codestates.coplit;
import java.util.*;
public class Solution {
public int paveBox(Integer[] boxes) {
Queue<Integer> qu = new LinkedList<>();
ArrayList<Integer> arr = new ArrayList<>(); //한번에 나가는 사람 수를 저장할 List
for(int i : boxes) {
qu.add(i);
}
int start = qu.poll(); //제일 앞에 있는 사람의 박스 수
int max = 1; //최대로 나갈 수 있는 사람 수
while(!qu.isEmpty()) {
if(qu.peek()<=start) {
qu.poll();
max++;
}
else {
arr.add(max);
start = qu.poll();
max = 1;
}
}
arr.add(max);
int result = arr.stream().mapToInt(i->i).max().getAsInt();
return result;
}
}
3. [Queue] 프린터
문제
김코딩은 최근 인쇄할 일이 많이 생겨 창고에서 안 쓰던 프린터를 꺼냈습니다. 이 프린터의 성능을 테스트하여 새로운 프린터를 장만할지 결정하려고 합니다. 김코딩은 프린터의 인쇄 작업 목록의 크기와 최대 용량을 가정하고 각기 다른 용량의 문서를 차례대로 인쇄하여 모든 문서가 인쇄되는데 최소 몇 초가 걸리는지 테스트하기로 했습니다. 프린터 인쇄 작업 목록의 제한사항은 다음과 같습니다.
[제한사항]
- 인쇄 작업 목록은 칸으로 이루어져 있습니다.
- 각 칸에는 한 개의 문서만 위치할 수 있습니다.
- 문서는 1초에 한 칸만 이동할 수 있습니다.
- 인쇄 작업 목록의 크기는 bufferSize이고 최대 용량 capacities 만큼 문서를 담을 수 있습니다.
만약, 인쇄 작업 목록의 크기가 2이고 최대 용량이 10Kib라면 크기가 [7, 4, 5, 6] Kib인 문서들이 최단 시간 안에 순서대로 모두 인쇄되는 과정은 다음과 같습니다.
- 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 문서가 마지막으로 인쇄됩니다.
위 예시에서와 같이 모든 문서가 출력되는데 걸리는 최소 시간은 8초가 걸립니다.
김코딩이 가지고 있는 프린터의 제한사항인 인쇄 작업 목록의 크기 bufferSize, 최대 용량 capacities가 주어집니다. 인쇄할 문서의 크기가 나열된 배열 documents가 모두 인쇄되는데 걸리는 최소 시간을 반환하는 솔루션을 만들어 주세요.
입력
인자1: bufferSize
- int 타입의 인쇄 작업 목록 크기
인자 2: capacities
- int 타입의 인쇄 작업 목록에 추가될 수 있는 최대 용량
인자 3: documents
- int 타입을 요소로 갖는 문서 크기가 나열된 배열
출력
- int 타입을 리턴해야 합니다.
주의사항
- bufferSize는 1 이상 100 이하입니다.
- capacities는 100Kib 이하입니다.
- 인쇄할 문서의 개수(배열의 길이) 1이상 100 이하입니다.
- 문서 하나의 크기는 capacities를 초과하지 않습니다.
풀이
계속 시간초과가 나서 Stream 대신 sum 변수를 추적하면서도 해봤고, 배열 복사 대신 currentindex변수로 값을 넣어주기도 했는데 도저히 해결이 되지 않았다.
다시 시작하는 마음으로 로직을 새로 짰더니 바로 해결 ,,, 머선 일이야 진쟈 ,,
아직도 두 코드의 차이를 잘 모르겠다 ,,,,
코드(시간 초과)
public class Solution {
public int queuePrinter(int bufferSize, int capacities, int[] documents) {
Queue<Integer> process = new LinkedList<>();
int time = 0;
for(int i=0; i<bufferSize; i++) {
process.add(0);
}
int sum = documents[0];
while(documents.length!=0||sum!=0) {
sum = process.stream().mapToInt(i->i).sum() + documents[0];
if(sum-process.peek()<=capacities) {
process.add(documents[0]);
process.poll();
}
else {
while(sum-process.peek()>=capacities) {
sum -= process.poll();
process.add(0);
time++;
}
process.poll();
process.add(documents[0]);
}
documents = Arrays.copyOfRange(documents,1,documents.length);
time++;
if(documents.length==0) {
while(!process.isEmpty()) {
process.poll();
time++;
}
break;
}
}
return time;
}
}
코드
public class Solution {
public int queuePrinter(int bufferSize, int capacities, int[] documents) {
Queue<Integer> process = new LinkedList<>();
int time = 0;
for(int i=0; i<bufferSize; i++) {
process.add(0);
}
while(documents.length!=0||process.stream().mapToInt(i->i).sum()!=0) {
if(documents.length!=0) {
int sum = process.stream().mapToInt(i->i).sum() + documents[0];
if(sum-process.peek()<=capacities) {
process.poll();
process.add(documents[0]);
time++;
documents = Arrays.copyOfRange(documents,1, documents.length);
}
else {
while(sum-process.peek()>capacities) {
sum -= process.poll();
process.add(0);
time++;
}
process.poll();
process.add(documents[0]);
time++;
documents = Arrays.copyOfRange(documents,1, documents.length);
}
}
else {
while(!process.isEmpty()) {
process.poll();
time++;
}
}
}
return time;
}
}