💬 회고
문제 자체가 막 어렵지는 않았다.
정해진 횟수만큼 배열의 최댓값이 저장된 곳은 -1, 최솟값이 저장된 곳은 +1을 하는 코드를 작성하면 됐다.
그리고 문제를 해결하는 것도 그렇게 어렵지는 않았지만 문제를 풀고 나서 분명 내가 지금 푼 것보다 더 좋은 방법이 있을거라는 생각이 들었기 때문에 블로그에 기록한다!
💡 더 좋은 아이디어
minIdx
minHeight
maxIdx
minHeight
4개의 변수를 이용하고 움직여야 하는 횟수만큼 이 숫자들을 갱신하고
height[maxidx]--
height[minidx]++
를 해주었는데 이렇게 할 필요없이
for(int i = 0 ; i < move; i++){
Arrays.sort(boxHeight);
box[0]++;
box[99]--;
}정렬을 이용해서 move순간마다 현재 높이 배열의 첫번째는 최소, 마지막은 최대로 위치하게 하면 짧은 코드로 완성이 가능하다! 시간복잡도 측면에서도 그렇게 큰 차이를 낼 것 같지는 않다!
📝정리
배열이 주어지고 그 배열에 최소랑 최대를 다루게 되는 경우 시간복잡도가 괜찮다면 정렬을 해놓고 구해보자!!
자바 Arrays.sort의 시간복잡도[피봇]: n * log(n) 근데 최악은 n제곱!
자바 Collections.sort의 시간복잡도[삽입,합병]: 항상 n *log(n)
