/**
* bridge_length : 다리에 올라갈 수 있는 트럭 수
* weight : 다리가 견딜 수 있는 무게
* truck_weights : 트럭 별 무게
*/
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> queue = new LinkedList<>();
int sum = 0; // 현재 다리를 건너는 트럭 무게의 합
int time = 0; // 모든 트럭이 다리를 건너는 최소의 시간
for(int i = 0; i < truck_weights.length; i++) { // 향상된 for문을 쓰는게 좋을 것
int truck = truck_weights[i];
while(true) {
// [1] 큐가 비어있는 경우 = 어떠한 트럭도 다리위에 없는 경우
if(queue.isEmpty()) {
queue.add(truck);
sum += truck;
time++; // 다리에 오를 때만 시간 추가
break;
} else if(queue.size() == bridge_length) { // [2] 큐가 가득찬 경우
sum -= queue.poll();
} else { // [3] 큐가 다리 길이만큼 가득 차지 않는 경우
// weight 값을 넘지 않는 선에서 새로운 트럭을 다리에 올려줌
if(sum + truck <= weight) {
queue.add(truck);
sum += truck;
time++;
break;
} else {
// weight 값을 넘는다면, 0을 넣어 이미 큐에 있는 트럭이 다리를 건너게 만듬
queue.add(0);
time++;
}
}
}
}
// 마지막 트럭에서 반복문이 끝나는데, 마지막 역시 다리 길이만큼 지나가야 하기 때문에, 다리 길이만큼 더해준다.
return time + bridge_length;
}
}
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 한다. => 큐를 사용한다.
큐를 다리라고 생각하고, 조건에 맞게 트럭을 큐에 넣고 빼면서 최소 몇 초가 걸리는 지 return 하면 되는 문제였다.
고려해야할 사항
다리에는 트럭이 최대 bridge_length대 올라갈 수 있고, 다리는 weight 이하까지의 무게를 견딜 수 있다.
다리에 완전히 오르지 않는 트럭의 무게는 무시한다 == 다리를 건너는 트럭의 무게만 측정한다 => 같은 의미.
트럭이 다리에 올라가면 1초가 시작되고, 다리 위에서 1칸씩 움직일 때마다 역시 1초가 흘러간다.
다리에 트럭을 넣는 조건은 총 3가지다.
[1] 큐가 비어있는 경우 -> 트럭을 다리에 올려준다 (시간은 +1 증가)
[2] 큐가 가득찬 경우 -> 이때는 가장 앞에 넣은 트럭이 다리의 끝에 도달했다는 의미이므로 poll() 메서드를 이용해 트럭을 꺼내 줌으로써, 다리를 건너가도록 한다. 이때 다리에서 내릴 때는 시간이 들지 않는다.
[3] 큐가 다리 길이만큼 가득 차지 않는 경우 -> 큐에 이미 있는 트럭에 다리를 지나갈 수 있도록 0 값을 넣어준다. (시간은 +1 증가)
이 과정을 전체 트럭의 개수만큼 반복한다.
위의 반복문의 특성상 마지막 트럭의 경우 다리에는 올랐지만 다 건너지는 못한다. 그래서 정답을 출력할 때는 지금까지 걸린 time에서 마지막 트럭이 건너는데 걸리는 시간인 다리의 길이를 더해서 출력하면 된다.
// 다리를 지나는 트럭(23.12.18) - 1차 복습
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int sum = 0; // 현재 다리를 지나는 트럭 무게의 합
int time = 0; // 모든 트럭이 다리를 건너는 최소 시간의 합(걸린 시간)
Queue<Integer> bridgeQueue = new LinkedList<>(); // 다리를 지나기 전 트럭
for(int truck : truck_weights) {
while(true) {
// 1. 큐가 비어있는 경우 트럭 추가
if(bridgeQueue.isEmpty()) {
bridgeQueue.offer(truck);
sum += truck;
time++; // 다리에 오를 때만 시간 추가
break;
}
// 2. 다리에 건너는 트럭 무게의 합 == 견딜 수 있는 최대무게(weight)
else if(bridgeQueue.size() == bridge_length) {
sum -= bridgeQueue.poll();
}
// 3. 큐가 비어있지 않은 경우
else {
// 2-2. (다음 트럭까지 포함하여) 다리에 건너는 트럭 무게의 합 > 견딜 수 있는 최대 무게
if(sum + truck > weight) {
bridgeQueue.offer(0);
time++;
}
// 2-3. (다음 트럭까지 포함하여) 다리에 건너는 트럭 무게의 합 < 견딜 수 있는 최대 무게
else {
bridgeQueue.offer(truck);
sum += truck;
time++;
break;
}
}
}
}
// 걸린 시간 + 마지막 트럭의 통과 시간
return time + bridge_length;
}
}
큐를 이용해서 문제를 풀어야 겠다는 생각은 가졌지만, 경우의 수를 생각하는 데 있어서 어려움이 있었다.
단순히 머리로만 생각하지말고, 뭔가 생각할 게 많다고 생각하면 그림을 그리면서 풀어가는 습관을 가지도록 하자.
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
for(int i = 0; i < answer.length; i++) {
for(int j = i + 1; j < answer.length; j++) {
answer[i]++;
if(prices[i] > prices[j]) break;
}
}
return answer;
}
}
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
Queue<Pair> queue = new LinkedList<>();
int answer = 0;
for(int i = 0; i < priorities.length; i++) {
queue.add(new Pair(i, priorities[i]));
}
while(!queue.isEmpty()) {
int current = queue.peek().value;
boolean flag = false;
for(Pair pair : queue) {
if(pair.value > current) {
flag = true;
break;
}
}
if (flag) { //우선순위가 높은게 있으면 뒤로 보낸다.
Pair temp = queue.poll();
queue.add(temp);
} else {
answer++;
Pair pair = queue.poll();
if(pair.index == location) {
return answer;
}
}
}
return answer;
}
class Pair {
int index;
int value;
public Pair(int index, int value) {
this.index = index;
this.value = value;
}
}
}
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
// 1. 큰 수가 우선순위를 갖는 우선순위 큐
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
int answer = 0;
//2. 우선순위 큐에 배열값 넣어주기
for (int i = 0; i < priorities.length; i++) {
pq.add(priorities[i]);
}
// 3. 큐의 값이 없어지기 전까지 반복
while (!pq.isEmpty()) {
for (int i = 0; i < priorities.length; i++) {
// 4.만약 큐의 가장 높은 숫자가 배열의 i번째 index값과 같다면
if (priorities[i] == pq.peek()) {
// 5.값과 위치가 모두 같다면 answer 리턴
if (i == location) {
answer++;
return answer;
}
// 6.값만 일치하는 경우 해당 문서 출력
pq.poll();
answer++;
}
}
}
return -1;
}
}
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
Queue<Pair> queue = new LinkedList<>();
for(int i = 0; i < priorities.length; i++) {
queue.add(new Pair(i, priorities[i]));
}
while(!queue.isEmpty()) {
int currnet = queue.peek().value;
boolean flag = false;
for(Pair pair : queue) {
if(pair.value > currnet) { // 현재 값보다 나머지 값이 우선순위가 더 높다면
flag = true;
break;
}
}
if(flag) {
Pair temp = queue.poll();
queue.add(temp);
} else {
// 현재 값이 나머지 값보다 우선순위가 더 높다면 answer++
answer++;
Pair pair = queue.poll();
if(pair.index == location) { // 현재 찾고자 하는 위치이면 출력
return answer;
}
}
}
return answer;
}
class Pair {
int index;
int value;
public Pair(int index, int value) {
this.index = index;
this.value = value;
}
}
}
1번은 그냥 큐로 구현한 것이고, 2번은 우선순위 큐로 구현한 것이다.
문제에 대한 설명을 읽고 직관적으로 큐를 사용해서 구현해야 했다.
큐에 남아있는 값들 중 방금 뽑은 값보다 더 높은 우선순위가 있으면 다시 큐에 넣는 식으로 했다.
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
Queue<Integer> q = new LinkedList<>();
List<Integer> answerList = new ArrayList<>();
for(int i = 0; i < speeds.length; i++) {
double remain = (100 - progresses[i]) / (double) speeds[i];
int date = (int) Math.ceil(remain); //Math.ceil: 올림
if(!q.isEmpty() && q.peek() < date) { //3 < 5
answerList.add(q.size());
q.clear();
}
q.offer(date);
}
answerList.add(q.size());
int[] answer = new int[answerList.size()];
for(int i = 0; i < answer.length; i++) {
answer[i] = answerList.get(i);
}
return answer;
}
}
import java.util.*;
class Solution {
public String[] solution(String[] record) {
Map<String, String> idMap = new HashMap<>(); // (아이디 - 닉네임) Map
int count = 0; // Change할 때마다 +1 증가
for(int i = 0; i < record.length; i++) {
String [] info = record[i].split(" ");
if(info[0].equals("Leave")) {
continue;
} else if(info[0].equals("Enter")) {
idMap.put(info[1], info[2]);
} else {
idMap.put(info[1], info[2]);
count++;
}
}
String[] answer = new String[record.length - count];
int idx = 0;
for(int i = 0; i < record.length; i++) {
String [] info = record[i].split(" ");
String nickname = idMap.get(info[1]);
if(info[0].equals("Enter")) {
answer[idx++] = nickname + "님이 들어왔습니다.";
} else if(info[0].equals("Leave")) {
answer[idx++] = nickname + "님이 나갔습니다.";
}
}
return answer;
}
}
idMap이라는 변수에 저장하고, 닉네임을 변경할 때마다 메시지에서 제외할 count를 증가하는 메서드를 구현한다.Map<String, String> idMap = new HashMap<>(); // (아이디 - 닉네임) Map
int count = 0; // Change할 때마다 +1 증가
for(int i = 0; i < record.length; i++) {
String [] info = record[i].split(" ");
if(info[0].equals("Leave")) {
continue;
} else if(info[0].equals("Enter")) {
idMap.put(info[1], info[2]);
} else {
idMap.put(info[1], info[2]);
count++;
}
}
닉네임에 대한 탐색을 마치고 나서 return하기 위해 메시지에 담을 배열인 answer 선언한다.
여기서 닉네임 변경한 것에 대해 채팅방 메시지에 표시되지 않으므로 메시지에서 제외할 count 만큼의 크기로 초기화한다.
배열의 인덱스를 지정할 변수 idx도 선언한다.
String[] answer = new String[record.length - count];
int idx = 0;
각 값을 공백을 기준으로 split하고, 들어오고 나가는 경우에 대해서만 메시지를 작성하여 저장한다.
닉네임은 아이디를 key를 이용하여 idMap에서 value를 가져와서 사용한다.
for(int i = 0; i < record.length; i++) {
String [] info = record[i].split(" ");
String nickname = idMap.get(info[1]);
if(info[0].equals("Enter")) {
answer[idx++] = nickname + "님이 들어왔습니다.";
} else if(info[0].equals("Leave")) {
answer[idx++] = nickname + "님이 나갔습니다.";
}
}
HashMap의 개념과 문제를 제대로 이해한다면 충분히 풀 수 있는 문제였다.
해당 문제를 풀면서, HashMap의 개념을 제대로 깊이 이해할 필요가 생겼다는 계기가 되었다.