매일 성장하는 블로그

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

문제 링크 :

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] !입니다.

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

안녕하세요. 이번엔 [프로그래머스 - 코딩테스트 - 스택/큐 - 탑] 문제를 풀어보았습니다.

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

저의 풀이 방법은 아래와 같습니다.

* Input : 각 탑의 높이를 기록한 배열
* Output : 해당 위치의 신호를 수신한 탑의 위치를 기록한 배열

1. 오른쪽부터 하나씩 뽑는다.
2. 해당 인자와 가장 가까운 위치에 있는 해당 인자보다 높은 탑을 찾는다.
  2-1) 타겟 높이를 기록한다. 
  2-2) 하나씩 index를 왼쪽으로 가면서 타겟 높이와의 높이값을 비교한다
3. 높은 탑을 찾으면 answer에 기록한다.

뭐 난이도가 2인만큼 푸는건 어렵지 않지만 언제나 느끼듯 기본 라이브러리를 활용하여 쉽게 푸시는 분들이 참 많은 것 같아요. 더 간단한 답을 원하시면 range()함수를 한번 활용해보세요!

이번 문제는 [프로그래머스 - 코딩테스트 - 스택/큐 - 프린터] 문제입니다.

문제의 규칙은 아래와 같습니다.

* INPUT : 인쇄 대기목록, 목표문서의 Index

* Output : 목표문서의 출력 순서

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.

좀 더 고차원적으로 생각하여 문제를 풀어보고자 하였지만 답을 찾을 수 없어서...

그냥 주어진 문제 그대로 구현하였습니다. 

이번엔 스택/큐의 쇠막대기 문제 풀이입니다.(사실 저는 문제를 풀지 못했습니다..)

스택/큐에 관한 간단한 소개와 코드 설명입니다.

* Stack과 Queue

1) Stack : LIFO의 데이터 구조, 이름 그대로 데이터를 순서대로 쌓는다. 데이터를 추출(삭제)할 때는 맨 위에서부터(마지막에 들어간 데이터) 뽑는다.

2) Queue : FIFO의 데이터 구조, 한쪽에서는 데이터의 삽입만, 한쪽에서는 데이터의 추출(삭제)만 가능하다.

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

저의 접근 방식은 아래와 같습니다.

# 목표 : 주어지는 String의 처음부터 끝까지 각 괄호의 짝을 찾고, 그 안의 레이저 수를 구해서 쪼개지는 막대기의 수를 구한다.

# 방법 : 

1. 레이저를 의미하는 '()'는 모두 '.'으로 replace한다.

2. 막대기의 시작을 의미하는 '('를 찾고, 시작과 Match되는 막대기의 끝 ')' 을 찾는다. 

3. 막대기의 시작과 끝 사이의 레이저 수를 세서 쪼개지는 막대기의 수를 구한다.

→ 2,3번의 기능을 하는 것이 count_pieces()함수입니다.

4. 쪼개진 막대기의 총합(count)을 구한다.

결과적으로 테스트 케이스 20개 중에서 19개는 성공했지만, 1번은 통과하지 못했습니다. 도저히 이유를 모르겠어서 답을 보고 말았는데, 아직도 안되는 이유는 잘 모르겠습니다. 신박한 답들이 많으나 꼭 자신만의 답을 찾아보시면 좋을 것 같습니다!(저는 못했..)

유명한 국내 코딩 문제 사이트로는 백준, 프로그래머스가 있습니다.

우선 1차 목표로 프로그래머스의 코딩테스트 문제들을 풀어볼 예정입니다.

코딩테스트 # 해시 문제 4번

장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 만들어라.
주어지는 데이터 : genres[], plays[]

genres[] : i번째 노래의 장르
plays[] : i번째 노래의 play 수

규칙
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

* 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.

베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 

#문제풀이

→ 필요한 것 : 장르별 재생횟수 및 순서, 장르 내 재생횟수가 많은 순서

주어진 데이터(genres[], plays[])는 Direct Addressing Table 방식으로 정리되어 있다. 

ex) genres = ["classic", "pop", "classic", "classic", "pop"]       plays = [500, 600, 150, 800, 2500]

1. 장르 종류를 파악하여 이를 저장하는 배열을 만든다.

→ ex) ['classic', 'pop']

  -classic은 0번, pop은 1번으로 활용한다.

2. 장르별로 배열을 만든 뒤, 각 장르 배열에 [곡 번호, 재생 횟수]를 저장한다.  

→ ex) [[[0, 500], [2, 150], [3, 800]], [[1, 600], [4, 2500]]]

  classic을 뜻하는 0번째 배열에는 3개 곡의 [곡 번호, 재생 횟수]가, pop을 뜻하는 1번째 배열에는 2개 곡의 [곡 번호, 재생 횟수]가 저장된 것을 볼 수 있다.

3. 2번을 수행하는 과정에서 장르별 재생 횟수도 모두 합하여 별도의 배열에 저장한다. 

→ ex) [[0, 1450], [1, 3100]]

  [장르 번호, 총 재생횟수] 순으로 저장한다. classic 곡들은 총 1450번, pop 곡들은 총 3100번 재생된 것을 볼 수 있습니다.

4. 장르별 배열을 재생횟수 순으로 정렬한다.

→ ex) [[[3, 800], [0, 500], [2, 150]], [[4, 2500], [1, 600]]]

5. 장르별 총 재생횟수를 정렬한다.

→ ex) [[1, 3100], [0, 1450]]

총 재생횟수가 높은 장르의 순서는 1(pop), 0(classic)으로 정렬되었다.

6. 재생횟수가 많은 장르별로 2개씩 뽑아 인덱스로 이루어진 리스트 만든다.

→ ex) [4, 1, 3, 0]

이 때 각 장르 배열별로 2곡씩만 뽑아야하며, 1곡만 있는 장르의 경우 1곡만 담아야 한다는 점을 명심해야 한다.

필요하시면 댓글로 말씀해주시면 부족한 코드라도 보내드리겠습니다.

* 해쉬

임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것.
기존 자료구조 -> 탐색이나 삽입에 선형적인 시간이 걸림
해쉬 : 탐색이나 삽입 시 위치를 바로 찾을 수 있음

* 해쉬 방식

1. Direct Addressing Table : (Key - Value) 쌍의 데이터 중의 Key 값을 배열의 인덱스로 
사용한다. Key 값이 400인 값이 존재한다면, 400 이전의 값들은 모두 Null 처리하고, 인덱스가 400
인 곳에 Value값을 저장할 수 있다. 단점은 저장을 위해 할당되는 배열의 크기가 Key 값의 최대값과
일치한다는 점이며, (Key - Value)쌍의 데이터가 적을 경우 공간이 낭비될 확률이 높다.

2. Hash Table : Key값을 함수를 통해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 사용한다.
H(k)라는 해쉬 함수를 만든 후, Key 값을 넣어서 결과값인 H(k)를 배열의 인덱스로 사용한다. H(k)
값은 0부터 배열의 크기 -1 사이의 값을 가진다. H(k)를 k의 해쉬값이라고 한다. Direct Addressing
Table에 비해 공간 낭비가 적지만, h(k)값이 중복(충돌)될 수 있으므로 유의해야 한다.
이를 위해 Chaining 등의 방법을 사용한다.