택배상자

📑 문1) 영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

---

제한사항

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

---

입출력 예

order	result
[4,3,1,2,5]	2
[5,4,3,2,1]	5

---

나의 풀이

package programmers;

import java.util.Stack;

public class DeliveryBox {
	
	public static int solution(int[] order) {
		
		
		int idx = 0;
		Stack<Integer> stack = new Stack<>();
		
		for(int i = 0; i < order.length; i++) {
			stack.push(i+1);
			while(!stack.isEmpty()) {
				if(stack.peek() == order[idx]) {
					stack.pop();
					idx++;
				}else break;
			}
		}
		System.out.println(idx);
		return idx;
		
    }
	
	public static void main(String[] args) {
		int[] order = {1,3,5,7,9,2,4,6,8,10};
		solution(order);
	}

}

---

다리를 지나는 트럭

📑 문2) 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

---

입출력 예

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

---

나의 풀이

package programmers;

import java.util.LinkedList;
import java.util.Queue;

public class PassingOverTheBridge {
	
	public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> bridge = new LinkedList<>();
        
        for(int truck_weight : truck_weights) {
        	queue.add(truck_weight);
        }
        
        int currentWeightOnBridge = 0;
        
        for(int i = 0; i < bridge_length; i++) {
        	bridge.add(0);
        }
        
        
        
        while(!queue.isEmpty() || currentWeightOnBridge > 0) {
        	answer++;
        	
        	currentWeightOnBridge -= bridge.poll();
        	
        	if(!queue.isEmpty() && currentWeightOnBridge + queue.peek() <= weight) {
        		int nextTruckWeight = queue.poll();
        		bridge.add(nextTruckWeight);
        		currentWeightOnBridge += nextTruckWeight;
        		
        	}else {
        		bridge.add(0);
        	}
        	
        
        }
        
       	
        return answer;
    }
	
	
	public static void main(String[] args) {
		int[] truck_weights = {7,4,5,6};
		solution(2, 10, truck_weights);
	}

}

---

나의 생각

문제를 이해하면서 제일 처음 한 생각은 다리길이를 배열 또는 순서로 저장하면 되겠다는 생각을 하였다. 예를들어, 다리 길이가 2라는 것은 버스한대가 다리 길이를 통과하는데 걸리는 시간이 2초라는 의미이다. 그렇기에 다음과 같은 열거식을 작성해보았다.

[0,0] // 다리의 초기상태
---------------------
[0,7] // 무게 7짜리 버스가 다리 초입을 통과한 상태
[7,0] // 무게 7짜리 버스가 다리 끝에 선 상태
[0,4] // 무게 4짜리 버스가 다리 초입을 통과한 상태
[4,5] // 두 버스의 무게가 10을 넘지않기 때문에 무게 4,5 버스가 다리 위에 선 상태
[5,0] // 무게 5짜리 버스가 다리 끝에 선 상태
[0,6] // 무게 6짜리 버스가 다리 초입을 통과한 상태
[6,0] // 무게 6짜리 버스가 다리 끝에 선 상태
[0,0] // 모든 버스가 다리를 통과한 상태 

이렇게 작성하고 보니 int[] 배열보단 Queue 자료구조를 사용하여 FIFO 구조를 활용하면 큐의 값들을 쉽게 수정할 수 있겠다는 생각을 하였다.

 Queue<Integer> queue = new LinkedList<>();
 Queue<Integer> bridge = new LinkedList<>();
        
 for(int truck_weight : truck_weights) {
 	queue.add(truck_weight);
 }

현재 대기중인 버스 상태

그리고, 다리 위에 선 버스들의 무게를 관리하는 변수 currentWeightOnBridge를 선언하고 초기값을 0으로 설정하였다.

int currentWeightOnBridge = 0;
        
for(int i = 0; i < bridge_length; i++) {
	bridge.add(0);
}

핵심 로직을 살펴보면 다음과 같다.

while(!queue.isEmpty() || currentWeightOnBridge > 0) {
	answer++;
        	
    currentWeightOnBridge -= bridge.poll();
        	
    if(!queue.isEmpty() && currentWeightOnBridge + queue.peek() <= weight) {
    	int nextTruckWeight = queue.poll();
        bridge.add(nextTruckWeight);
        currentWeightOnBridge += nextTruckWeight;
        		
    }else {
    	bridge.add(0);
    }
        	
        
}

1. Loop 조건 : queue가 비어있지 않거나(! queue.isEmpty()) 다리 위의 현재 무게 (currentWeightOnBridge)가 0보다 큰 동안 루프를 계속 실행
- queue : 대기 중인 트럭들의 무게가 담긴 큐
- currentWeightOnBridge : 다리 위의 현재 트럭들의 무게 합

2. Time Update : answer++;를 통해 시간을 1씩 증가

3. Move Truck out of the Bridge

- bridge.poll() : 다리 위 첫 번째 트럭(가장 먼저 들어온 트럭)을 다리에서 빼내고
- currentWeightOnBridge -= bridge.poll() : 그 트럭의 무게를 
- currentWeightOnBridge에서 뺀다.

4. Check and Move New Truck onto the Bridge

- if(!queue.isEmpty() && currentWeightOnBridge + queue.peek() <= weight): 대기 중인 트럭이 있고, 그 트럭이 다리 위로 올라가도 다리의 최대 무게(weight)를 초과하지 않으면,

- queue.poll(): 대기 트럭에서 하나를 빼내어(nextTruckWeight로)
- bridge.add(nextTruckWeight): 다리 위에 올리고,
- currentWeightOnBridge += nextTruckWeight: 다리 위의 현재 무게를 업데이트한다.
- else: 만약 새 트럭이 올라갈 수 없다면,
- bridge.add(0): 다리 위에 0을 추가하여 트럭이 없음을 표현한다.

