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

풀이과정

1. 시간을 초단위로 모두 바꾸어 준다.
2. 전날 -> 오늘로 넘어오는 케이스도 있으므로 완료시간(초)에 + 4 해준다.
3. 완료시간으로 시작시간을 구해준다. - 시작 시간 = 완료시간 - 처리시간 + 0.001
4. 시작 시간 기준으로 정렬을 해준다.
5. 시작 시간을 기준으로 반복문을 돌면서, 최소 히프에 완료 시간을 기준으로 넣어준다.
   • 넣어준 다음, 현재 시간 + 1 기준으로 끝난 작업들은 히프에서 빼준다.
6. 히프에 남아있는 요소들의 개수가 현재 겹치는 작업들을 의미하므로 answer을 갱신해준다.

소스 코드

import heapq
import math
def convert_second(s):
    hour = int(s[0:2])
    minute = int(s[3:5])
    second = int(s[6:8])
    msecond = int(s[9:]) / 1000
    return 4 + 3600 * hour + 60 * minute + second + msecond


def solution(lines):
    answer = 0
    cv_list = []
    for line in lines:
        temp = line.split()
        end = convert_second(temp[1])
        start = round(end - float(temp[2][:-1]) + 0.001, 3)
        cv_list.append([start, end])

    cv_list.sort()

    heap = []
    for start, end in cv_list:
        heapq.heappush(heap, [end, start])
        while heap:
            if heap[0][0] + 1 <= start:
                heapq.heappop(heap)
            else:
                break
        answer = max(answer, len(heap))

    return answer

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

풀이 과정

1. play_time, adv_time, log를 모두 초단위로 변경
2. log의 시작시간엔 +1, 종료시간엔 -1
3. 누적합을 구함 => 현재 시점에서의 시청자 수
4. 다시 누적합을 구함 => 현재 시점까지의 시청자 수 누적합
5. 전체 구간에서 가장 누적 재생시간이 긴 시작시간을 찾으면 된다.
   • (a, b) 구간의 누적합 = 누적합[b] - 누적합[a]

소스 코드

def convert(time):
    return 3600 * int(time[:2]) + 60 * int(time[3:5]) + int(time[6:8])

def r_convert(s):
    hour = str(s // 3600).zfill(2)
    s = s % 3600
    minite = str(s // 60).zfill(2)
    s = s % 60
    second = str(s).zfill(2)
    return hour + ":" + minite + ":" + second


def solution(play_time, adv_time, logs):
    answer = ''
    total = convert(play_time)
    advertise = convert(adv_time)
    consumers = [0] * (total+1)
    n = 0

    for log in logs:
        temp = log.split('-')
        consumers[convert(temp[0])] += 1
        consumers[convert(temp[1])] -= 1

    for i in range(1, total+1): # 현재 시점에서의 시청자 수
        consumers[i] += consumers[i-1]

    for i in range(1, total+1):
        consumers[i] += consumers[i-1]

    people = consumers[advertise-1]
    time = 0

    for start in range(0, total-advertise):
        if people < consumers[start+advertise] - consumers[start]:
            people = consumers[start+advertise] - consumers[start]
            time = start + 1

    answer = r_convert(time)

    return answer

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

풀이 과정

1. A와 B를 모두 오름차순으로 정렬
2. B를 Queue로 전환한 후, A를 이길때까지 B에서 한명씩 뽑아준다.
3. A의 인원을 이기게 된다면 카운팅 해주고 반복문 종료
4. B의 인원을 모두 뽑게 되면 종료한다.

소스 코드

from collections import deque

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    B_queue = deque(B)

    for a in A:
        while B_queue:
            b = B_queue.popleft()
            if b > a:
                answer += 1
                break

        if not B_queue:
            break


    return answer

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

문제 설명

풀이 과정

1. 재귀를 배우게 되면 가장 많이 배우게 되는 하노이의 탑 문제이다.

2. 1번에서 3번으로 맨 아래의 원판을 옮기기 위해서는 다음과 같은 과정을 거친다.
   2-1) 1번에서 자기 위의 원판들을 2번으로 옮겨 둔다.
   2-2) 1번의 가장 아래 원판을 3번으로 이동한다.
   2-3) 2번으로 옮겨둔 자기 위의 원판들을 3번으로 이동시킨다.

3. 위 과정을 재귀로 작성하면 문제가 풀리게 된다.

def hanoii(answer, n, src, temp, dest):
    if n == 1:
        answer.append([src, dest])
    else:
        hanoii(answer, n-1, src, dest, temp)
        answer.append([src, dest])
        hanoii(answer, n-1, temp, src, dest)

def solution(n):
    answer = []
    hanoii(answer, n, 1, 2, 3)
    return answer

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

풀이 과정

1. 최소 비용 신장 트리 문제라고 볼 수 있으므로 Kruskal 알고리즘 사용

2. Cycle을 판단하기 위해 Union-find 알고리즘 사용

3. Kruskal 알고리즘을 사용하여 가중치가 최소인 간선부터 골라가면서 사이클을 형성하는지 체크하고, 사이클을 형성하지 않는다면 해당 간선 사용

4. 가중치가 최소인 간선을 고르기 위해 최소 히프 사용

import heapq

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

def union(parent, a, b):
    t1 = find(parent, a)
    t2 = find(parent, b)
    if t1 != t2:
        parent[t1] = t2

def solution(n, costs):
    answer = 0
    heap = []
    for src, dest, cost in costs:
        heapq.heappush(heap, [cost, src, dest])

    selected_edges = 0
    parent = [i for i in range(n)]

    while heap:
        cost, src, dest = heapq.heappop(heap)
        t1 = find(parent, src)
        t2 = find(parent, dest)
        if t1 != t2:
            union(parent, src, dest)
            answer += cost
            selected_edges += 1
            if selected_edges == n-1:
                break

    return answer

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

풀이 과정

1. referral이 부모노드를 가리키므로, 반복해서 referral을 타고 올라가면서 -가 나올때까지 10%씩 삭감해주면서 더해주면 된다.

2. 또는 10%가 0원이 된다면 그냥 더한 후 바로 종료해주면 된다.

def solution(enroll, referral, seller, amount):
    answer = [0] * len(enroll)
    people_idx = {key:i for i,key in enumerate(enroll)}
    for idx, sell in enumerate(seller):
        temp = 100 * amount[idx]
        who = people_idx[sell]
        while True:
            answer[who] += temp - temp // 10
            if temp // 10 == 0 or referral[who] == '-':
                break
            temp = temp // 10
            who = people_idx[referral[who]]

    return answer

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

풀이 과정

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