문제
제출 코드(Java)
코드 제출
int weight;
int[] truck_weights;
Deque<Integer> bridge;
int currentBridgeWeight = 0;
int currentTruckIdx = 0;
int bridge_length;
int result = 0;
public int solution(int bridge_length, int weight, int[] truck_weights) {
initParam(bridge_length, weight, truck_weights);
while (currentTruckIdx < truck_weights.length) {
moveOneBlock();
if (isPossibleToaddTruck()) { addTruck(); }
result++;
}
return result + bridge_length;
}
private void moveOneBlock() {
extractTruck();
addDummy();
}
private void addDummy() {
bridge.addFirst(null);
}
private void extractTruck() {
Integer extractTruck = bridge.pollLast();
if (extractTruck != null) {
currentBridgeWeight -= extractTruck;
}
}
private void addTruck() {
int newTruck = truck_weights[currentTruckIdx++];
bridge.pollFirst();
bridge.addFirst(newTruck);
currentBridgeWeight += newTruck;
}
public void initParam(int bridge_length, int weight, int[] truck_weights){
this.bridge_length = bridge_length;
this.weight = weight;
this.truck_weights = truck_weights;
this.bridge = new LinkedList<>(Arrays.asList(new Integer[bridge_length]));
this.currentBridgeWeight = 0;
this.currentTruckIdx = 0;
this.result = 0;
}
public boolean isPossibleToaddTruck(){
if ( bridge.getFirst() != null ) { return false; }
else if (currentTruckIdx >= truck_weights.length) { return false; }
else { return (currentBridgeWeight + truck_weights[currentTruckIdx]) <= weight; }
}bridge_length Size만큼의 dummy Data를 넣은 Queue를 통해 해결한 문제
정확성 테스트
테스트 1 〉 통과 (1.88ms, 53.1MB)
테스트 2 〉 통과 (8.07ms, 53.3MB)
테스트 3 〉 통과 (0.20ms, 52.1MB)
테스트 4 〉 통과 (6.67ms, 53.2MB)
테스트 5 〉 통과 (34.11ms, 60.3MB)
테스트 6 〉 통과 (14.05ms, 55.6MB)
테스트 7 〉 통과 (2.08ms, 52.4MB)
테스트 8 〉 통과 (0.69ms, 52.8MB)
테스트 9 〉 통과 (4.45ms, 54.3MB)
테스트 10 〉 통과 (0.65ms, 52.9MB)
테스트 11 〉 통과 (0.21ms, 51.9MB)
테스트 12 〉 통과 (1.11ms, 52.6MB)
테스트 13 〉 통과 (3.88ms, 53.2MB)
테스트 14 〉 통과 (0.75ms, 52.9MB)처음에 다리 길이만큼 이동해야한다는걸 놓쳐 한참 풀다가 처음으로 되돌아간 문제,,, 문제 해결 능력도 좋지만 일단 처음에 문제 분석부터 제대로 해야겠다...
그리고 코딩 테스트지만 method 분리로 구현하기로 다짐했던 계기가 된 문제
제출 코드(Python)
첫번째 코드 제출
import collections
def solution1(bridge_length, weight, truck_weights):
currentBridgeWeight = 0
currentTruckIdx = 0
answer = 0
bridge = deque([0 for i in range(0, bridge_length)]);
while currentTruckIdx < len(truck_weights):
# moveOneBlock
outTruck = bridge.pop()
if outTruck > 0:
currentBridgeWeight -= outTruck
bridge.appendleft(0)
answer += 1
if currentTruckIdx >= len(truck_weights):
pass
elif bridge.index(0) > 0:
pass
else:
if (currentBridgeWeight + truck_weights[currentTruckIdx]) <= weight:
# addTrcuk
newTruck = truck_weights[currentTruckIdx]
bridge[0] = newTruck
currentBridgeWeight += newTruck
currentTruckIdx += 1
answer += bridge_length
return answer
java와 비슷한 구현 방식.
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.98ms, 10.2MB)
테스트 2 〉 통과 (11.32ms, 10.4MB)
테스트 3 〉 통과 (0.02ms, 10.2MB)
테스트 4 〉 통과 (11.39ms, 10.3MB)
테스트 5 〉 통과 (106.02ms, 10.4MB)
테스트 6 〉 통과 (32.49ms, 10.2MB)
테스트 7 〉 통과 (0.93ms, 10.2MB)
테스트 8 〉 통과 (0.20ms, 10.1MB)
테스트 9 〉 통과 (4.22ms, 10.3MB)
테스트 10 〉 통과 (0.24ms, 10.3MB)
테스트 11 〉 통과 (0.02ms, 10.2MB)
테스트 12 〉 통과 (0.41ms, 10.2MB)
테스트 13 〉 통과 (1.57ms, 10.3MB)
테스트 14 〉 통과 (0.01ms, 10.2MB)java와 같은 풀이로 구현하려 했으나, method안에서는 전역변수 수정이 안된다는걸 깨닫고 내부 구현으로 해결
두번째 코드 제출
import collections
DUMMY_TRUCK = 0
class Bridge(object):
def __init__(self, length, weight):
self._max_length = length
self._max_weight = weight
self._queue = collections.deque()
self._current_weight = 0
def push(self, truck):
next_weight = self._current_weight + truck
if next_weight <= self._max_weight and len(self._queue) < self._max_length:
self._queue.append(truck)
self._current_weight = next_weight
return True
else:
return False
def pop(self):
item = self._queue.popleft()
self._current_weight -= item
return item
def __len__(self):
return len(self._queue)
def __repr__(self):
return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))
def solution(bridge_length, weight, truck_weights):
bridge = Bridge(bridge_length, weight)
trucks = collections.deque(w for w in truck_weights)
for _ in range(bridge_length):
bridge.push(DUMMY_TRUCK)
count = 0
while trucks:
bridge.pop()
if bridge.push(trucks[0]):
trucks.popleft()
else:
bridge.push(DUMMY_TRUCK)
count += 1
while bridge:
bridge.pop()
count += 1
return count
def main():
print(solution(2, 10, [7, 4, 5, 6]), 8)
print(solution(100, 100, [10]), 101)
print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)
if __name__ == '__main__':
main()
원래 내가 구현하고 싶었던 방식,, class화해서 해결
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (2.54ms, 10.3MB)
테스트 2 〉 통과 (26.80ms, 10.3MB)
테스트 3 〉 통과 (0.08ms, 10.3MB)
테스트 4 〉 통과 (22.04ms, 10.3MB)
테스트 5 〉 통과 (221.04ms, 10.3MB)
테스트 6 〉 통과 (60.32ms, 10.4MB)
테스트 7 〉 통과 (1.96ms, 10.3MB)
테스트 8 〉 통과 (0.46ms, 10.3MB)
테스트 9 〉 통과 (7.58ms, 10.3MB)
테스트 10 〉 통과 (0.58ms, 10.2MB)
테스트 11 〉 통과 (0.03ms, 10.2MB)
테스트 12 〉 통과 (0.86ms, 10.2MB)
테스트 13 〉 통과 (2.37ms, 10.3MB)
테스트 14 〉 통과 (0.11ms, 10.2MB)성능 자체는 비슷하거나 더 안나오지만 python에서 class화를 권장하기도하고 이에 대해 더 공부해야겠다
Be More!