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

문제 설명

풀이 과정

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

풀이 과정

1. math.gcd 함수는 존재하지만 math.lcm 함수는 없어서 lcm 함수를 만들어 줌.

2. a * b = gcd * lcm인걸 활용하여 lcm 함수를 만들어준 다음 첫번째 요소에서부터 순차적으로 갱신하면서 lcm을 구해주면 된다.

import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

def solution(arr):
    answer = arr[0]
    for i in range(1, len(arr)):
        answer = lcm(answer, arr[i])

    return answer

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

풀이 과정

1. 순차적으로 접근하면서 문자열의 첫번째를 숫자인지 알파벳인지 체크

2. 숫자가 아니라면 첫번째 대문자, 맞다면 그대로 저장

3. 나머지 문자열들은 소문자로 변환하여 저장

4. 공백(" ") 만날 시 저장 및 문자열 초기화

def solution(s):
    word = False # 문자열 상태 저장
    answer = ''
    for i in s:
        if not word: # 첫번째 자리
            if i.isdigit(): # 첫번째 자리가 숫자
                answer += i
                word = True
            elif i == ' ': # 공백(첫번째 자리가 아님)
                answer += i
                continue
            else: # 첫번째 자리가 알파벳
                answer += i.upper() # 대문자
                word = True
        else:
            if i == " ":
                answer += i
                word = False
            else:
                answer += i.lower()


    return answer

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

풀이 과정

1. numpy의 matmul 함수를 활용하여 행렬의 곱셈 수행

2. matmul 함수 활용하기 위해 리스트를 np.array로 변환하는 과정 필요

3. numpy array를 list로 변환하기 위해 tolist 함수 사용

import numpy as np

def solution(arr1, arr2):
    a1 = np.matmul(np.array(arr1),np.array(arr2))
    answer = a1.tolist()
    return answer

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

풀이 과정

1. split과 map을 활용하여 정수형 리스트로 변환

2. 리스트 정렬후 0번째 ,-1번째 합쳐서 리턴(최소, 최댓값)

def solution(s):
    answer = ''
    p = list(map(int, s.split()))
    p.sort()
    answer = str(p[0]) + ' ' + str(p[-1])

    return answer

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