매일 성장하는 블로그

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문의 조건을 계속 치환하여 변환한다는 점입니다.

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

이상 끝-!

오늘 풀어본 문제는 Hackerrank의 Binary Search Tree 입니다.

기본 Tree의 구조 생성 및 Node의 정의는 코드로 짜져 있고, Tree의 Height을 구하는 문제였습니다.

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

Binary Search Tree란 다음과 같은 구조를 갖는 트리를 말합니다.

1. 특정 노드의 왼쪽 subtree는 특정 노드보다 작은 값을 갖는다.

2. 특정 노드의 오른쪽 subtree는 특정 노드보다 큰 값을 갖는다.

3. 모든 노드들은 Binary Search Tree이다.

즉 아래와 같은 그림에서는, Height 가 2가 됩니다. (※ Height를 2로 보는지 3으로 보는지는 사람마다 다른 것 같습니다. 문제에서는 Root Node를 Height에 포함시키지 않습니다. ※)

이 문제는 대충 감이 오는 것처럼, Recursive 구조를 활용합니다.

1) 특정 노드가 Null인 경우 -1을 반환합니다.(마지막에 다다랐을 때)

2) Left Subtree의 Height와 Right Subtree의 Height을 Recursive를 활용하여 구합니다.

3) Left Subtree의 Height와 Right Subtree의 Height를 비교하여, (더 큰 것 + 1)을 반환합니다.

이렇게 구하면 마지막에 Root Node를 구하게 되고, 초기 값 -1을 준 덕분에 이 문제에서 말하는 Height를 구할 수 있습니다.

이상 끝-!

이번엔 Hackerrank의 문제들을 풀어보기 시작했습니다.

일단 하나의 사이트 문제들이라도 마스터하고 다른 사이트의 문제들을 풀어야 하는데....흠 

Hackerrank의 문제들을 모두 푸는 것을 목표로 시작해보겠습니다.

문제 링크입니다.

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

문제 : 특정 문자열 X가 무한히 반복된 문자열 Y가 있다고 하자. 임의의 숫자 n이 주어질 때, Y의 첫번째 문자부터 n번째 문자까지 'a'가 포함된 횟수를 구하라.

* 변수

1) X의 길이 : x_len

2) n을 x_len으로 나눈 몫 : x_share

3) n을 x_len으로 나눈 나머지 : x_remainder

4) X 내에 포함된 'a'의 개수 : x_a

1) X 내에 포함된 'a'의 개수를 구한다.

2) n을 x_len으로 나눈 몫과 나머지를 구한다.(x_share, x_remainder)

3) (x_share * x_a) + (x_remainder 내의 'a'의 개수) 를 return한다.

성공적으로 코드가 돌아가는 것을 확인했습니다. 꾸준한 습관이 꼭 되었으면 좋겠네요 -!

이번 문제는 [프로그래머스 - 힙 - 디스크 컨트롤러] 입니다!

문제 링크 :

https://programmers.co.kr/learn/courses/30/lessons/42627

이전에 풀어봤던 라면공장 문제와 매우 비슷한데, 컴퓨터의 스케쥴러의 매우 간단한 구조를 구현하는 것입니다.
주어진 컨트롤러는 작업 요청이 들어온 작업들 LIST를 가지고 있고, 이 LIST에 있는 모든 작업들이 완료되었을 때,
평균 소요시간(작업완료시점 - 요청시점) 이 가장 짧아지는 작업 순서를 구하는 것이 문제입니다.

자세한 내용은 문제를 직접 보시는 것이 좋을 것 같습니다.

변수 : 

  1) t : 현재 시간

  2) jobs : 작업 list

  3) t_spent : 작업별 소요시간을 적은 list(순서대로 X)

  4) a_jobs : 특정 시점 t에서 수행 가능한 작업 list

방법 : 

  1) 현재 시점 t에서 수행 가능한 작업들을 찾아 a_jobs에 넣는다.

  2) 가장 짧은 작업시간을 가진 작업을 수행한다.(작업시간을 기준으로 Reverse Sort 후 pop)

  3) 현재 시간에 작업시간을 더한다.

  4) 소요시간을 t_spent에 넣는다.

  5) 더 이상 작업 리스트에 작업이 남아있지 않다면, a_jobs에 남은 작업들을 순차적으로 수행한다.

  6) t_spent의 평균을 구한 후 return한다.

이상 끝-!

이번 문제는 [프로그래머스 - 힙 - 라면공장] 입니다!

문제 링크 :

https://programmers.co.kr/learn/courses/30/lessons/42629

1. 변수 : 

  1) stock : 초기 재고량

  2) dates : 입고 가능 일자

  3) supplies : 입고 가능 수량(dates와 매치됨)

  4) k : 버텨야 하는 일수

2. 방법 : 

  1) dates, supplies를 역순으로 바꾼다.(pop(0) 대신 pop()을 활용하기 위해)

  2) 초기 재고량(stock)으로 버틸 수 있는 기간 내에 받을 수 있는 수량을 확인한다.(두번째 while문)

  3) 받을 수 있는 수량 중 가장 큰 것을 택하여 받는다.(가장 큰 것을 빼기 위해 -supplies 사용)

이상 끝-!

이번 문제는 [프로그래머스 - 힙 - 더 맵게] 입니다!

문제 링크 :

https://programmers.co.kr/learn/courses/30/lessons/42626

작년 말 카카오 코딩테스트에 나왔던 문제같은데....못 풀었던 것 같은 기억이 납니다.

힙 자료구조를 사용하니 매우 쉬운 문제였는데요...문제는 이 자료구조를 사용해야겠다!라는 생각이 잘 떠오르지 않는다는겁니다. 항상 많이 풀어보고 고민해봐야 하는 것 같습니다.

1. 변수 : 

  1) answer : 답

  2) scoville : 각 음식의 맵기 정도가 담긴 배열(즉, List의 길이는 주어진 음식의 수를 나타냅니다.)

  3) a = 가장 scoville 지수가 낮은 음식

  4) b = 두번째로 scoville 지수가 낮은 음식

2. 방법 : 

  1) 음식 리스트 중 가장 scoville 지수가 낮은 음식의 scoville 지수가 K보다 작은지 판별한다.  

    1-1) False : 낮은 scoville 지수를 가진 두 음식을 음식 리스트에서뽑아낸 뒤(a, b), 새로운 음식의 scoville 지수를 음식을 List에 추가한다.

    1-2) True : answer를 return한다.

  * 이 때 만약 음식 List의 길이가 1개에 다다랐다면, -1을 return해야 합니다. 이상 끝-!