프로그래머스 - 택배배달과수거

문제 설명

최소한의 이동거리로 배달과 수거를 모두 마치는 거리를 구하는 문제이다.

최대길이가 10만이다.

단순히 구현하는 문제인데, 구현을 해나가는 과정이 쉽지않다.

그래서 나는 이렇게 시도해봤다.

배달 또는 수거할 제일 먼곳을 찾는데, 먼곳을 가는 과정에서 배달할 물건을 내려놓는다고 생각했다.

그리고 끝지점에서 다시 물건을 실으러 오면서 회수할 물건을 최대 담아내는 탐욕법을 이용했다.

풀이

 

public long solution(int cap, int n, int[] deliveries, int[] pickups) {
		TreeMap<Integer, Integer> d = new TreeMap();
		for (int i = 0; i < n; i++) {
			if( deliveries[i] ==0 ) continue;
			d.put(i + 1, deliveries[i]);
		}
		TreeMap<Integer, Integer> p = new TreeMap();
		for (int i = 0; i < n; i++) {
			if( pickups[i] ==0 ) continue;
			p.put(i + 1, pickups[i]);
		}
		int todo = 0;
		int bring = 0;
		long totalDist = 0;
		while (true) {
			int todoD = d.size() == 0 ? 0 : d.lastKey();
			int todoP = p.size() == 0 ? 0 : p.lastKey();
			// 해당 목적지 최고점을 가면서 내려준다는 점
			if (todoD != 0) {
				while (todo != cap) {
					if (d.size() == 0)
						break;
					if (todo + d.get(d.lastKey()) <= cap) {
						todo += d.get(d.lastKey());
						d.remove(d.lastKey());
					} else {
						d.put(d.lastKey(), d.get(d.lastKey()) - (cap - todo));
						todo = cap;
					}
				}
			}

			if (todoP != 0) {
				while (bring != cap) {
					if (p.size() == 0)
						break;
					if (bring + p.get(p.lastKey()) <= cap) {
						bring+=p.get(p.lastKey());
						p.remove(p.lastKey());
					} else {
						p.put(p.lastKey(), p.get(p.lastKey()) - (cap - bring));
						bring = cap;
					}
				}
			}

			totalDist += Math.max(todoD, todoP) * 2;
			todo=0;
			bring=0;
			if(p.size()==0 && d.size()==0) break;
		}

		return totalDist;
	}