매일 성장하는 블로그

https://www.hackerrank.com/challenges/crush/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

매우 골치를 썩였던 문제입니다.

단순히 풀리나 싶더니 어김없이 Time Limit을 걸어놓았더군요 ㅎㅎ

discussion을 조금 보고서야 풀 수 있었습니다.

문제 : 길이가 n이며 원소가 모두 0인 배열 arr이 주어질 때, 주어지는 query에 따라서 arr[a:b]에 k만큼 더한다. query들이 끝나면, 배열 내에서 가장 큰 수를 찾는다.

input : n, m, a, b, k

n : array의 길이

m : query의 수

a : 시작 index

b : 끝 index

k : 더하는 수

Ex) n = 5, m = 3 a,b,k = [[0, 1, 100], [1, 2, 100], [2, 3, 100]]

n= 5이므로 처음 배열의 시작은 

[0,0,0,0,0]

1) a = 1, b = 2, k = 100

arr 배열의 1번째 원소부터 2번째 원소까지 k만큼 더합니다.

→ [100, 100, 0, 0, 0]

이와 같이 문제를 풀어나가시면 됩니다. 다만 단순히 구현만 해서는 Timeout에 걸릴 수 있으니 주의하세요.

직접 풀어보시길 추천합니다. 저는 방법에 대한 힌트를 얻어서 이미 불가능했습니다..

방법 :

0) arr = [0] * (n+1) 

* n+1개를 만드는 이유는 1)번 과정을 보시면 이해할 수 있습니다.

1) query가 주어질 때([a,b,k]), a-1번째 원소에 +k를, b번째 원소에 -k를 해줍니다.

 * a와 b의 index는 1부터 시작하기 때문에, a,b가 주어졌을 때 arr[a-1: b] += k를 해줘야 합니다.

 * 여기서 (1)번을 수행하는 이유는, a-1번째 원소부터 b-1번째 원소들의 최대값을 표시한 것입니다. 모두 동일한 값을 더했기 때문에 우리가 구하길 원하는 최댓값을 구하는 방법을 간단히 구현하였습니다.

(arr의 최댓값을 구하는 3번 과정을 보시면 더 잘 이해할 수 있습니다.)

2) 1)번이 완료되면, arr에 for loop을 돌리면서 값들을 더해줍니다. 더해주는 과정에서 max가 될 때의 값을 찾아냅니다.

max, x = 0

for i in arr:

    x += i

    if(max<x):

        max = x

https://www.hackerrank.com/challenges/minimum-swaps-2/submissions/code/149223858?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

이번 문제는 주어진 배열을 정렬하기 위해 필요한 최소의 swap 수를 구하는 것입니다.

[4, 3, 2, 1]이란 배열이 주어진다면, 이 배열을 [1,  2 3, 4]로 정렬하기 위해 필요한 swap의 수를 구하면 됩니다.

이 때, swap은 아무 위치에 있는 숫자끼리도 바꿀 수 있습니다.

위의 예를 보면,

[4,1] swap → [1, 3, 2, 4]

[3,2] swap → [1, 2, 3, 4]

따라서 위의 배열을 정렬하는데 필요한 최소의 swap 수는 2입니다.

1. 방법

  1) for loop에 enumerate 함수를 사용하여 idx, 숫자를 순차적으로 뽑아냅니다.

  2) 만약 idx와 숫자(x)가 일치하지 않는다면(정렬되어있지 않다는 뜻), 해당 숫자(x)의 고유 idx 위치에 숫자(x)를 입력합니다.(일치하면 for loop 지속)

  3) swap 횟수를 1을 더해줍니다.

  4) x의 고유idx에 존재하던 숫자(y)와 y의 고유 idx에 있는 숫자 z를 비교하고, 다르다면 swap한 뒤 swap 횟수에 1을 더합니다.(같아질 때까지 반복하고, 같다면 swap 횟수에 1을 빼고 for loop로 복귀합니다.) 

  5) for loop이 완료될 때까지 (2) - (4)를 반복한다.

