모서리 IT 블로그

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

내 문제풀이

1. scoville과 같은 내용을 갖는 heapq를 생성한다.
2. heap의 첫번째 원소(가장 작은 값)가 K보다 작을 때까지 반복한다.
3. 반복할 때마다 answer+1을 해주고 스코빌 계산 결과를 heap에 추가한다. 이 때 heappop()을 사용해서 값을 꺼내는 동시에 heap에서 삭제한다.
4. heap의 첫 원소가 K보다 같거나 커지면 answer를 return. 그 전에 heap의 길이가 1이 되면 스코빌 지수를 K 이상으로 만들 수 없는 경우이기 때문에 -1을 return.

내 코드 - 파이썬

import heapq

def solution(scoville, K):
    answer = 0
    heap = []
    for i in scoville:
        heapq.heappush(heap, i)
    
    while(heap[0] < K):
        if len(heap) == 1:
            return -1
        answer += 1
        heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap)*2)
        
    return answer

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.
예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

내 문제풀이

1. 프린트 된 문서를 저장할 리스트(printer)를 생성한다.
2. 아무 문서도 프린트하지 않은 상태에서, 가장 중요도가 높은 문서를 먼저 프린트하여 초기화 작업을 한다.
   - 프린트 작업 : 해당 문서의 index를 printer에 저장하고, priorities에서 중요도는 임의의 최솟값(-1)로 수정
3. location이 printer에 있을 때(프린터 된 경우)까지 무한 루프를 돈다.
4. priorities의 index를 +1씩 증가시키며 중요도 최댓값과 일치하는지 비교한다. index가 (priorities길이-1)일 때까지만 +1을 한 후 넘어가는 경우 0으로 재설정하여 반복한다.
5. 중요도 최댓값과 일치하는 경우 위의 프린트 작업을 수행하고 answer+1을 해준다.

내 코드 - 파이썬 

def solution(priorities, location):
    answer = 1
    printer = [] # 프린트 된 문서 index 
    
    # 초기화 작업 : 중요도 가장 높은 문서의 index를 printer에 저장
    idx = priorities.index(max(priorities))
    printer.append(idx)
    # 대기목록에서는 중요도를 임의의 최소값(-1)으로 변경
    priorities[idx] = -1
    
    while(1):
        # 요청 문서 index가 프린트 된 경우
        if location in printer:
            return answer
        
        # 중요도 최댓값 계산
        top_pri = max(priorities)
        
        # index를 +1씩 추가하며 중요도 최댓값과 같으면 인쇄
        if idx+1 <= len(priorities)-1: idx += 1
        else: idx = 0            
        if priorities[idx] == top_pri:
            answer += 1
            printer.append(idx)
            priorities[idx] = -1
    
    return answer
   

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

내 문제풀이

1. 다리 위의 트럭을 표현하는 list(bridge)를 생성한다. 길이는 다리 길이, 값은 0으로 초기화를 해둔다.

2. bridge 길이가 0이 되기 전까지 반복문을 실행한다. 이 때 소요 시간(answer)과 다리 위 트럭의 합산 무게(weight_sum)를 계산한다. while문을 시작할 때마다 answer은 +1, weight_sum은 bridge의 가장 마지막 무게를 뺀다.

3. 대기 트럭이 있다면, weight_sum + 대기 트럭 중 가장 앞에 있는 트럭 무게와 다리가 견딜 수 있는 무게를 비교한다. 다리가 견딜 수 있는 무게가 더 크거나 같다면,
- weight_sum에 대기 트럭 중 가장 앞 트럭 무게를 더하고
- bridge에 해당 트럭을 추가한다.

4. 다리가 견딜 수 있는 무게가 더 작다면, bridge에 0을 추가한다. 아무런 트럭이 올라가지 못한 것으로 취급한다.

5. 다리 위 트럭이 모두 빠져나갈 때까지의 시간을 계산해야 하기 때문에 대기 트럭이 없더라도 계속해서 bridge의 값을 제거해야 한다. bridge가 모두 비어버리면 그 때 while문이 종료된다.

내 코드 - 파이썬

def solution(bridge_length, weight, truck_weights):
    answer = 0
    weight_sum = 0
    bridge = [0]*bridge_length
    
    while(len(bridge)):
        answer += 1
        weight_sum -= bridge.pop(0)
        
        if(len(truck_weights)):
            if(weight_sum + truck_weights[0] <= weight):
                    truck = truck_weights.pop(0)
                    bridge.append(truck)
                    weight_sum += truck
            else:
                bridge.append(0)
        
    return answer

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

내 문제풀이

1. 앞 작업부터 소요 시간을 저장해두고, 이를 기준으로 반복문을 통해 뒷 작업의 소요 시간과 비교한다. 가장 첫 작업에서는 반복문 수행 전에 초기화를 해두고, 반복문을 1~작업 길이까지 수행한다.
2. 저장한 소요 시간보다 뒷 작업 소요시간이 작거나 같으면 한 배치에 배포할 수 있는 작업 수(count)를 증가시킨다.
3. 저장한 소요 시간보다 뒷 작업 소요시간이 크면 이전까지 증가시킨 count 값을 answer에 저장하고 count와 작업 소요 시간을 다시 설정한다.
4. 반복문이 끝나면 마지막으로 계산했던 count를 answer에 저장한다.

내 코드 - 파이썬

from math import ceil

