HackerRank - Largest Permutation

www.hackerrank.com/challenges/largest-permutation/problem

Largest Permutation | HackerRank

문제 - 1부터 증가하는 정수를 구성요소로 하는 배열이 있다. 그리고 제한된 교환 횟수 안에서 두 번호를 교환할 수 있다. 함수가 실행되면 가장 큰 수부터 앞쪽에 정렬되는 배열을 리턴해야 한다.

입력값 1. 교환횟수 int k

입력값 2. 정수배열 int[] arr

 

문제점. - 구현 시 문제.

문제는 빨리 이해했다. 그런데 디테일한 고려사항들을 놓쳤다.

1. 배열의 구성요소. 1부터 1씩 증가하는 배열이다. (1이 구체적으로 언급되지는 않았지만 Input Format을 보면 n개의 요소가 있는 arr는 1≤arr(i)≤n 이라는 조건이 있다. 즉, 최대값은 배열의 사이즈이고, 최소값은 1이며 각 요소간의 차이는 1임을 알 수 있다.)

2. swap 횟수는 실제로 숫자의 위치를 바꿨을 때에만 카운트 해야 한다. (이걸 놓침...) 그리고 이 부분은 코드 최적화에도 포함되는 요소이다.

 

1번을 초반에 고려하지 못해서 일반적인 정렬로직을 만들었다. -> 시간 많이 걸림.

그리고 2번을 고려하지 못해서 swap 횟수만큼 항상 숫자가 바뀐다고 생각을 했다.(정확히 말하면 숫자가 바뀌지 않을 경우를 생각하지 못했다.)

토론방을 보지 못했다면 문제점을 파악하기 어려웠을 것이다.(진짜...이건 너무 한심했다...ㅜㅜ)

 

사실 2번이 문제를 풀지못한 핵심이었다.

코딩 구현보다 정확한 문제의 이해가 우선이다. 잊지말자!!