* 이 때 for loop 복귀 전에 swap 횟수를 1을 빼주는 이유는, 위에서 주어진 예시[4,3,2,1]에서의 [1,4], [3,2]와 같이 한번 swap을 통하여 두 숫자가 제자리를 찾아가는 경우가 있습니다. 하지만 이 알고리즘에서는 해당 경우를 즉각적으로 검출해내지 못하므로, 1을 빼주는 것입니다.

Ex) Input : [4, 3, 2, 1] (이 때 보기 쉽게 idx는 1, 2, 3, 4로 지정하겠습니다. 실제로는 0, 1, 2, 3)

for idx, num in enumerate(Input):

→ idx = 1, num = 4

→ idx != num이므로 4가 있어야 할 원래 위치(idx : 4)에 4를 입력하고, num을 1로 바꿔줍니다. [swap 횟수 = 1]

→ [4, 3, 2, 4], num = 1

→ num(=1)이 있어야할 원래 위치(idx : 1)의 숫자(=4)와 num(=1)을 비교합니다.

→ num(=1)이 있어야할 원래 위치(idx : 1)에 num을 입력하고, num을 4로 바꿔줍니다. [swap 횟수 = 2]

→ num(=4)이 있어야할 위치에 해당 숫자(4)가 위치해 있으므로 for loop을 벗어납니다.

이상 끝-!

https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

이번에 풀어본 문제입니다.

문제) 사람들이 일렬로 물건을 사기 위해 줄을 서있습니다. 이 때, 모든 사람들은 앞 사람들에게 돈을 주고 자리를 바꿀 수 있고, 특정 사람이 다른 사람을 매수할 수 있는 최대 횟수는 2회입니다.(즉, 자신의 자리보다 최대한 2칸까지 앞으로 갈 수 있습니다.) 숫자들의 List가 주어질 때, 매수가 일어난 최소 횟수를 구하시오.

[예시]

초기 상태 : [1, 2, 3, 4, 5]

최종 상태 : [2, 1, 5, 3, 4]

* 엄청나게 큰 Input이 테스트 항목에 있으므로, 단순히 풀기만 해서는 안됩니다.(여기서 많은 시간을 보냈습니다. 사실 답을 찾지 못해서 discussion에 들어가서 힌트를 얻었습니다 ㅠㅠ)

1. 방법

* (매수가 일어난 총 횟수) = (각각의 사람들이 매수당한 횟수의 총 합)

  -> 각 사람들이 매수당한 횟수는 특정 사람(x)보다 앞에 있지만 뒷번호를 가진 사람(y: y>x)을 찾으면 됩니다.

  -> 특정 사람의 순서(x)보다 뒷 번호를 가진 사람(y : y>x)은, 특정 사람의 원래 자리(x) 보다 1자리 앞(x-1)까지 갈 수 있습니다.(y : y≥x-1)

     (이 부분을 이해하는 것이 중요합니다. 뒤에 있던 사람이 매수를 하면 뒤에 있던 사람은 자리 (x)로 오게 됩니다.)

  -> 즉, 원래 특정 사람이 x에 위치해 있었고 현재 위치가 i라면, x-1부터 i-1까지 위치에 x보다 큰 숫자가 몇개 있는지 찾으면 됩니다.

코드는 매우 간단하므로 생략하겠습니다. -!

Weighted Mean을 구하는 문제입니다.

숫자 행렬 X = [1, 2, 3]

가중치 행렬 W = [4, 5, 6]

과 같이 행렬이 주어지면 Weighted Sum은 (1x0.1 + 2x0.2 + 3x0.3)/(4 + 5 + 6) 과 같이 구할 수 있습니다.

https://www.hackerrank.com/challenges/s10-weighted-mean/problem

https://www.hackerrank.com/challenges/30-nested-logic/problem

