그냥 코딩하는 사람의 블로그

풀이 과정

1. 합계를 구하는 용인 딕셔너리(1)와, 각 장르별 노래를 저장할 딕셔너리(2)가 필요하다.

2. 각 장르의 합계를 구할 때 순차적으로 방문하며 딕셔너리를 사용하여 더하고, 합계를 구함과 동시에 장르별 딕셔너리에 해당 노래를 넣어준다.

3. (1)의 딕셔너리의 items를 사용하여 키,값을 모두 받아온 다음, 값별로 내림차순 정렬해 준다. 이 때 키에는 장르, 값에는 합계가 들어 있다.

4. (1)의 items를 순차적으로 방문하면서(내림차순), (2)의 딕셔너리를 (1)의 key를 사용해서 받아온다. 이 때 받아오는 리스트에는 (재생횟수, 인덱스)형식으로 들어있으므로 받아있는 리스트 역시 재생횟수로는 내림차순, 인덱스로는 오름차순으로 정렬해 준다.

5. 앞에서 2개까지만 answer에 저장해준다.

def solution(genres, plays):
    answer = []
    count_hash = {key:0 for key in set(genres)}
    list_hash = {key:[] for key in set(genres)}

    for idx, genre in enumerate(genres):
        count_hash[genre] += plays[idx]
        list_hash[genre].append([plays[idx], idx])

    temp = list(count_hash.items())
    temp.sort(key = lambda x:x[1], reverse=True)
    for key, _ in temp:
        cnt_list = list_hash[key]
        cnt_list.sort(key = lambda x:(-x[0], x[1]))
        for i, (_, idx) in enumerate(cnt_list):
            answer.append(idx)
            if i == 1: # 두개만
                break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 재귀 함수를 활용함.
2. i행 기준으로 모든 열을 탐색하면서 0~i-1행까지 존재하는 퀸들과 충돌하지 않는지 확인(같은 열이거나 대각선에 존재하거나)
3. (2)번이 통과한다면 현재 단계에서의 퀸을 리스트에 넣어준 후 다음 단계로 이동
4. 전체 행 진행하였다면 정답을 1 증가(answer)

answer = 0
def check(x1, y1, x2, y2):
    if abs(y2 - y1) == abs(x2 - x1):
        return True
    else:
        return False

def queen(current, row, n):
    global answer

    if row == n:
        answer += 1
        return

    for i in range(n):
        skip = False
        for x1, y1 in current:
            if y1 == i or check(row, i, x1, y1):
                skip = True
                break

        if not skip:
            queen(current+[[row, i]], row+1, n)

    return

def solution(n):
    global answer
    queen([], 0, n)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 칸에 도달 가능한 경우가 딱 두가지이다.

2. 하나는 타일을 세로로 배치하는 경우(dp[i-1])

3. 하나는 타일을 가로로 두개 배치하는 경우(dp[i-2])

4. 따라서, 현재 도달 가능한 케이스는 dp[i-1] + dp[i-2]를 하면 된다.5. 그냥 하면 수가 너무 커져서 런타임 에러가 나타나므로.. 매번 더할때마다 % 1000000007을 해주어야 함.

def solution(n):
    answer = 0
    dp = [0] * (n+1)
    if n == 1:
        return 1
    if n == 2:
        return 2
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
    answer = dp[n]
    return answer % 1000000007

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

1. 오른쪽과 아래로만 이동 가능하므로 점화식을 세우면..

   dp[i][j] = dp[i-1][j] + dp[i][j-1] 이다.

2. 단, 여기서 웅덩이가 있을 수도 있으므로 웅덩이는 따로 INT_MAX값을 넣어주어서 만약 현재 자기 위치 기준 왼쪽이나 위가 웅덩이라면 계산하지 않도록 처리해 준다.

3. 첫째 열/행은 일직선으로 가는 경우가 최단거리이므로 1로 처리하지만, 이때도 웅덩이를 만나게 된다면 break해주어야 한다.

4. 문제 자체가 일반적인 행,열 순서가 아닌 열,행 순서로 주어지기 때문에 헷갈림.

from collections import deque

def solution(m, n, puddles):
    answer = 0
    INT_MAX = int(10e9)
    dp = [[0] * m for _ in range(n)]

    for a,b in puddles:
        dp[b-1][a-1] = INT_MAX
    # initiate
    for i in range(m):
        if dp[0][i] == INT_MAX:
            break
        dp[0][i] = 1

    for i in range(n):
        if dp[i][0] == INT_MAX:
            break
        dp[i][0] = 1

    for i in range(1, n):
        for j in range(1, m):
            temp = 0
            if dp[i][j] == INT_MAX:
                continue
            if dp[i-1][j] != INT_MAX:
                temp += dp[i-1][j]
            if dp[i][j-1] != INT_MAX:
                temp += dp[i][j-1]
            dp[i][j] = temp


    answer = dp[n-1][m-1] % 1000000007

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

풀이 과정

1. dp를 활용하여야 효율성에서 통과 가능(탐색 X)

2. 현재 시점에서 이동 가능한 케이스가 두가지 있음. [i][j] -> [i+1][j], [i][j+1]

3. 따라서 맨 위에서 아래로 이동하면서 열 별로 현재 시점에서 이동 가능한 케이스 두가지를 이동하면서 누적합을 최댓값으로 계속 갱신해주는 방식으로 구현

import copy

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

문제 설명

풀이 과정

1. 플로이드 알고리즘을 통해 승리, 패배 시 가능한 최단 경로들을 모두 구해준다.

2. 각 선수의 케이스에서 승리해서 도달 가능한 선수의 수 + 패배해서 도달 가능한 선수의 수가 전체 선수의 수와 같다면 순위 지정이 가능하다.

