매일 성장하는 블로그

오늘 풀어본 문제는 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해야 합니다. 이상 끝-!

이번 문제는 [프로그래머스 - 스택/큐 - 주식 가격] 입니다!

문제 링크 :

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

이번 문제는 주식 가격을 예측..!!하는 것이 아니라 주식 가격이 최초로 떨어지기 전까지의 시간을 구하는 문제입니다!

주식 가격 변동을 나타낸 배열 [a, b, c, d, e]가 주어진다면 a보다 낮은 가격이 최초로 나타난 시점 까지의 길이 a', b보다 낮은 가격이 최초로 나타난 시점까지의 길이 b'....등등을 구해서 [a', b', c', d', e']의 배열을 반환하시면 됩니다.

문제는 매우 간단하죠! 풀이도 그리 어렵지 않습니다. (저와 같이 그냥 막 푸신다면..)

1. 변수 : 

  1) prices : 가격 변동을 나타낸 배열

  2) pr : 배열 prices의 길이

  3) standard : 가격 변동의 기준

  4) first_drop : 최초로 가격이 떨어진 시간까지의 길이

2. 방법 : 

  1) 기준이 되는 가격을 구한다. (standard)

  2) price의 가격 변동값들에 대하여 standard보다 낮은지 판단한다.

    2-1) True : 1초를 반환한다.

    2-2) False : first_drop에 1초를 더한다.

    2-3) IF문 : 만일 prices 배열의 맨 끝에 도달했다면, first_drop을 answer 배열에 추가한다.

  3) 마지막 가격은 하락할 일이 없으므로 answer에 0을 추가한다.

3. 후기 : 음...뭔가 생각나는대로 풀어서 풀긴 했는데 매우 찜찜한 문제입니다. 매우 비효율적으로 보인단말이죠....일단 풀긴 했으니 패스! 이상 끝-!

이번 문제는 [프로그래머스 - 스택/큐 - 다리를 지나는 트럭] 입니다!

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42583

문제는 다음과 같습니다.

위와 같이 다리 길이, 다리 허용 무게, 순서대로 지나가야 하는 트럭이 주어졌을 때, 총 걸리는 시간을 구하라!

모든 트럭의 속도는 1이며, 트럭은 배열에 주어진 순서대로 반드시 지나가야 합니다.

저는 다음과 같이 문제를 풀었습니다.

1. 변수 : 

  1) bridge : 다리에 올라가 있는 트럭을 나타낸 배열

  2) bridge_length : 다리의 길이

  3) weight : 다리 허용 무게

  4) truck_weights : 트럭의 무게를 지나야 하는 순서대로 나타낸 배열

2. 방법 : 

  1) bridge 생성, bridge에 올라가야 하는 첫번째 트럭 삽입 (bridge[-1])

  2) 다리 위에 한대의 트럭이 더 올라갈 수 있는지 확인

    2-1) True : 트럭을 새로 삽입

    2-2) False : 다리 위의 트럭들을 한칸 왼쪽으로 이동시킴

  3) 더 이상 다리 위에 올라갈 수 있는 트럭이 없는 경우 마지막 트럭이 빠져나올 때까지의 시간을 구한다.

3. 후기 :

위와 같은 방법으로 문제를 풀어 아래와 같은 코드를 작성하였습니다.

다만, 아래와 같은 방법은 간신히(성공했다, 실패했다를 반복합니다.) 시간 Limit를 통과했는데요, 이유는 pop(0)때문입니다. 리스트에서 pop(0)을 하게 되면, 0번째 요소를 빼낸 뒤 나머지 요소들의 index를 재배열하는 과정을 거치게 됩니다. 따라서 pop(0)은 매우 지양해야 하는 방법입니다. 

→ truck_weights를 거꾸로 재배열 한 뒤, pop을 사용하는 방법이 훨씬 효율적으로 사용하는 방법입니다. 참고하세요.(제 코드는 정말 허접하게 푼거라 부끄럽네요..) 이상 끝-!

이번주에 푼 문제는 [프로그래머스 - 스택/큐 - 기능개발] 문제입니다.

한동안 골치를 썩였는데 문제를 생각하니 참 ....어리석었다는 생각이 듭니다.

애초에 알고리즘을 설계할 때부터 제가 잘못된 것을 몰라서 오래 걸렸네요.

(다른 사람들의 답에 또 감탄을 합니다..)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586

언뜻 보면 매우 간단한 문제지만 생각해야 될 부분이 2가지정도 있습니다.

1. 남은 시간 배열 만들기 : 저같은 경우에는 매우 어렵게 만들었습니다. 남은 양을 speed로 나눈 뒤 반올림을 했죠.

여기서 잘하시는 분들의 풀이를 보니 힌트를 얻은 부분은! -10 // 3은 -4라는 점입니다. 오랜만에 생각났습니다... 제 기억으로는 나머지는 무조건 양수가 되어야 하므로 -10 = 3 * -4(몫) + 2(나머지) 가 됐던 것 같습니다. 이를 활용하시면 더욱 쉽게 남은 시간 배열을 만들 수 있습니다.

2. 남은 시간 비교하기 : 처음 제가 문제를 풀지 못했던 이유는 배열의 각 요소를 다음 요소와(만) 비교하는 것을 계속 반복했기 때문이었습니다... 예를 들어, [50일, 25일, 3일, 24일] 이렇게 남은 시간을 구한 경우에는 다음과 같은 과정을 겪는다고 생각했습니다.

1) 50일 > 25일이므로 첫번째와 두번째 배포는 같이 이루어진다.

2) 25일 > 3일이므로 두번째와 세번째 배포는 같이 이루어진다.

3) 3일 > 24일이므로 앞의 3가지 배포는 이루어진다.

4) 24일 걸리는 배포가 혼자 마지막으로 이루어진다.

→ 답은 [3, 1] ! 이라고 생각했던 제가 바보였죠..

1) 50일 > 25일이므로 첫번째와 두번째 배포는 같이 이루어진다.

2) 50일 > 3일이므로 두번째와 세번째 배포는 같이 이루어진다.

3) 50일 > 24일 일이므로 4가지 배포는 모두 한번에 이루어진다.

→ 답은 [4] !입니다.

즉, 미루어진 프로그램 배포 중에 가장 긴 시간이 걸리는 것과 비교해야 하는 것을 망각하고 있었습니다.. 혹시나 막히시는 분이 계시다면 이 점을 생각하시고! 답은 보지 마시고 한 번 다시 풀어보세요. 이상 끝 -!