이번 문제는 Nested Logic입니다. 간단한 문제이지만 괜히 이상하게 푼 것 같습니다..

이 문제는 책을 반납받을 때 내야하는 연체료를 계산하는 문제였습니다. 

연체료를 내는 조건은 다음과 같습니다.

i) 반납 예정 일자 이전(혹은 당일)에 반납할 경우 0원

ii) 반납 예정 일자 이후에 반납할 경우 : 

  1) 같은 해, 같은 월에 반납할 경우 (연체된 일수 * 15)원

  2) 같은 해 다른 월에 반납할 경우 (연체된 월수 * 500)원

  3) 다른 해에 반납할 경우 10000원

변수 : 

  1) return_date_input : 입력 받은 반납 날짜 (Input Format은 'day month year'입니다.)

  2) expected_date_input : 입력 받은 반납 예정 날짜

  3) date_list : input들을 저장하는 list, string 을 가공하여 datetime 객체로 만든다.

  4) return_date : datetime Format로 변경된 반납 날짜

  5) expected_date : datetime Class로 변경된 반납 예정 날짜

방법 : 

  1) input을 datetime형식으로 변경하여 저장한다. (저는 연체 날짜가 1달을 넘어갈 경우 (연체된 달 * 500)이 아니라 (연체된 날짜 * 500)으로 이해해서 datetime형식으로 변환했습니다. 30일/31일/28일/29일 등 달마다 일의 개수는 다르니까요. 하지만 문제를 잘못 읽었었습니다.)

  2) return_date의 연/월/일, expected_date의 연/월/일 비교를 통하여 연체료를 계산한다.

이 때 주의해야 할 점은,

1) Input format에서 연도는 항상 4자리가 아니다.(Datetime 객체로 변환할 시 문제가 됩니다.)

2) 반납 날짜와 반납 예정 날짜의 연도 / 월이 다르지만 연체료를 내지 않는 경우도 있습니다.(1년 혹은 1달 이상 빨리 반납했을 경우)

이상 끝-!

https://www.hackerrank.com/challenges/30-running-time-and-complexity/editorial

이번에 푼 문제는 "소수(Prime Number) 여부 판별하기"입니다.

소수란, "1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수"를 의미합니다.

예를 들어, 2, 3, 5, 7, 11, 13....과 같은 숫자들이 있습니다.

특정 숫자를 Input으로 받을 때, 해당 숫자가 소수인지 아닌지를 판별하여,

맞다면 "Prime", 아니라면 "Not Prime"을 출력하면 됩니다.

* 소수 판별하기 : 

  저는 약간 다른 방향으로 접근해서 풀긴 했지만, 결국 같은 내용이므로 최적 알고리즘에 대해 설명하겠습니다.

시간과 공간을 고려하지 않는다면, n을 1부터 n-1까지의 수로 모두 나눠본 뒤 소수인지 아닌지를 판별할 수도 있습니다. 하지만 항상 시간과 메모리는 제한되어있기 때문에, 최적의 알고리즘을 찾아야 합니다.

  특정 숫자 n이 주어졌을 때, n은 소수가 아니라면 양의 정수 a,b의 곱으로 나타낼 수 있습니다. 이 때, a와 b는 동시에 루트 n보다 커질 수 없습니다. 두 수 모두 루트 n보다 클 경우, a*b > n 이 될 것이기 때문이죠.

이 조건을 활용하면,

i) a ≤ 루트 n

이라는 조건을 찾을 수 있습니다. 우리는 특정 수 n이 주어졌을 때, [1, 루트n] 범위 내의 숫자에 대해서 n의 인수인지 확인해보면 최종적으로 n의 소수 여부를 판별할 수 있습니다.

(이 때, a의 counterpart로 지정된 b에 대해서는 고려하지 않아도 됩니다. 아래 표와 같이, a*b나 b*a나 같으니까요.)

