처음 문제를 보고 뭘해야하는지 감이 잡히지 않아 생각보다 시간이 소요되었다.
이때까지 코테공부는 주구장창하였지만 자바로 api호출, jsonParsing 등은 해본적이 없어 더 그랬던 것 같다. 나같은 사람들에게 이글이 도움이 되길 바라면서!!
(api호출, json파싱은 다른글에!)
해당글 참조
1번문제 성능
합격자 평균 대여 성공 건수 : 1268건
합격자 최대 대여 성공 건수 : 1384건
코드 성공건수 : 1310건
2번문제 성능(2번문제 따로 조건 적용 하지 않음)
합격자 평균 대여 성공 건수 : 9652건
합격자 최대 대여 성공 건수 : 10784건
코드 성공건수 : 9709건
(2번문제의 핫스팟은 고려하지 않았습니다.수정중)
카카오 T 바이크 관리 시뮬레이션
https://tech.kakao.com/2021/02/16/2021-kakao-recruitment-round-2/
위 주소에 카카오에서 제공한 자세한 문제 및 해설이 있습니다.
문제 접근법
첫번째접근 방법(실패)
현실의 킥보드수거하는 구조를 생각해보면 많이 쌓여있는 장소의 킥보드를 부족한 장소에 옮겨 주는 것으로 알고 있습니다.
해당 방식에 따라 문제를 접근하였습니다.
- 평균 보다 많은 바이크를 가진 장소를 찾아 가장 가까운 트럭에 싣는다
- 평균 보다 작은 수의 가진 장소와 가까운 트럭에서 바이크 평균 갯수가 될때 까지 채워준다.
문제점 -> 생각보다 바이크를 대여하고 있는 유저가 많았고, 그로 인해 바이크가 부족한 곳을 많지만 바이크가 여유로운 장소가 거의 없었다.
결과 -> 최소 대여 성공 건수(트럭을 움직이지않는 상태)와 거의 유사
두번쨰접근 방법
위 방법에서 바이크 수거 기준을 평균-> 평균/2로 수정해주었다.
자세한 풀이를 작성해보면
- 평균의/2보다 많은 바이크를 가지고 있는 장소들을 takeArray에 담아줌
- 평균의/2보다 작은 바이크를 가지고 있는 장소들을 fillArray에 담아줌
- takeArray에 들어있는 장소기준으로 truck가까운 순서대로 정렬해줌
- truck해당위치로 이동후 바이크 싣기(truck의 소요시간과 가지고있는 바이크 수 업데이트)
- fillArray에 들어있는 장소기준으로 truck가까운 순서대로 정렬해줌
- 짐을들고있는 truck해당 위치로 이동후 바이크 내리기
- 1~6을 반복하며 여러장소에 골고루 바이크를 분포 시킴
최단거리 및 좌표
장소의 좌표는 위와 같이 id로 표시되어있기 때문에 최단 거리의 트럭 찾기 위해서는 좌표를 이해할 필요가 있다.
nxn의 행렬기준으로
열위치: id/n
행위치: id%n
위로 이동: id+1
오른쪽 이동: id+n
아래 이동: id-1
왼쪽 이동: id-n
경로이동 커맨드 메소드
private static void findRoute(Truck truck, Location location, Command command) {
int loc_id=location.getId();
int loc_truck=truck.getLocation_id();
int truck_c=loc_truck/n;//트럭열
int loc_c=loc_id/n;//장소열
int truck_r=loc_truck%n;//트럭행
int loc_r=loc_id%n;//장소행
while(truck_c!=loc_c&&truck.getTime_remaining()>=6){//트럭의 이동시간이 남아있으면서 트럭열과 장소열 같아질때까지
if(truck_c>loc_c){//왼쪽이동
command.getCommand().add(4);
truck_c--;
}else{//오른쪽이동
command.getCommand().add(2);
truck_c++;
}
truck.useTime();
}
while(truck_r!=loc_r&&truck.getTime_remaining()>=6){
if(truck_r>loc_r){//아래
command.getCommand().add(3);
truck_r--;
}else{//위
command.getCommand().add(1);
truck_r++;
}
truck.useTime();
}
}