HackerRank Interview Preparation Kit > Arrays

HackerRank의 Interview Preparation Kit > Arrays의 medium이상 문제

New Year Chaos - medium

문제요약

n명이 줄을 서 있고 각자 처음의 위치(1...n)를 가지고 있다. 각각 자신의 바로 앞 사람과 자리를 변경할 수 있으며 최대 2번까지만 가능하다. 임의의 순서가 주어졌을 때 최초 순서부터 몇 번의 위치 변경을 통해 가능한지 최소 횟수를 불가능하다면 "Too chaotic"을 출력한다. (1<=n<=10^5)

Sample Input

2

5

2 1 5 3 4

5

2 5 1 3 4

Sample output

3

Too chaotic

풀이

처음부터 어렵게 접근해서, 경우들을 다 생각해보느라 시간을 많이 썼다. 문제를 다시 보면 처음에 순서대로 정렬되어 있고 바로 앞 사람과 만 위치를 변경가능하고, 최대 2번까지만 변경 할 수 있다.

즉, 현재 위치가 원래 위치보다 3이상 앞으로 와있다면 불가능한 경우이다.('Too chaotic')

그렇지 않은 경우, 문제의 위치 변경이 bubble sort의 역과 비슷하다. 즉 정렬되지 않은 array의 앞에서부터 시작하면 큰 값들이 뒤로 한 칸씩 이동하면서 정렬이 된다. 그리고 최종적으로 1...n의 순서로 최초 위치와 동일하게 된다.

따라서 해당 순서를 bubble sort를 이용해 정렬하면서 위치가 변경되는 횟수를 구하면 답을 찾을 수 있다.

이 때 주의할 점은 loop를 무작정 돌리다보면 timeout이 발생할 수 있는데, bubble sort시 swap이 발생하지 않았다면 이미 정렬된 것으로 보고 탈출시키는 최적화 작업이 추가되어야 한다.

실제 bubble sort를 수행하지 않고 횟수를 계산할 수도 있다고도 한다.

Minimum Swaps 2 - medium

문제요약

[1, 2, 3, ..., n]까지의 정수가 중복없이 들어있는 정렬되지않은 array가 있다. 두 개의 숫자만 위치를 서로 변경하면서 제 위치로 정렬 되는 최소의 변경 횟수를 출력한다. (1<= n <= 10^5)

Sample Input

4

4 3 1 2

Sample Output

3

문제풀이

위의 문제를 이어서 풀면서 정렬 알고리즘을 연결하다가 괜히 시간을 잡아먹었다. 쉽게 생각하면 제 자리로 돌리기 위해서는 각각 자기 위치에 있는 숫자와 변경을 해주어야 한다. 즉 최대 n-1번의 swap이 발생할 수 있고, 혹시라도 제자리에 있거나, swap 한 번으로 두 숫자가 모두 제자리를 찾거나 하면 횟수는 줄어들게 된다.

Array Manipulation - Hard

문제요약

인덱스가 1부터 시작하고 n개의 0으로 초기화된 array가 있다. 입력 (a b k)가 입력되면 a<=i<=b인 요소들에 대해 k를 더한다.  m개의 주어진 입력 (a b k) 모두 수행하고 났을 때 해당 array의 가장 큰 값을 반환한다. (3<=n<=10^7, 1<=m<=2*10^5, 0<=k<=10^9)

Sample Input

5 3

1 2 100

2 5 100

3 4 100

Sample Output

200

문제풀이

처음엔 그냥 계산을 다 해서 결과를 구했다. 답은 나오지만 많은 경우에는 time out이 발생한다. medium까지는 시간이 있으면 풀 수 있겠지만 hard는 방법적인 부분을 찾아내야해서 쉽지않다. 정답을 보고 이해하는 것도 노력이 필요하다.

정리를 하면, 굳이 계산을 다 할 필요없이 각 array를 더한 결과값이 아닌 이전 인덱스와의 차이를 저장하도록 하면 각 연산 (a b k)를 다 할 필요 없고, 최종 결과 누적해서 더하면 결과값을 알 수 있다. 즉 [2]의 최종값은 [1] + [2], 3의 최종값은 [2]의 최종값 + [3] = [1] + [2] + [3]... 이런식으로.

즉 모두 0인 상태에서 [a]에 k를 더하고, [b+1]에는 k를 빼주면 [a+1],...,[b]은 0이므로 [a]값과 같다는 의미이고, [a+1]은 [a]보다 k만큼 작다는 의미가 된다. 다시 [a+2] 부터는 [a+1] 0이므로 [a+1]과 같다는 의미로 볼 수 있다.

sample을 보면,

    [0,   0,      0,   0,    0]

    [100, 0,   -100,   0,    0]

    [100, 100, -100,   0,    0]

    [100, 100,    0,   0, -100] => [100, 200, 200, 200, 100]로 알아낼 수있다.

DP를 비롯해서 연산 횟수를 줄이는 문제들이 종종 어려운 문제로 등장한다.  염두하고 방법을 생각할 때 고려할 필요가 있겠다.