HackerRank Interview Preparation Kit > Search

HackerRank의 Interview Preparation Kit > Search의 Medium 이상 문제

Hash Tables: Ice Cream Parlor - medium

문제요약

길이가 n인 정수 배열 cost와 정수 money가 주어지면, cost에서 두 item을 골라 money가 되는 index(base1)를 오름차순으로 출력

첫 줄은 test case t (1<=t<=50), 이후 세줄 씩은 money(2<=money<=10^9), n(2<=n<=5*10^4), n개의 cost[i] (1<=cost[i]<=10^9)

Sample Input

2

4

5

1 4 5 3 2

4

4

2 2 4 3

Sample Output

1 4

1 2

풀이

제목처럼 hash table을 사용하면 된다. 처음엔 각 수를 dictionary에 저장했고, 충돌을 위해 list를 저장해서 미리 값-[인덱스]를 구해놓고 다시 cost를 돌면서 합이 money가 되는 값이 있는지 dictionary를 조사해서 확인했다. 통과는 했으나 굳이 미리 구해놓을 필요가 없다. 두 과정을 하나로 합쳐서 현재 cost와 합해서 money가 되는 값이 들어있는지 조사하고 없으면 dictionary에 추가한다.

Swap Nodes [Algo] - medium

문제요약

binary tree와 정수 k가 주어지면 높이(1부터)가 k의 배수인 노드의 left와 right를 swap한다. k마다 swap 후 inorder traversal로 결과를 반환한다.

첫 줄엔 노드 수 n, 다음 n 줄엔 i번째 노드의 left와 right인 a b(-1은 null node), 다음 줄엔 k의 수 t, 다음 t줄엔 k들이 입력된다.

(1<=n<=1024, 1<=t<=100, 1<=k<=n, a=-1 or 2<=a<=n, b=-1 or 2<=b<=n)

Sample Input

3

2 3

-1 -1

-1 -1

2

1

1

Sample Output

3 1 2

2 1 3

풀이

swap을 처리하려면 link기반의 tree를 구성해야 한다. Node class를 만들고 입력에 따라 binary tree를 만든다. i번째 노드의 값은 i이므로 data는 미리 초기화하고 left와 right만 연결해주면 구성이된다.

이후 swap과 inorder를 처리해야 하는데, 시간을 줄이기 위해 inorder traversal하면서 swap을 함께 처리한다.

최종 결과를 테스트하면 timeout이 발생하는데 python이 재귀를 1000번 까지만 허용하기 때문이다. 이를 위해 limit을 추가로 늘리는 부분도 함께 적용한다.(기억해두자!)

Pairs - medium

문제요약

n개의 정수배열 arr과 k가 주어지면 arr에서 arr[i]-arr[j] = k인 (i,j)의 갯수를 구한다.

(2<=n<=10^5, 0<k<10^9, 0<arr[i]<2^31-1)

Sample Input

5 2
1 5 3 4 2

Sample Output

3

풀이

문제를 푸는 방법은 두 가지가 생각났다. 첫 번째는 정렬 후에 각 값에 대해 arr[i]-k 값이 있는지 binary search로 찾는 것. 그렇게 되면 정렬하는데 O(nlog(n))이 소요되고, binary search에 각 O(log(n))이므로 전체에 대해선 O(nlog(n))이 소요되므로 전체적으로 O(nlog(n))이 된다.

discussion에 보면 binary search를 사용하지 않고 두 개의 index를 통해 찾는 방법도 있다. i=0, j=1부터 시작해서 arr[j]-arr[i]가 k이면 갯수를 증가하고 i++, j++. k보다 크면 i++, k보다 작으면 j++. 이렇게 하면 정렬에 O(nlog(n))과 판단에 O(n)이므로 전체적으로 O(nlog(n))이 되나 좀 더 빠르다.

하지만 두 번째 방법은 dictionary를 사용하는 것이다. memory를 추가로 O(n)이 필요하겠지만 검색시간이 O(n)이 되므로 전체 시간으로는 O(n)이된다.

마찬 가지로 discussion을 보다 알았지만 모든 항목이 unique하기 때문에 dictionary대신 set을 쓰는 것이 좀 더 나은 듯 하다.

dictionary와 set의 in에 대한 time complexity은 O(1)이라고 한다.(평균적인 경우에, hash를 잘못쓰면 O(n)) - https://wiki.python.org/moin/TimeComplexity

Triple sum - medium

문제요약

길이가 다른 정수배열 a, b, c가 주어질 때, p∈a, q∈b, r∈c이고 p<=q, q>=r인 중복되지 않는 (p, q, r)의 갯수를 구한다.

(1<=lena, lenb, lenc<=10^5, 1<=all elements in a,b,c<=10^8)

Sample Input

3 2 3
1 3 5
2 3
1 2 3

Sample Output

8

풀이

결과만 생각해보면 b의 각 q보다 작거나 같은 a의 원소 갯수 * c의 원소 갯수를 하면 q에 대한 경우의 수를 계산할 수 있다. 단 중복을 없애기 a, b, c에서 모두 중복된 원소를 제거해야 한다. 따라서 a, b, c를 set으로 변경하고 정렬한 다음 위 계산을 처리한다.

Minimum Time Required - medium

문제요약

만들어야 하는 item 갯수 goal과  n개의 각 machine에서 item 1개를 만드는게 걸리는 일 수가 주어지면, goal을 만드는데 걸리는 최소 일수를 계산한다. (1<=n<=10^5, 1<=goal<=10^9, 1<=machines[i]<=10^9)

Sample Input

2 5

2 3

Sample Output

6

풀이

특정 일안에 주어진 machine들로 만들어지는 item 수는 해당 일에서 각 machine별 일수로 나눈 몫을 더해주면 알 수 있다. 즉 위의 예에서 5일 동안 생산된 item 수는  5//2 + 5//3 = 2 + 1 = 3개가 된다. 문제는 역으로 결과를 가지고 일수를 알아내야 한다.

각 경과된 일 동안의 만들어지는 item수를 알 수 있으므로 goal보다 이상인 item을 만드는 최솟값을 찾아내야 하는데 일수를 1부터 증가하면서 찾는다고 하면 너무 오래 걸리게 된다. 범위를 생각해보면 machine의 가장 작은 값으로 모든 machine이 되어 있을 때 걸리는 일수와 가장 큰 값으로 모든 machine이 되어 있을 때 걸리는 일수 사이에 원하는 답이 있게 된다. 따라서 상한과 하한을 두고 binary search를 활용하면 단순 탐색보다 빠르게 결과를 찾을 수 있다. binary search를 언듯 생각했으나 범위에 대해서 생각을 하지 못해 쉽게 해결하지 못했다. 뭔가 다른 계산 방법이 있을 줄 알고... 때론 쉽게 생각하고, 한 가지를 깊게 생각해보는게 필요할 듯 하다.