5. 위 단계들을 큐가 빌 때까지 혹은 다리 위의 트럭 무게가 0이 될 때까지 계속 반복한다.

---

가장 큰 수

📑 문3) 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

---

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

---

입출력 예

number	return
[6,10,2]	"6210"
[3,30,34,5,9]	"9534330"

---

나의 풀이

package programmers;

import java.util.Arrays;

public class BiggestNumber {
	
	public static String solution(int[] numbers) {
       
		
		String[] strNumbers = new String[numbers.length];
		
		for(int i = 0; i < numbers.length; i++) {
			strNumbers[i] = String.valueOf(numbers[i]);
		}
		Arrays.sort(strNumbers, (o1, o2) -> (o2 + o1).compareTo(o1+o2));
		
		if(strNumbers[0].equals("0")) {
			return "0";
		}
        
        return String.join("", strNumbers);
    }
	
	public static void main(String[] args) {
		int[] numbers = {3, 30, 34, 5, 9};
		solution(numbers);
	}

}

---

나의 생각

• 숫자를 문자열로 변환하여 서로 합치고 비교하면, 자릿수를 고려하지 않고 숫자를 비교할 수 있음

(o1, o2) -> (o2 + o1).compareTo(o1 + o2)
이 비교 함수는 두 문자열 o1과 o2를 연결한 두 가지 방법 
(o2 + o1 과 o1 + o2)을 비교하여 배열을 정렬하는데 사용됨
예를 들어 o1 = "3" 이고 o2 = "30"이라면 
"303","330"을 비교하게 되고, 첫 번째 문자열이 두 번째 문자열보다 
사전적으로 앞선다면 음수를, 뒤따라 온다면 양수를 반환
양수를 반환받은 경우, 정렬 알고리즘 o2가 o1보다 먼저 오도록 배열을 정렬

---

소수 찾기

📑 문4) 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

---

입출력 예

numbers	return
"17"	3
"011"	2

---

입출력 예 설명

예제 #1

• [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

• [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

---

나의 풀이

package programmers;

import java.util.LinkedHashSet;
import java.util.Set;

public class FindPrimeNum2 {
	
	
	
	static Set<String> set = new LinkedHashSet <>();
	
	
	
	public static void dfs(String prefix, String remaining) {
		
		if(!prefix.isEmpty()) {
			set.add(Integer.toString(Integer.parseInt(prefix)));
		}
		System.out.println(set);
		if(remaining.isEmpty()) {
			return;
		}
		
		for(int i = 0; i < remaining.length(); i++) {
			
			dfs(prefix + remaining.charAt(i), remaining.substring(0,i) + remaining.substring(i+1));
		}
	}
	
	public static int solution(String numbers) {
        int answer = 0;
        
        dfs("", numbers);
        
        for(String numStr : set) {
        	int num = Integer.parseInt(numStr);
        	if(isPrime(num)) {
        		answer++;
        	}
        }
        
        
        return answer;
    }

	public static boolean isPrime(int n) {
		if(n < 2) return false;
		
		for(int i = 2; i <= Math.sqrt(n); i++) {
			if(n % i == 0) return false;
		}
		
		return true;
	}
    
	
	
	
	public static void main(String[] args) {
		String numbers = "011";
		solution(numbers);
	}

}

---

나의 생각

알고리즘 공부를 하면서 문턱에 턱하고 걸리는 느낌이 드는 문제가 DFS, BFS가 있었다. 매번 문제를 풀면서 "다음에 나오면 다시 풀지 뭐...." 하고 지나쳤는데, 오늘은 기필코 깊이 우선 탐색이 어떻게 동작하는지 이해를 하기위해 하루 종일 이 문제를 잡고 있었다. 이걸 왜 하루 종일 잡고 있냐는 분들도 계시겠지만, 나로서는 이것을 이해 못하면 앞으로 나아갈 수 없기때문이다. 지금 이 문제의 풀이는 나의 머릿속에서 100% 나온 답은 아니지만 (feat.chatGPT) 내가 이해한 것을 한번 더 기록함으로써 다음에 이와 비슷한 문제가 나오면 꼭 나의 힘으로 해결하겠다.

dfs("", "011")

• i = 0 dfs("0", "11")
  • i = 0 dfs("01", "1")
    • i = 0; dfs("011","") -> 종료 (하위 호출 없음)
  • i = 1 dfs("01", "1") -> 이미 호출됨 (중복)
• i = 1 dfs("1", "01")
  • i = 0 dfs("10", "1")
    • i = 0 dfs("101", "") -> 종료
  • i = 1 dfs("11", "0")
    • i = 0 dfs("110", "") -> 종료
• i = 2 dfs("1", "01") -> 이미 호출됨 (중복)

소수 판별 메서드

public static boolean isPrime(int n) {
	if(n < 2) return false;
		
    for(int i = 2; i <= Math.sqrt(n); i++) {
    	if(n % i == 0) return false;
    }
		
    return true;
}

---

큰 수 만들기

📑 문5) 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

---

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

나의 풀이

package programmers;

import java.util.Stack;

public class MakingBigNum {
	
	public static String solution(String number, int k) {
    	
		Stack<Character> stack = new Stack<>();
		
		for(char c : number.toCharArray()) {
			while(!stack.isEmpty() && stack.peek() < c && k > 0) {
				stack.pop();
				k--;
			}
			stack.push(c);
			
		}
		
		while(k > 0) {
            stack.pop();
            k--;
        }
		
		StringBuilder sb = new StringBuilder();
		
		for(char c : stack) {
			sb.append(c);
		}
        
        return sb.toString();
    }
	
	public static void main(String[] args) {
		String number = "4177252841";
		solution(number, 4);
	}

}