반응형
1680번 쓰레기 수거
https://www.acmicpc.net/problem/1680
1680번: 쓰레기 수거
쓰레기장에서 출발한 쓰레기차가 여러 지점들을 방문하며 쓰레기를 모으고 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 방문하며, 쓰레기를 모으다가 다음과 같은 경우에 쓰레기장으로 돌
www.acmicpc.net
Comment
일반 시뮬레이션 구현문제라서 평소처럼 풀까하다가 자바스럽게 풀어보고싶어서 객체지향(?)적으로 설계를 하기 위해 노력하면서 구현해보았다.
알고리즘을 풀 때 클래스를 잘 활용하지 않아서 생각보다 많이 오래걸렸던 문제
hint
문제를 잘 읽고 테스트케이스 또한 해당 지문에 맞춰서 잘 이해해야한다.
Solution
메모리나 시간이나 상관없이 구현만 잘하면 되는 문제였다. 때문에 클래스를 만들어서 써보기에 더 좋았던 것 같다.
일단 해당 문제의 1, 2, 3번 조건을 항상 잘 생각해서 염두에 두고 조건을 넣는다면 쉽게 풀리는 문제일 것이다.
1번의 시점은 다음 지점으로 이동하기 전이고, 2번의 시점은 쓰레기를 싣기 전, 3번은 가장 마지막. 이렇게 해당 분기를 잘 확인해서 조건처리만 잘 해준다면 문제 해결은 쉽게 될 것이다.
클래스 활용해서 구현하면 속도가 안나온다....
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | import java.io.*; import java.util.*; public class p1680 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); int weight, point; StringTokenizer st; StringBuilder sb = new StringBuilder(); while (t-- > 0) { st = new StringTokenizer(br.readLine()); weight = Integer.parseInt(st.nextToken()); point = Integer.parseInt(st.nextToken()); p1680TrashCar garbageTruck = new p1680TrashCar(weight, 0); for (int i = 0; i < point; i++) { st = new StringTokenizer(br.readLine()); int pointDistance = Integer.parseInt(st.nextToken()); //해당 위치의 거리값(원점기준) int pointWeight = Integer.parseInt(st.nextToken()); //해당 위치의 쓰레기양 garbageTruck.movePoint(pointDistance); // 해당 포인트로 이동 while (pointWeight > 0) { if (!garbageTruck.possibleCollect(pointWeight)) { //용량을 넘게될때 garbageTruck.movePoint(0); garbageTruck.movePoint(pointDistance); } if (garbageTruck.possibleCollect(pointWeight)) { // 용량이 넘지않으면 True반환 pointWeight = garbageTruck.collectTrash(pointWeight); // 쓰레기 수집 -> 해당 위치의 쓰레기는 0이됨 } if (garbageTruck.isFull() && i != point - 1) { // 마지막 지점이 아닐 때 쓰레기가 꽉차면 수거장에 가서 비우고 와야함 garbageTruck.movePoint(0); garbageTruck.movePoint(pointDistance); } } if (i == point - 1) { garbageTruck.movePoint(0); } } sb.append(garbageTruck.getMeter()).append("\n"); System.out.println(garbageTruck.getPoints()); // 쓰레기를 담기위해 문제제출할 땐 주석처리해야함 } System.out.println(sb); } } /** * 기본 차 인터페이스 * recentDestination : 목적지에 이동할 때 이동한 거리를 매 순간 담음 */ interface p1680Car { public int getMeter(); public void movePoint(int distance); ArrayList<Integer> recentDestination = new ArrayList<>(); default public void pointAdd(int n) { recentDestination.add(n); } default public ArrayList<Integer> getPoints() { return recentDestination; } default public void resetDestList() { recentDestination.clear(); } } /** * TrashCar는 p15979Car의 상속을 받아 Meter와 movePoint를 반드시 사용해야한다. * 추가로 쓰레기를 담을 capacity, 쓰레기의 용량상태확인이 필요한 trashWeight이 필요 */ class p1680TrashCar implements p1680Car { private int capacity; private int trashWeight; private int meter; private int nowLocation; public p1680TrashCar(int capacity, int nowLocation) { this.capacity = capacity; this.nowLocation = nowLocation; resetDestList(); } @Override public int getMeter() { return meter; } @Override public void movePoint(int point) { if (point == 0) { pointAdd(nowLocation); meter += nowLocation; nowLocation = 0; trashWeight = 0; return; } pointAdd(point - nowLocation); meter += point - nowLocation; nowLocation += point - nowLocation; } public boolean possibleCollect(int weight) { if (capacity < trashWeight + weight) { return false; } return true; } public boolean isFull() { // 비었을 때는 꽉차는지 체크 if (trashWeight >= capacity) { return true; } return false; } public int collectTrash(int weight) { trashWeight += weight; return 0; } } | cs |
반응형
'공부 > Algorithm' 카테고리의 다른 글
백준 12755번 수면 장애 자바로 풀어 본 짧은 글 (0) | 2023.11.21 |
---|---|
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글 (0) | 2023.09.15 |
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글 (0) | 2023.08.17 |
백준 골드5 달성! (0) | 2023.08.11 |
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글 (0) | 2023.08.03 |