종료 시간을 기준으로 오름차순 정렬하는 건 맞다.
하지만 종료 시간이 같다면 시작 시간이 빠른 것이 앞에 오도록 정렬해야 함.
시작 시간이 늦으면 더 적은 시간을 써서 유리할 것이라고 생각했었는데
다음 반례를 보면 아니다.
N = 3
1 4
4 8
8 8
좌표들을 한 좌표로 최단거리로 모으는 좌표는
(행,열) 값들의 평균값이 아니다.
중앙값이다.
또 격자 크기를 N, 좌표 갯수를 M이라고 네이밍을 했더니 N,M을 헷갈렸다.
MAP_SIZE, POINT_COUNT로 네이밍했으면 헷갈리진 않았을 듯.
실수는 아니지만 웰노운 정리
오름차순 정렬한 수열 arr이 있을 때 prefixSum[i-1]+1 >= arr[i]이면
prefixSum[i-1]+arr[i]까지의 모든 수는 arr[i]까지의 수들을 적절히 더해서 만들 수 있다.
- 문제 조건 잘 읽기.
- 초기화 잘못하여 많이 틀림.
답이 Integer.MAX_VALUE까지 가능했다.
초기화를 Integer.MAX_VALUE가 아니라 보다 크게 설정했어야 했다.
해커랭크/hard/Insertion Sort Adavanced Analysis
와,,, 참신한 접근이 필요했던 문제다....
1. 처음 생각 및 접근
일단 배열의 각 원소를 이동하는 순서는, 그때 그때 최적으로만 이동하면, 총 이동 횟수에 영향을 주지 않는다고 추측했다.
BIT를 사용하면 답을 구할 수 있을거라 생각했다.
배열의 수들을 정렬하고, 각 수의 개수 및 개수 psum 구하고..
->로 iterating하면서 적절히 psum에서 빼주고.. 이런 식으로 하면(좀 추상적이긴 하다만..) 될 거라 생각했었다.
근데 BIT를 구현하기 복잡해서 관뒀다.
2. 해설을 본 뒤..
merge sort의 과정을 떠올려보면 답이 나온다..................
merge sort를 split과 merge 과정으로 나누면,
merge 과정은 정렬된 두 배열을 투포인터 알고리즘 써서 하나로 정렬한다.
이 때 오른쪽 배열의 원소가 왼쪽 배열의 원소보다 크면 왼쪽으로 shift가 발생했다고 볼 수 있다!!!!!!!!
근데 merge sort 구현 좀 자신이......
