2023.01.15 코딩 테스트 공부 기록 입니다.

프로그래머스 : 다리를 지나는 트럭

🤡다리를 지나는 트럭 (Lv.2)

🤑풀이

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_queue = deque(truck_weights)
    bridge_queue = deque([0 for i in range(bridge_length)])
    bridge_remain_weight = weight
    sum_outweight = sum(truck_weights)
    
    time = 0
    while sum_outweight > 0 :
        time += 1
        # 다리 -> 나가는 차
        out = bridge_queue.popleft()
        sum_outweight -= out
        bridge_remain_weight += out
        
        # 대기하는 차 -> 다리
        # 들어갈 차 있는지 확인
        if len(truck_queue) > 0 :
            # 다리가 차를 받을 수 있는지 확인
            in_bridge = truck_queue[0]
            if bridge_remain_weight >= in_bridge :
                bridge_remain_weight -= in_bridge
                bridge_queue.append(in_bridge)
                truck_queue.popleft()
            else :
                bridge_queue.append(0)
        else :
            bridge_queue.append(0)
    return time

👩‍🏫 아이디어

1. 조건이 있는 FIFO 구조 파악.(queue 자료구조 사용)
   • 조건 1. 다리에 들어갈 차가 있는지 확인
   • 조건 2. 다리에 잔여 하중이 있는지 확인
2. 다리에서 나온 차의 누적 무게를 통해 모든 차가 나왔는지 여부 확인.
   • 위 조건(조건1, 조건2)에 만족하지 않는다면, 차가 들어가지 않는다는 표시를 0을 넣어서 우회

프로그래머스 : 숫자게임

🤡숫자게임 (Lv.3)

🤑풀이

from collections import deque
def solution(A, B) :
    A.sort()
    A = deque(A)
    B.sort()
    score = 0
    for b in B :
        if b > A[0] :
            A.popleft()
            score += 1
    return score

👩‍🏫 아이디어

1. A를 좌표상의 점으로 생각하고, B는 A보다 큰 위치에 분배하는 개념으로 접근.

   • A의 순서는 상관없어짐.
   • A 오름차순 정렬

2. 결과 값은 "점수" 이기 때문에 누가 누굴 이겼는지는 중요하지 않음. 이기는 횟수만 고려.

• 첫번째 A의 원소를 B의 작은 값으로 이기는 것이 가장 높은 점수를 받을 수 있음.
• B 오름차순 정렬

3. B를 순회하며, A의 첫번째 원소와 비교.

• 크다면 A[0] 제거, score += 1
  + 제거 당시 FIFO 구조 사용. (queue 자료구조 채택)
• 같거나 작다면 다음 B와 A[0]를 비교

프로그래머스 : 베스트앨범

🤡베스트앨범 (Lv.3)

🤑풀이

def solution(genres, plays) :
    ans, hash, genre_play = [], {}, []
    
    # genre별 정보와 전체 play 정보를 담은 hash 생성
    for i in range(len(genres)) :
        hash[genres[i]] = hash.get(genres[i], {'info' : [], 'sum' : 0})
        hash[genres[i]]['sum'] += plays[i]
        hash[genres[i]]['info'].append([i, plays[i]])
    
    # genre, 장르별 전체 play 정보을 담은 리스트 생성
    for genre in hash.keys() :
        genre_play.append([hash[genre]['sum'], genre])
    
    # 장르별 전체 play 정보를 기준으로 내립차순 정렬
    genre_play.sort(key = lambda x : x[0], reverse=True)
    
    # 장르마다, play가 높은 순서대로 정답에 입력, 개수가 1개일 때도 고려.
    for _, genre in genre_play : 
        hash[genre]['info'].sort(key =lambda x : x[1], reverse=True)
        ans.append(hash[genre]['info'][0][0])
        if len(hash[genre]['info']) > 1 :
            ans.append(hash[genre]['info'][1][0])
            
    return ans

👩‍🏫 아이디어

1. hash 테이블을 생성하여 genre별로 정보를 관리.
2. 문제에 주어진 조건대로 구현.

프로그래머스 : 기지국 설치

🤡기지국 설치 (Lv.3)

🤑풀이

from collections import deque

def solution(n, stations, w) :
    installed = deque(stations)
    step = -w  
    answer = 0
    while step < n-w :
        step += 2*w+1  
        if len(installed) > 0 :
            if step < installed[0] : 
                answer += 1
            elif step == installed[0] : 
                installed.popleft()
            else :
                step = installed.popleft()
        else :
            answer += 1
    return answer

👩‍🏫 아이디어

1. 반복되는 패턴을 파악.
   • 연산은 컴퓨터가 하므로 반복되는 패턴을 찾아주는 것이 중요.
   • 내가 찾은 패턴은 "이동" & "조건 고려" 이 두가지가 반복된다는 것.
     • 어떻게 이동해야 하는가.
     • 어떤 조건으로 고려해야 하는가.
2. 시작점을 0으로 고정할 필요가 없다.
   • 보통 시작점은 0으로 설정한 경우가 많았음.
     하지만, 위의 반복되는 패턴을 적용하기 위해 $step = -w$ 부터 시작하고 while문 안에서 $2 \times w+1$ 를 더해줘 실제 시작은 $step=w+1$ 이도록 설정.