def solution(progresses, speeds):
    answer = []
    # old_date : 현재 작업까지 가장 긴 소요 시간
    # 첫번째 작업 기준으로 초기화
    old_date = ceil((100-progresses[0])/speeds[0])
    count = 1
    
    for idx in range(1, len(progresses)):
        # 현재 작업 소요시간이 old_date보다 작거나 같은 경우
        if ceil((100-progresses[idx])/speeds[idx]) <= old_date:
            count += 1
            continue
            
        # 현재 작업 소요시간이 old_date보다 큰 경우
        else:
            answer.append(count)
            count = 1
            # old_date 현재 작업 기준으로 다시 계산
            old_date = ceil((100-progresses[idx])/speeds[idx])
            
    # 마지막 작업에서 append를 못하므로 마지막 count를 추가
    answer.append(count)
    
    return answer

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

내 문제풀이

1. prices길이 -1 만큼 반복문을 돌면서, 현재 주식 가격과 이후의 주식 가격들을 비교한다. 이 때 이중 for 문을 사용한다.
2. 현재 - 이후 주식 가격을 한 번 비교할 때마다 count를 1씩 증가시킨다.
3. 어떤 이후 주식 가격이 현재 주식 가격보다 낮아진 경우 반복문을 중단시키고 answer에 count(가격이 떨어지지 않은 초)를 저장한다.
4. 가장 마지막의 주식 가격은 항상 count(가격이 떨어지지 않은 초)가 0이므로 마지막에 answer에 0을 추가한다.

내 코드 - 파이썬

def solution(prices):
    answer = []
    
    for cur_idx in range(0, len(prices)-1):
        count = 0
        for next_idx in range(cur_idx+1, len(prices)):
            count +=1 
            if prices[cur_idx] > prices[next_idx]:
                break
        answer.append(count)
    answer.append(0)
    
    return answer

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

내 문제 풀이

- genre와 plays 같은 index 값 = 같은 노래 이다.
1. 장르 별 전체 plays 계산한다.
2. 장르 별 전체 plays 기준으로 내림차순 정렬한다. (문제 조건 1)
3. 장르 하나마다 반복문 수행하며 해당 장르 노래의 index 값을 알아낸다. 이 index를 사용해서 노래 별 plays를 top_song 리스트에 저장한다.
4. 해당 장르의 노래가 2개 미만이라면, 해당 plays를저장한다.
5. 해당 장르의 노래가 여러 개라면, plays 기준으로 내림차순 정렬 후 앞 2개의 plays를 저장한다. 이 때 index()는 리스트 앞 부분부터 찾기 때문에 중복된 plays가 있는 경우, 첫 번째로 저장한 노래의 고유 번호를 중복해서 answer에 저장하지 않기 위해 임의로 -1 값으로 변경해준다.

Collections.defaultdict

객체마다의 카운트 갯수를 알고 싶을 때 collections.Counter 말고 Collections.defaultdict를 사용할 수 있다. key-value 형태의 dictionary 형태로 저장할 수 있다. 
또한 정렬을 할 때에는 sort()를 사용할 수 없고 대신 sorted()를 사용한다.

내 코드 - 파이썬

from collections import defaultdict

def solution(genres, plays):
    answer = []
    
    song_count = defaultdict(int)
    for idx in range(0, len(genres)):
        song_count[genres[idx]] += plays[idx]
    # -----------------> genre별 전체 play count 완료
    
    song_count = sorted(song_count.items(), key=lambda x:x[1], reverse=True)
    # defaultdict는 sort() 사용 불가능
    
    # 상위 장르 순서대로 반복
    for sc in song_count:
        # 현재 장르 index(노래)의 plays 저장
        top_song = []        
        for idx in range(0, len(genres)):
            if genres[idx] == sc[0]:
                top_song.append(plays[idx])
                
        # 노래가 한 개일 때
        if len(top_song) < 2:
            answer.append(plays.index(top_song[0]))
        
        # 노래가 여러 개일 때
        else:
            # plays 수를 내림차순 정렬 
            top_song.sort(reverse=True)
            answer.append(plays.index(top_song[0]))
            plays[plays.index(top_song[0])] = -1
            answer.append(plays.index(top_song[1]))

    return answer

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

내 문제 풀이

1. 의상 종류 별 의상 이름 갯수를 센다.
2. 전체 조합 계산 = (n+1) * (m+1) * ... 을 활용하여 의상 종류 별 의상 이름 갯수를 모두 곱한다.
3. 최소 한 개의 의상은 입어야 하므로 아무것도 입지 않을 경우를 제외하고 return. (2번 결과의 -1)

collections.Counter

동일한 값의 갯수를 count 해주며 dictionary 형태로 반환된다. 
Counter('abcaab')을 수행할 경우 Counter({'a':3, 'b':2, 'c':1})이 return 된다.

내 코드 - 파이썬

from collections import Counter

def solution(clothes):
    answer = 1
    

    counter = Counter(cloth[1] for cloth in clothes)
    for a, b in counter.items():
        answer *= (b+1)
    
    return answer-1

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예제

내 문제 풀이

1. phone_book을 정렬한다.(오름차순, 내림차순 상관 없음.)
2. phone_book 기준으로 반복문을 수행한다. 반복 횟수는 phone_book 길이 -1.
3. 반복문을 수행하며 현재 index의 전화번호가 바로 뒤 index의 전화번호에 포함되는지 확인한다.
4. 포함되는 된다면 바로 False를 return.
5. 반복문이 끝날 때까지 return이 되지 않으면 서로 접두사인 전화번호가 없다는 것이므로 True를 return.

내 코드 - 파이썬

def solution(phone_book):
    phone_book.sort()
    
    for idx in range(0, len(phone_book)-1):
        if phone_book[idx] in phone_book[idx+1]:
            return False
        
    return True