- 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1]을 return 합니다. arr = [4, 4, 4, 3, 3] 이면 [4, 3]을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
💡 제한사항
- 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
1. Stack의 값이 존재하지 않는 경우 (Stack.isEmpty())는 처음 배열의 요소 값을 넣습니다.
2. Stack의 값이 추가되어서 이를 통해 다음 배열의 요소와 비교하여 같으면 넣지 않고, 같지 않는 경우 Stack에 추가합니다.
3. 최종적으로 Stack에서 후입선출(FIFO)에 의해 마지막 값이 먼저 출력이 되어 배열을 역순으로 순회하며 요소 값을 채워 넣습니다.
/**
* 1. STACK - 같은 수는 싫어
*
* @return ResponseEntity<ApiResponse>
* @link https://school.programmers.co.kr/learn/courses/30/lessons/12906
* @since 2023.05.13
*/
@GetMapping("/stack1")
public ResponseEntity<ApiResponse<Object>> questionStack1() {
int[] answer;
int[] arr = {1, 1, 3, 3, 0, 1, 1};
// int[] arr = {4,4,4,3,3}; //[4,3]
Stack<Integer> stack = new Stack<>();
// [CASE1] 스택 내의 값이 존재하지 않으면 요소를 채워넣고 존재하면 스텍의 peek()로 가장 위에 값을 가져와 비교합니다.
for (int arrItem : arr) {
if (stack.isEmpty()) stack.push(arrItem);
else if (stack.peek() != arrItem) stack.push(arrItem);
}
answer = new int[stack.size()];
// [CASE2] Stack to Array : 배열을 역순으로 순회하면서 스텍의 pop()을 이용하여 마지막 값을 넣습니다.
for (int i = answer.length - 1; i >= 0; i--) {
answer[i] = stack.pop();
}
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
2. 문제 : 올바른 괄호
💡 문제 설명
- 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()"는 올바른 괄호입니다.")()(" 또는 "(()("는 올바르지 않은 괄호입니다.'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
💡 제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
💡 해당 방법에서는 Stack을 이용하여서 “좌측 괄호” 일 경우 Stack에 넣어두고 우측 괄호가 나오면 Stack에 저장되어 있는 좌측 괄호 값을 빼는 형태로 짝을 찾아가는 형태로 구성합니다.
1. 문자열을 문자 배열로 구성하여 반복문을 순회합니다.
2. 순회하면서 좌측 괄호인 경우는 Stack에 넣어둡니다.
3. 순회하면서 우측 괄호인 경우 Stack에서 값을 뺍니다.( * Stack 값이 비었을 경우 false를 리턴합니다 : 짝이 맞지 않는 경우 )
4. 순회가 끝나고 Stack에 값이 존재하지 않으면 false를 리턴합니다.
/**
* 2. 올바른 괄호
*
* @return ResponseEntity<ApiResponse>
* @link https://school.programmers.co.kr/learn/courses/30/lessons/12909
* @since 2023.05.13
*/
@GetMapping("/stack2")
public ResponseEntity<ApiResponse<Object>> questionStack2() {
boolean answer = true;
String s = "()()";
// String s = "(())()";
// String s = "(()(";
Stack<Character> stack = new Stack<>();
// [STEP1] 문자를 순회합니다.
for (char iItem : s.toCharArray()) {
// [CASE1] 요소 값이 좌측 괄호인 경우 Stack에 넣어둡니다.
if (iItem == '(') stack.push(iItem);
// [CASE2] 요소 값이 우측 괄호인 경우 Stack에 값이 있는 경우 뺍니다.(좌측 괄호 값을 뺍니다)
else {
if (stack.isEmpty()) answer = false;
else stack.pop();
}
}
// [STEP2] Stack의 값이 비어있지 않은 상태(짝이 이루어지지 않은 상태)라면 false로 리턴합니다.
if (!stack.isEmpty()) answer = false;
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
3. 문제 : 괄호 회전하기
💡 문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
(), [], {}는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, []가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다. 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {}와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해 주세요.
💡 해당 문제에서는 '주식의 가격이 떨어진 초'에 대해서 값을 구하기 위해 하나의 요소와 나머지 요소들을 비교하는 기능을 구현하는 것이 초점이 됩니다.
1. 스택 객체를 생성합니다.
2. 주식 가격을 순회하면서 가격이 '떨어진 초'에 대한 값을 구합니다.
3. Stack의 값이 비어져 있지 않고 현재 값과 비교하여 이후 값이 더 큰 경우를 찾습니다 : 답을 계산하여 배열에 누적합니다 * 해당 경우는 가격이 떨어진 초에 대해서 찾기 위함입니다. 4. 배열의 누적으로 위해 Stack에 index 값을 추가합니다.
5. 위에 과정에서 값을 구하지 못한 경우 : 가격이 모두 비교하였을 때 떨어지지 않은 경우: 해당 값을 계산합니다.
/**
* 7. [스택] 주식 가격
*
* @return ResponseEntity<ApiResponse>
* @link <a href="https://school.programmers.co.kr/learn/courses/30/lessons/42584">...</a>
* @since 2023.07.14
*/
@GetMapping("/stack3")
public ResponseEntity<ApiResponse<Object>> question07() {
int[] prices = new int[]{1, 2, 3, 2, 3};
int[] answer = new int[prices.length];
// [STEP1] 스택 객체를 생성합니다.
Stack<Integer> stack = new Stack<>();
// [STEP2] 주식 가격을 순회하면서 가격이 떨어진 '초'에 대한 값을 찾습니다.
for (int i = 0; i < prices.length; i++) {
// [STEP3] Stack 비어져 있지 않고, 현재 값과 비교하여 이후 값이 더 큰 경우 : 답을 계산하여 결과 배열에 누적합니다.
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
answer[stack.peek()] = i - stack.peek(); // 답이 구해집니다.
stack.pop(); // Stack에 최상위에 있는 값을 뺍니다.
}
// [STEP4] Stack에는 index를 추가하여 증감합니다.
stack.push(i);
}
// [STEP5] 값을 구하지 못한 경우 : 가격이 끝까지 떨어지지 않은 경우
while (!stack.isEmpty()) {
answer[stack.peek()] = prices.length - stack.peek() - 1;
stack.pop();
}
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
2) 큐(Queue), 우선순위 큐(Priority Queue)
💡 큐(Queue)
- 선입선출(FIFO, First-In-First-Out) 방식을 따르는 자료구조로 먼저 저장된 데이터가 먼저 꺼내지는 형태입니다.
- 큐를 구현하기 위해 java.util 패키지에서 제공하는 Queue 인터페이스를 사용할 수 있습니다.
💡우선순위 큐(Priority Queue)
- 큐(Queue) 데이터 구조를 기반으로 데이터를 ‘일렬로 늘어놓은 다음’ 그중에서 ‘가장 우선순위가 높은 데이터'를 '가장 먼저 꺼내오는 방식’으로 동작하는 클래스를 의미합니다.
- Queue 인터페이스를 상속받기 때문에 Queue 인터페이스에서 정의된 메서드들도 사용할 수 있습니다.
메서드
설명
offer(E e)
큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 false를 반환합니다.
add()
큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 IllegalStateException 예외를 발생시킵니다.
poll()
큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
peek()
큐의 맨 앞에서 요소를 반환합니다. 큐가 비어 있으면 null을 반환합니다.
clear()
큐의 모든 요소를 제거합니다.
💡 [참고] Queue 클래스의 API 문서, Priority Queue API 문서에 대해서 궁금하시면 아래의 글을 참고하시면 도움이 됩니다.
- "명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.
- 이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.
- 명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return 하는 solution 함수를 완성해 주세요.
💡 제한 사항
- 3 ≤ k ≤ 100 - 7 ≤ score의 길이 ≤ 1,000 - 0 ≤ score [i] ≤ 2,000
💡 해당 방법은 PriorityQueue를 활용하여서 우선순위에 따라 데이터를 반환해 주는 처리를 수행합니다
1. 데이터 처리를 수행하려는 배열을 순회합니다
2. 우선순위 큐에 값을 넣습니다. : pg.add(socre [j]) (* 우선순위(값)에 따라 정렬이 됩니다)
3. k 값이 3보다 작은 경우 맨 앞의 요소를 결과값으로 반환합니다.(제거 X) : pg.peek()
4. k 값이 3보다 큰 경우에는 배열에 값을 넣고, 배열 안에서 제일 작은 값을 제거합니다 : pg.poll()
5. 배열의 작은 값을 반환합니다. pg:peek()
6. 해당 작업들을 통해서 최종적으로 배열을 구성합니다.
/**
* 1. Queue - 명예의 전당(1)
*
* @return ResponseEntity<ApiResponse>
* @link
* @since 2023.05.29
*/
@GetMapping("/queue1")
public ResponseEntity<ApiResponse<Object>> question46() {
int k = 3;
int[] score = {10, 100, 20, 150, 1, 100, 200};
int[] answer = new int[score.length];
PriorityQueue<Integer> pq = new PriorityQueue<>();
// [STEP1] 배열을 순회합니다.
for (int i = 0; i < score.length; i++) {
// [STEP2] 우선순위 큐 내의 값을 넣습니다.
pq.add(score[i]);
// [STEP3] 우선순위 큐의 사이즈가 k보다 클 경우에만 제일 작은 값을 '제거'합니다.
if (pq.size() > k) {
pq.poll();
}
// [STEP4] 우선순위 큐에서 제일 작은 값을 '반홥'합니다
answer[i] = pq.peek();
}
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
2. 문제: 기능 개발
💡 문제 설명
- 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100% 일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
💡 제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자연수입니다. 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
💡 해당 방법에서는 Queue를 이용하여서 큐의 요소 값을 채워 넣은 뒤에 필요에 따라 요소를 빼고 비교를 위해서 사용하는 형태로 구성합니다.
1. 사이즈가 동일하여 하나의 반복문에서 두 개를 수행합니다.
2. 최대 완료 값에서 진행 상태를 빼고 걸리는 시간을 나눕니다.(나머지는 버립니다)
3. 요소 별로 계산된 값을 큐에 더합니다.
4. 누적된 값을 기반으로 큐가 비워질 때까지 수행합니다.
5. 큐의 값(가장 먼저 들어온 값)을 빼고 임시 값에 저장합니다.
6. 큐가 비워져 있지 않고 가장 먼저 들어온 값이 다음 들어온 값 보다 큰 경우 루프를 종료합니다.
7. 현재 큐의 가장 먼저 들어온 값을 빼고 Counting을 합니다.
8. 최종 카운트 된 값을 리스트에 넣습니다. : 사이즈를 정하지 않아도 되므로 가변 배열을 이용하였습니다.
9. List to Array 반환
10. answer 배열을 구성합니다.
/**
* 2. Queue - 기능 개발
*
* @return ResponseEntity
* @link <https://school.programmers.co.kr/learn/courses/30/lessons/42586>
* @since 2023.05.13
*/
@GetMapping("/queue2")
public ResponseEntity<ApiResponse<Object>> question09() {
List<Integer> answerList = new ArrayList<>();
int[] progresses = new int[]{93, 30, 55};
int[] speeds = new int[]{1, 30, 5};
Queue<Integer> queue = new LinkedList<>();
// [STEP1] 사이즈가 동일하여 하나의 반복문에서 두개를 수행합니다.
for (int i = 0; i < progresses.length; i++) {
// [STEP2] 최대 완료 값에서 진행 상태를 빼고 걸리는 시간을 나눕니다.(나머지는 버립니다)
int result = (int) Math.ceil((100 - progresses[i]) / (double) speeds[i]);
// [STEP3] 요소 벌료 계산된 값을 큐에 더합니다.
queue.add(result);
}
System.out.println("queue : " + queue); // [7, 3, 9]
int temp = 0; // 임시로 넣을 값
int count = 0; // 배포 시 기능 개발 count
// [STEP4] 누적된 값을 기반으로 큐가 비워질때까지 수행합니다.
while (!queue.isEmpty()) {
// [STEP5] 큐의 값(가장 먼저 들어온 값)을 빼고 임시 값에 저장합니다.
temp = queue.poll();
count = 1;
// [STEP6] 큐가 비워져 있지 않고 가장 먼저 들어온 값이 다음 들어온 값 보다 큰 경우 루프를 종료합니다.
while (!queue.isEmpty() && (temp >= queue.peek())) {
// [STEP7] 현재 큐의 가장 먼저 들어온 값을 빼고 Counting을 합니다.
queue.poll();
count++;
}
// [STEP8] 최종 카운트 된 값을 리스트에 넣습니다. : 사이즈를 정하지 않아도 되므로 가변 배열을 이용하였습니다.
answerList.add(count);
}
// [STEP9] List to Array 반환
int answer[] = new int[answerList.size()];
if (answerList.size() == 0) answer = new int[]{};
// [STEP10] answer 배열을 구성합니다.
for (int i = 0; i < answerList.size(); i++) {
answer[i] = answerList.get(i);
}
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
3. 문제 : 프로세스
💡 문제 설명
- 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다. 실행 대기 큐(Queue)에서 대기 중인 프로세스 하나를 꺼냅니다. 큐에 대기 중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다. 예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다. 현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고 싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해 주세요. 💡 제한사항
- priorities의 길이는 1 이상 100 이하입니다. priorities의 원소는 1 이상 9 이하의 정수입니다. priorities의 원소는 우선순위를 나타내며 숫자가 클수록 우선순위가 높습니다. location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다. priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다. 💡 출처
💡 해당 방법에서는 PriorityQueue를 이용하여서 구성하고 큐의 우선순위 값을 찾아서 우선순위 이후 큐를 비워가면서 결과값을 얻어내는 방법입니다.
1. 우선순위 큐를 생성하고 값을 넣습니다. 2. 우선순위 큐가 비워질 때까지 반복합니다. 큐를 순회합니다(* 해당 순회를 하면 기존의 배열의 값들을 순차적으로 반환합니다) 3. 순차적인 배열과 우선순위 큐의 가장 높은 경우(pg.peek)를 찾아서 비교합니다. 4. 우선순위 큐에서는 최상위 값( 가장 높은 우선순위 인경우)을 제거합니다. 5. 큐와 위치가 같으면 큐를 초기화하고 멈춥니다.
/**
* 3. Queue - 프로세스
*
* @return ResponseEntity<ApiResponse>
* @link https://school.programmers.co.kr/learn/courses/30/lessons/42587
* @since 2023.05.
*/
@GetMapping("/queue3")
public ResponseEntity<ApiResponse<Object>> questionQueue2() {
int answer = 0;
Queue<Integer> queue = new LinkedList<>();
int[] priorities = {2, 1, 3, 2};
int location = 2;
// int[] priorities = {1, 1, 9, 1, 1, 1};
// int location = 0;
// [STEP1] 우선순위 큐를 생성하고 값을 넣습니다.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int priority : priorities) {
pq.offer(priority);
}
// [CASE2] 우선순위 큐가 비워질때까지 반복됩니다.
while (!pq.isEmpty()) {
// [STEP3] 구성한 큐를 순회합니다.
for (int i = 0; i < priorities.length; i++) {
// [STEP4] 큐의 요소 값과 큐의 최상위 값(pg.peek)인 우선순위가 높은 요소인 경우를 비교합니다.
if (priorities[i] == pq.peek()) {
// [STEP5] 우선순위 큐에서는 최상위 값을 제거합니다.
pq.poll();
answer++;
// [STEP6] 큐와 위치가 같으면 큐를 초기화하고 멈춥니다.
if (i == location) {
pq.clear();
break;
}
}
}
}
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
4. 문제 : 다리를 지나는 트럭
💡 문제 설명
- 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
- 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
<아래 표 참고>
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
- solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
💡 제한 조건
- bridge_length는 1 이상 10,000 이하입니다. - weight는 1 이상 10,000 이하입니다. - truck_weights의 길이는 1 이상 10,000 이하입니다. - 모든 트럭의 무게는 1 이상 weight 이하입니다.
💡 해당 문제 풀이의 요점은 Queue가 비어져 있는 경우, Queue가 가득찬 경우, Queue가 가득차지 않은 경우의 3가지 경우를 기반으로 수행이 됩니다.
1. Queue를 선언합니다.
2. 트럭을 순회합니다
3. 하나의 트럭 별 Queue, sum, time에 누적합니다.
[CASE1] Queue 비어져 있는 경우 : 최초 들어온 경우 큐에 트럭을 넣고 트럭에 무게를 합하고 지나간 시간을 올립니다.
[CASE2] Queue 가 가득찬 경우 : 큐의 맨앞의 요소를 제거합니다.(다리에 도착한 요소가 다리를 내림)
[CASE3] Queue 가득차지 않은 경우 : 현재 트럭의 용량을 비교하여 혼자 지나갈지 같이 지나갈지 정한다.
3.1. 트럭의 최대 용량이 넘지 않은 경우 : A 트럭 + B 트럭의 최대용량을 넘지 않는 경우(함께 지나간다)
3.2. 트럭의 최대 용량이 넘는 경우 : 큐에 0의 값을 넣고 트럭이 다리를 지나가게 한다.
4. 마지막 트럭이 지나는 시간을 계산합니다.
/**
* 4. Queue - 다리를 지나는 트럭
*
* @return ResponseEntity<ApiResponse>
* @link https://school.programmers.co.kr/learn/courses/30/lessons/42583
* @since 2023.07.16
*/
@GetMapping("/queue4")
public ResponseEntity<ApiResponse<Object>> question08() {
int bridge_length = 2;
int weight = 10;
int[] truck_weights = new int[]{7, 4, 5, 6};
int answer = 0;
// [STEP1] Queue를 선언합니다.
Queue<Integer> queue = new LinkedList<>();
int sum = 0; // 트럭이 들어오고 나가는 중에 최대 무게
int time = 0; // 트럭이 지나가는데 경과 시간
// [STEP2] 트럭을 순회합니다
for (int i = 0; i < truck_weights.length; i++) {
int truck = truck_weights[i];
// [STEP3] 하나의 트럭 별 Queue, sum, time에 누적합니다.
while (true) {
// [CASE1] Queue 비어져 있는 경우 : 최초 들어온 경우 큐에 트럭을 넣고 트럭에 무게를 합하고 지나간 시간을 올립니다.
if (queue.isEmpty()) {
queue.add(truck);
sum += truck;
time++;
break;
}
// [CASE2] Queue 가 가득찬 경우 : 큐의 맨앞의 요소를 제거합니다.(다리에 도착한 요소가 다리를 내림)
else if (queue.size() == bridge_length) {
sum -= queue.poll();
}
// [CASE3] Queue 가득차지 않은 경우 : 현재 트럭의 용량을 비교하여 혼자 지나갈지 같이 지나갈지 정한다.
else {
// [CASE3-1] 트럭의 최대 용량이 넘지 않은 경우 : A 트럭 + B 트럭의 최대용량을 넘지 않는 경우(함께 지나간다)
if (sum + truck <= weight) {
queue.add(truck);
sum += truck;
time++;
break;
}
// [CASE3-2] 트럭의 최대 용량이 넘는 경우 : 큐에 0의 값을 넣고 트럭이 다리를 지나가게 한다.
else {
queue.add(0);
time++;
}
}
}
}
//[STEP4] 마지막 트럭이 지나는 시간
answer = time + bridge_length;
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