3. 케이스의 수를 모두 세서 리턴해주면 된다.

def solution(n, results):
    answer = 0
    
    INT_MAX = int(10e9)
    win_matrix = [[INT_MAX] * (n+1) for _ in range(n+1)]
    lose_matrix = [[INT_MAX] * (n+1) for _ in range(n+1)]
    
    for i in range(n+1):
        win_matrix[i][i] = 0
        lose_matrix[i][i] = 0
    
    for src, dest in results:
        win_matrix[src][dest] = 1
        lose_matrix[dest][src] = 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                win_matrix[j][k] = min(win_matrix[j][k], win_matrix[j][i] + win_matrix[i][k])
                lose_matrix[j][k] = min(lose_matrix[j][k], lose_matrix[j][i] +
                                       lose_matrix[i][k])
    
    for i in range(1, n+1):
        count = len([k for k in win_matrix[i] if k != INT_MAX]) + len(
            [k for k in lose_matrix[i] if k != INT_MAX])
        if count == n+1:
            answer += 1
        
    
    
    return answer

문제 설명

풀이 과정

1. 문자열 두개를 비교하는 함수를 하나 만들어 줌(서로 다른 문자열의 개수가 단 한개여야 함)

2. begin을 시작점으로 최단 길이의 변환 과정이므로 bfs를 돌아줌. ( 서로 다른 문자열의 개수가 단 한개이고, 방문하지 않은 문자열 )

from collections import deque

def compare(a, b):
    count = 0
    for i in range(len(a)):
        if a[i] == b[i]:
            count += 1
    
    if count == len(a)-1:
        return True
    else:
        return False
    
def solution(begin, target, words):
    answer = 0
    
    visited = set()
    queue = deque()
    queue.append([begin, 0])
    visited.add(begin)
    while queue:
        wd,count = queue.popleft()
        if wd == target:
            answer = count
            break
        for word in words:
            if not word in visited and compare(wd, word):
                queue.append([word, count+1])
                visited.add(word)

    return answer

풀이 과정

1. 시간이 덜 걸리는 작업부터 처리하면 된다.

2. jobs를 도착시간 순으로 정렬한 뒤, 히프에 첫번째 작업을 넣어 준다.

3. 히프에 있는 작업들 중, 작업 시간이 가장 짧은걸 먼저 처리한다(작업 시간 기준으로 최소 히프)

4. 현재 시간 + 작업 시간 내에 도착한 작업들이 있다면 최소 히프에 넣어준다.

5. ★ 이때, 현재시간 + 작업시간 내에 도착하지 않고 이후에 도착하는 작업이 있을수도 있으니 해당 부분도 처리해주어야 한다.

import heapq

def solution(jobs):
    answer = 0
    heap = []

    jobs.sort()
    currentTime = jobs[0][0]; # 초기 작업의 시간으로 세팅
    jobidx = 1

    # 작업 시간을 기준으로 최소 히프 구성
    heapq.heappush(heap, [jobs[0][1], jobs[0][0]])

    while heap:
        # 현재 기준 최소 시간의 작업 가져옴
        jobtime, arrive = heapq.heappop(heap)
        currentTime += jobtime
        while jobidx < len(jobs):
            if jobs[jobidx][0] <= currentTime:
                heapq.heappush(heap, [jobs[jobidx][1], jobs[jobidx][0]])
                jobidx += 1
            else:
                break

        answer += (currentTime - arrive)

        if not heap and jobidx < len(jobs):
            currentTime = jobs[jobidx][0]
            heapq.heappush(heap, [jobs[jobidx][1], jobs[jobidx][0]])
            jobidx += 1


    answer = answer // len(jobs)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

1. 이분 탐색을 사용하는 문제이므로 "시간" 을 기준으로 left, right 설정. (right는 정답의 최대치여야 하므로 가장 오래 심사하는 심사관이 전체 인원을 심사할때로 설정)

2. 중간 시간(left + right // 2)일 때, 각각의 심사관이 몇명을 심사할 수 있는지 더해서 총 심사 가능한 인원수를 구함

3. 구한 값이 n보다 크거나 같다면 시간을 줄여야 하므로 right를 m-1로, 작다면 시간을 늘려야 하므로 left를 m+1로 대체함

4. 이 때, 구한 값이 n보다 크거나 같다면 answer에 따로 저장해 주어야 한다.

def solution(n, times):
    answer = 9999999999
    r = max(times) * n
    l = 0

    while (l <= r):
        m = (l + r) // 2
        tot = 0
        for time in times:
            tot += (m // time)        

        if tot >= n:
            answer = m
            r = m - 1
        else:
            l = m + 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 1번에서 시작하여 각각의 노드들에 대한 최단 경로를 구해준다(Dijkstra 알고리즘 사용)

2. 이번 문제에서는 간선의 가중치가 무조건 1이므로 따로 heap를 써줄 필요는 없으므로 deque 사용

3. 최단 경로중 거리가 가장 먼 경로의 개수를 구해주면 된다.

from collections import deque

def solution(n, edge):
    answer = 0
    INT_MAX = 99999999999
    queue = deque()
    distance = [INT_MAX] * (n+1)
    graph = [[] for _ in range(n+1)]

    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)

    distance[1] = 0
    queue.append(1)
    while queue:
        p = queue.popleft()
        for nx in graph[p]:
            if distance[nx] > distance[p] + 1:
                distance[nx] = distance[p] + 1
                queue.append(nx)

    distance[0] = 0
    mdistance = max(distance)
    answer = distance.count(mdistance)

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges