IT-garden

문제 설명

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

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

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

제한조건

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

입출력 예

genresplaysreturn

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

나의 풀이

def solution(genres, plays):
    di=dict()
    r=[]
    for g,p in zip(genres,plays):
        if g in di.keys():
            di[g] += p
        else:
            di[g] = p

    dic=sorted(di.items(), key=lambda x: x[1], reverse=True)
    for k,v in dic:
        li=[]
        for i,(g,p) in enumerate(zip(genres,plays)):
            if k == g:
                li.append([p,i])
                
        li=sorted(li,key = lambda x: (-x[0],x[1]))
        r.append(li[0][1])
        if len(li) > 1:
            r.append(li[1][1])
                        
    return r

프로그래머스 '베스트앨범' : https://programmers.co.kr/learn/courses/30/lessons/42579

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한조건

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

나의 풀이

from collections import deque

def solution(begin, target, words):
    def bfs(s):
        de=deque()
        de.append(s)
        
        while de:
            x=de.popleft()
            if x == target:
                break
            
            for i in words:
                c =0
                for be, wo in zip(x,i):
                    if be == wo:
                        c += 1
                if c == len(x)-1 and di[i] == 0:
                    di[i]=di[x]+1
                    de.append(i)
                    
    di=dict()
    di[begin]=0
    for i in words:
        di[i]=0
    bfs(begin)
    try:
        if di[target] != 0:
            return di[target]
    except:
        return 0

1. words의 단어들을 딕셔너리에 담아주고 begin 단어로 bfs를 수행했습니다.
2. 한 개의 알파벳만 바꿀 수 있는지 확인하고 바꿀 수 있다면 바꾸고 딕셔너리의 value를 1 증가시켰습니다.
3. bfs 실행후에 target값이 words에 있고 value가 0이 아니면 거친 단계 과정의 수를 리턴하고 변환할 수 없다면 0을 리턴합니다.

프로그래머스 '단어 변환' : https://programmers.co.kr/learn/courses/30/lessons/43163

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한조건

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

나의 풀이

def solution(routes):
    r=0
    routes=sorted(routes)
    s=routes[0][1]
    routes=routes[1:]
    r += 1

    for i in routes:
        if i[0] <= s:
            s = min(i[1],s)
        else:
            s = i[1]
            r += 1

    return r

프로그래머스 '단속카메라' : https://programmers.co.kr/learn/courses/30/lessons/42884

문제 설명

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

제한조건

• 지방의 수는 3 이상 100,000 이하인 자연수입니다.
• 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.
• 총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.

입출력 예

나의 풀이

def solution(budgets, M):
    budgets.sort()
    s=1
    e=max(budgets)
    r=0

    while s <= e:
        mi=(s+e)//2
        c=sum([mi if i > mi else i for i in budgets])
        if M >= c:
            s=mi+1
            r=mi
        else:
            e=mi-1
    return r

백준알고리즘 - 2512번 예산 - 파이썬(Python)

위 문제와 동일문제입니다.

프로그래머스 '예산' : https://programmers.co.kr/learn/courses/30/lessons/43237

문제 설명

제한조건

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

나의 풀이

def solution(triangle):
    for i in range(1,len(triangle)):
        triangle[i][0] += triangle[i-1][0]
        triangle[i][-1] += triangle[i-1][-1]
        for j in range(1,i):
            triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])
    
    return max(triangle[len(triangle)-1])

백준알고리즘 - 1932번 정수 삼각형 - 파이썬(Python)

위의 문제와 동일한 문제입니다.

프로그래머스 '정수 삼각형' : https://programmers.co.kr/learn/courses/30/lessons/43105

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한조건

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

나의 풀이

from collections import deque

def solution(n, edge):
    def bfs():
        de=deque()
        de.append(1)
        
        while de:
            x=de.popleft()
    
            for i in a[x]:
                if ch[i] == -1:
                    ch[i]=ch[x]+1
                    de.append(i)
                
    a=[[] for i in range(n+1)]
    ch=[-1]*(n+1)
    
    for i,j in edge:
        a[i].append(j)
        a[j].append(i)
    
    ch[1]=0
    bfs()
    return ch.count(max(ch))

1. edge 배열을 통해 간선은 a 배열에 담습니다.
2. bfs를 1번 노드에서 시작하고 가장 멀리 떨어진 노드의 개수를 리턴합니다.

프로그래머스 '가장 먼 노드' : https://programmers.co.kr/learn/courses/30/lessons/49189