매일 성장하는 블로그

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

문제 링크 : 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 등의 방법을 사용한다.