1. 변수

  1) bound : 주어진 숫자 a가 나눠지는지 확인해볼 숫자들의 범위(루트 n으로 지정하면 됩니다. 저는 조금 다른 방법으로 접근했으나 결국 같은 방법이었습니다.)

  2) count : 확인 횟수

2. 방법

  1) 루트 a보다 작은 숫자에 대해서 a가 나눠지는지 테스트해봅니다.

  * 이 때, 2는 별도로 걸러줘야 합니다. 2는 소수이기 때문입니다.

  ** 이 때, 2에 대해서 나눠지는지 여부를 먼저 확인하면 테스트해볼 범위의 수를 반이나 줄일 수 있습니다. 2로 나눠지는지 먼저 확인하고, 나눠지지 않는다면 홀수에 대해서만 테스트를 진행합니다.

이상 끝-!

https://www.hackerrank.com/challenges/30-linked-list-deletion/problem

이번에 풀어볼 문제는 Linked List 에서 중복된 Data를 가진 Node를 삭제하는 문제입니다.

이 때 Node들의 Data는 랜덤하게 배정된 것이 아니라(이렇게 되면 중복된 노드 중 어떤 노드를 삭제해야 할지 지정을 해주어야겠죠), Non-decreasing order로 연결되어 있습니다.

즉, 특정 노드의 Data ≤ 다음 노드의 Data 의 관계를 만족한다는 것입니다.

1. 변수

  1) target : 특정 노드를 지정해줍니다.

2. 방법

  1) target의 next node가 존재할 경우, 아래 작업을 반복합니다.

  2) target의 data와 target 다음 노드의 data 값을 비교하고, 같을 경우에는 target 노드에 다다음 노드를 연결해줍니다.

     (target.data 와 target.next.data를 비교, 같으면 target.next = target.next.next)

  3) 다를 경우에는 target = target.next를 진행합니다.(다음 노드에 대하여 위의 작업 반복)

이번 문제는 간단하게 끝났습니다. 이상 끝-! (보통 포인터에서는 할당된 메모리를 free해주었어야 하는데..이문제도 동일하게 해줘야하는지 또 찜찜한 기분이 들긴 합니다..)

https://www.hackerrank.com/challenges/30-binary-trees/problem

오늘 푼 문제는 그저께 생성하는 법을 배운 Binary Search Tree를 level 별로 출력하는 것입니다.

아래와 같은 그림이 주어지면, Level 0, Level 1, Level 2 순서로 node의 값들을 나열하면 됩니다.

즉, 아래의 Example에서는 3 2 5 1 4 7 의 순서대로 값을 출력하면 됩니다.

이번 문제는 회귀로 풀 수 없을 것 같아서 다른 방법을 적용했습니다.

(별로 안 좋은 방법 같아서 참고만 해주세요..ㅎ)

* 변수 : 

1) current_height : 출력할 Level에 있는 Node들을 담은 배열입니다.

2) next_height : 다음에 출력할 Level에 있는 Node들을 담은 배열입니다.

* 방법 : 

0. 초기화 : 

current_height = [root], next_height = []

while(current_height):

1. 입력받은 노드의 값을 출력한다.

2. 입력받은 노드의 왼쪽 / 오른쪽 Subtree 존재 여부를 확인한 뒤, next_height에 추가한다.

3. current_height = next_height으로 치환한다.

4. next_height = []으로 초기화한다.

이렇게 되면, current_height에 원소가 존재할 때까지 계속 출력을 하게 됩니다.

current_height은 next_height, 즉 current_height의 subtree들로 계속 업데이트가 되므로, 마지막 Level까지 출력을 계속하게 됩니다.

이 방법에서 문제가 될만한 소지는, while문의 조건을 계속 치환하여 변환한다는 점입니다.

뭔가 찜찜한 느낌이 계속 들지만....일단 돌아가니 문제를 푼 것 같습니다.

이상 끝-!