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

https://programmers.co.kr/learn/courses/30/lessons/92341?language=python3 

풀이 과정

본문이 너무 길어서 내가 이해한게 맞나 자주 확인해보아야 했던 문제 같다.

1. 시간을 처리할 때는 그냥 분으로 모두 바꿔준 다음에 처리해주는게 체감상 제일 좋다. 따라서 시-분으로 구성되어 있는 형태를 분으로 바꾸어주는 함수를 만들어 준다.
2. 이후, 입력된 기록에 맞추어서 다음 과정을 반복한다.
   1. 전체 주차 시간을 저장해 둘 딕셔너리를 따로 만들어 둔다.
   2. IN 표시가 되어있는 경우는, 해당 차의 주차 시간을 딕셔너리에 저장한다.
   3. OUT 표시가 되어 있는 경우는, 출차 시간에서 딕셔너리에 저장된 주차 시간을 빼준 값을 전체 주차 시간을 저장해 둘 딕셔너리에 더해 준다. 또한 이 때, OUT이 되었음을 나타내기 위해 값을 -1로 처리해 준다.
3. 위 과정을 끝내고 나서, OUT 처리가 되지 않은 경우는 23:59에 출차한 것으로 간주하여 처리해 준다.
   • (값이 -1이 아닌 경우)
4. 마지막으로, 주차 요금을 구해 준다.
   1. 차량 번호순으로 구해주어야 하므로 처음부터 딕셔너리의 키값을 정렬해서 진행하는게 편하다.
   2. 기본 시간보다 작거나 같은 경우는 기본 요금으로 처리해 준다.
   3. 기본 시간보다 크다면 다음 수식을 적용해준다.
      1. 기본 요금 + math.ceil((주차 시간 - 기본 시간) / 단위 시간) * 단위 요금
      2. 올림 기호를 사용하는 법을 모르므로 math.ceil로 표시함..ㅎㅎ

소스 코드

from collections import defaultdict
import math

def htom(s):
    return 60 * int(s[:2]) + int(s[3:])


def solution(fees, records):
    answer = []
    park_time = defaultdict(lambda: 0)
    in_time = defaultdict(lambda: 0)
    for record in records:
        time, number, status = record.split()
        if status == 'IN':
            in_time[number] = htom(time) 
        if status == 'OUT':
            park_time[number] += htom(time) - in_time[number]
            in_time[number] = -1
    
    last_time = htom("23:59")
    default_time, default_fee, per_minute, per_fee = fees
    for key in sorted(in_time.keys()):
        if in_time[key] != -1:
            park_time[key] += last_time - in_time[key]
        if park_time[key] <= default_time:
            answer.append(default_fee)
        else:
            answer.append(default_fee + (
                math.ceil((park_time[key] - default_time) / per_minute)
            ) * per_fee)
    
    
    
    return answer

https://programmers.co.kr/learn/courses/30/lessons/92335

풀이 과정

1. 우선 주어진 수를 k진수 문자열로 변환시켜 준다.
   1. k진수 문자열로 변환시키는 방법은 수가 0이 될때까지 k로 나눈 나머지를 앞에 붙여주고, 수를 k로 나누어 주는 방식으로 계산하면 된다.
   2. 2진수는 bin으로 해줄수도 있지만.. k가 3~10이니깐.. 위 방식으로 구해주는게 제일 좋을듯?
2. 구해준 2진수 문자열에서 조건에 맞는 소수를 구해준다.
   1. 결국 조건들을 보면, 숫자들이 0을 기준으로 split 된다는걸 볼 수 있다.
   2. 이 때, 그냥 "0" 으로 split 해준다면 문자열이 "00"같은 경우에는 빈 문자열도 등장하기 때문에, 정규 표현식을 사용해주는게 좋다. re 모듈을 사용하고, "0+"로 split 해준다
   3. split된 결과 중 소수인 개수를 구해서 리턴시켜 준다.

소스 코드

import math
import re

def convert(n, k):
    cv = ""
    while n != 0:
        cv = str(n % k) + cv
        n //= k
    
    return cv

def check_prime(n):
    if n == 1:
        return False
    
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
        
    return True

def solution(n, k):
    PATTERN = r"0+"
    answer = 0
    convert_string = convert(n, k)
    st_list = re.split(PATTERN, convert_string)
    
    for st in st_list:
        if st == "":
            continue
        if check_prime(int(st)):
            answer += 1
        
    return answer

https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3 

풀이 과정

1. 걸리는 시간의 범위가 크기 때문에 전체 범위가 너무 커질것 같아 이분탐색을 고려하였으나 이분 탐색 시 시뮬레이션 하는 파트 생각이 안나서 게시된 문제 풀이를 참조함.
2. 현재 시간을 t분이라고 할 때
   1. t분동안 물건을 나르는 횟수는 크게 mid // (걸리는 시간 * 2)이고, 맨 마지막에 편도로 이동 가능하므로 mid % (걸리는 시간 * 2)가 걸리는 시간보다 큰 경우는 횟수를 하나 늘려준다.
   2. t분동안 각각의 도시에서 옮길 수 있는 최대 금, 최대 은 개수를 각각 더해준다.
   3. 동시에 각각의 도시에서 옮길 수 있는 광물의 수의 총합도 구해준다.
   4. 다음 조건이 만족하면 정답을 저장하고 왼쪽 구간을, 아니라면 오른쪽 구간을 진행한다.
      1. 옮길수 있는 최대 금의 개수가 a보다 큰지
      2. 옮길수 있는 최대 은의 개수가 b보다 큰지
      3. 각각의 도시에서 옮길수 있는 광물의 수의 합이 a+b보다 큰지
   5. 잘 생각해 보면, 옮길 수 있는 광물의 수의 합이 a+b보다 크고, 최대 금과 최대 은의 개수가 a, b보다 크다면 금과 은의 개수를 적절하게 맞추어 준다면 금 a kg 이상, 은 b kg 이상을 나를 수 있다.
3. 시뮬레이션 파트를 잘 생각하지 못해서 풀지 못했던 문제임.. 고민 많이 해볼것.

소스 코드

def solution(a, b, g, s, w, t):
    answer = int(10**16)
    left, right = 0, int(10**16)
    
    while left <= right:
        mid = (left + right) // 2
        gold = 0
        silver = 0
        total = 0
        for i in range(len(g)):
            movement_count = mid // (t[i] * 2)
            if mid % (t[i] * 2) >= t[i]:
                movement_count += 1
            city_gold = w[i] * movement_count if w[i] * movement_count <= g[i] else g[i]
            city_silver = w[i] * movement_count if w[i] * movement_count <= s[i] else s[i]
            gold += city_gold
            silver += city_silver
            total += w[i] * movement_count if s[i] + g[i] >= w[i] * movement_count else s[i] + g[i]

        if gold >= a and silver >= b and total >= a + b:
            right = mid - 1
            answer = min(answer, mid)
        else:
            left = mid + 1
        
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12971

풀이 과정

1. 원형으로 연결되어 있으므로 첫번째 스티커를 선택하는지 선택하지 않는지에 따라 달라진다.
   1. 첫번째 스티커를 선택하는 경우, 마지막 스티커는 선택하지 않아야 함
   2. 첫번째 스티커를 선택하지 않는 경우, 마지막 스티커를 선택할 수도 있음
2. 첫번째를 선택하거나 선택하지 않은 각각의 경우에 따라 dp테이블을 구성해 준다.
3. 점화식은 다음과 같다.
   1. DP[i][0] = max(DP[i-1][0], DP[i-1][1])
   2. DP[i][1] = DP[i-1][0] + i번째 스티커
4. 첫번째 스티커를 선택한 경우는 마지막 스티커를 선택할 수 없으므로 DP[n-2]에서의 최댓값을, 첫번째 스티커를 선택하지 않은 경우는 마지막 스티커를 선택 가능하므로 DP[n-1]에서의 최댓값을 구해주면 된다.

소스 코드

def solution(sticker):
    answer = 0
    dp = [[0] * 2 for _ in range(len(sticker))]
    
    if len(sticker) == 1:
        return sticker[0]
    
    # 첫번째 선택
    dp[0][0], dp[0][1] = 0, sticker[0]
    dp[1][0], dp[1][1] = sticker[0], 0
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-2]))
    
    # 첫번째 선택하지 않은 경우
    dp[0][0], dp[0][1] = 0, 0
    dp[1][0], dp[1][1] = 0, sticker[1]
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-1]))
    
    return answer

https://programmers.co.kr/learn/courses/30/lessons/87390

풀이 과정

1. n의 범위가 10의 7승까지이므로 실제로 해보는건 불가능하다.
2. left와 right가 현재 몇행 몇열에 있는지 구한다.
   • 행의 경우 // 연산으로, 열의 경우 % 연산으로 구한다.
3. 문제를 보면, i행의 경우 i열까진 값이 i이고 i+1열부터는 값이 열과 같다.(i+1)
4. 따라서, left의 행,열에서 시작해서 right의 행,열까지 순서대로 이동하면서 값을 넣어주면 된다.
   1. left의 행일때는 left의 열~N열까지 단, left의 행과 right의 행이 같은 경우는 left의 열 ~ right의 열까지
   2. left의 행 + 1 ~ right의 행 - 1 구간에서는 (1~N열)
   3. right의 행에서는 1~right의 열까지
   4. 값을 넣어줄 때는 i행에서 i열까지는 i를 넣어주고, 이후에는 열에 맞추어서 넣어주면 된다.

소스 코드

def solution(n, left, right):
    answer = []
    sr, sc = (left // n)+1, (left % n)+1
    er, ec = (right // n)+1, (right % n)+1
    if sr == er:
        for j in range(sc, ec+1):
            if j <= sr:
                answer.append(sr)
            else:
                answer.append(j)
        return answer
    else:
        for j in range(sc, n+1):
            if j <= sr:
                answer.append(sr)
            else:
                answer.append(j)
                
    for i in range(sr+1, er):
        for j in range(1, n+1):
            if j <= i:
                answer.append(i)
            else:
                answer.append(j)
    
    for j in range(1, ec+1):
        if j <= er:
            answer.append(er)
        else:
            answer.append(j)
            

    return answer

https://programmers.co.kr/learn/courses/30/lessons/

풀이 과정

1. 던전의 수가 최대 8개까지밖에 없으므로 모든 조합을 다 해보는게 제일 쉬울것이라 판단
2. 배열의 인덱스가 2까지 있다고 하면 가능한 케이스는
   1. (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)
   2. 위 케이스를 하나씩 해보면서 탐험 가능한 최대 던전 수를 갱신하는 방식으로 풀이를 진행하면 된다.
   3. 초기 피로도를 k로 잡고, 현재 던전의 최소 필요 피로도보다 현재 피로도가 클 때, 던전의 수를 하나 늘리고 현재 피로도에서 현재 던전의 소모 피로도를 빼주는 방식으로 진행한다. 물론 최소 필요 피로도가 더 크다면 생략
3. recursion으로 구현하여도 되지만, 파이썬의 permutations 함수를 사용하는것이 가장 간편하다고 생각됨.

소스 코드

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    total_index = [i for i in range(len(dungeons))]
    total_case = list(permutations(total_index, len(dungeons)))
    
    for each_case in total_case:
        fatigue = k
        dungeon_count = 0
        
        for dungeon_idx in each_case:
            if fatigue >= dungeons[dungeon_idx][0]:
                dungeon_count += 1
                fatigue -= dungeons[dungeon_idx][1]
        
        answer = max(answer, dungeon_count)
    
    return answer

https://programmers.co.kr/learn/courses/30/lessons/87694

풀이 과정

구현 문제 겁나 어렵네

1. 풀이 이후 다른 사람들의 해결 방법을 보니 여러 해결방법이 있는것 같다.. 일단 본인은 직선 단위로 풀이를 진행함.
2. 각각의 직사각형을 4개의 직선으로 나누어서 저장.
3. 직선을 저장할 때, 다른 직선과의 교점이 발생할 경우, 해당 직선을 교점을 기준으로 나누어서 저장
   1. 교점 기준으로 왼쪽, 오른쪽, 위, 아래 총 네개의 직선이 나온다.
   2. 나누어진 직선이 또 다른 직선과의 교점이 발생할 수 있으므로 이 과정은 recursion으로 진행
4. 직선들 중 직선이 도형 내부에 존재하는 경우를 빼준다.
5. 시작점에서부터 BFS를 진행하여 도착 지점까지의 최소 거리를 구해준다.
6. 최소 거리를 리턴해주면 된다.

말은 쉽게 했지만.. 과정 하나하나 직접 코딩할 때 생각보다 시간이 훨씬 많이 걸려 3시간정도 걸린것 같다. 물론 이것도 변이 겹치는 경우가 없어서 위같이 풀이를 할 수 있었음. 구현 문제 연습을 조금 더 많이 해야할 것 같다..

소스 코드

"""
	nbalance97.tistory.com
"""

import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10**5)

def get_cross_point(lineA, lineB):
    p1_x, p1_y, p2_x, p2_y = lineA
    p3_x, p3_y, p4_x, p4_y = lineB
    
    # 평행인 경우
    if (p1_x == p2_x and p3_x == p4_x) or (p1_y == p2_y and p3_y == p4_y):
        return ()
    
    if p1_x == p2_x: 
        # 세로 직선인 경우
        if (p3_x < p1_x and p1_x < p4_x and p1_y < p3_y and p3_y < p2_y):
            return (p1_x, p3_y)
    else: 
        # 가로 직선인 경우
        if (p3_y < p1_y and p1_y < p4_y and p1_x < p3_x and p3_x < p2_x):
            return (p3_x, p1_y)
    
    return ()

def division(currentline, addline, deleteline, new_line):
    for exist_line in currentline:
        point = get_cross_point(new_line, exist_line)
        if point:
            deleteline.append(exist_line)
            x, y = point
            division(currentline, addline, deleteline, (new_line[0], new_line[1], x, y))
            division(currentline, addline, deleteline, (x, y, new_line[2], new_line[3]))
            division(currentline, addline, deleteline, (exist_line[0], exist_line[1], x, y))
            division(currentline, addline, deleteline, (x, y, exist_line[2], exist_line[3]))
            return

    addline.append(new_line)
        
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    line = set()
    
    for x1, y1, x2, y2 in rectangle:
        make_lines = [(min(x1, x2), y1, max(x1, x2), y1), (x2, min(y1, y2), x2, max(y1, y2)), 
                      (min(x1, x2), y2, max(x1, x2), y2), (x1, min(y1, y2), x1, max(y1, y2))]
        for new_line in make_lines:
            delete_line = []
            add_line = []
            
            division(line, add_line, delete_line, new_line)
                    
            for delete in delete_line:
                line.remove(delete)
            
            for add in add_line:
                line.add(add)

    delete_candidate = []
    # 사각형 내부에 직선이 포함되는지 확인
    for x1, y1, x2, y2 in line:
        for r_x1, r_y1, r_x2, r_y2 in rectangle:
            if x1 == x2:
                # 세로
                if r_x1 < x1 and x1 < r_x2 and r_y1 <= y1 and r_y2 >= y2:
                    delete_candidate.append((x1, y1, x2, y2))
                    break
            else:
                # 가로
                if r_y1 < y1 and y1 < r_y2 and r_x1 <= x1 and r_x2 >= x2:
                    delete_candidate.append((x1, y1, x2, y2))
                    break
    
    for candidate in delete_candidate:
        line.remove(candidate)
    
    graph = defaultdict(lambda:[])
    queue = deque()
    visited = set()
    for x1, y1, x2, y2 in line:
        if x1 <= characterX and characterX <= x2 and y1 <= characterY and characterY <= y2:
            queue.append([x1, y1, abs(x1-characterX) + abs(y1-characterY)])
            queue.append([x2, y2, abs(x2-characterX) + abs(y2-characterY)])
            visited.add((x1, y1))
            visited.add((x2, y2))
            
        graph[(x1, y1)].append((x2, y2))
        graph[(x2, y2)].append((x1, y1))
    
    # 이동 파트
    answer = int(10e9)
    while queue:
        x, y, dist = queue.popleft()
        for n_x, n_y in graph[(x, y)]:
            if min(x, n_x) <= itemX and itemX <= max(x, n_x) and \
               min(y, n_y) <= itemY and itemY <= max(y, n_y):
                answer = min(answer, dist + abs(itemX - x) + abs(itemY - y))
                continue
                
            if (n_x, n_y) not in visited:
                queue.append([n_x, n_y, dist + abs(n_x - x) + abs(n_y - y)])
                visited.add((n_x, n_y))
                        
    return answer

https://programmers.co.kr/learn/courses/30/lessons/87377

풀이 과정

1. 각각의 선분들의 교점을 따로 저장해 둔다.
   1. 문제 아래의 수식을 기반으로 ad - bc가 0일때는 일치하거나 교점이 없는 경우이므로 생략하고 0이 아닐때만 교점 x,y를 구해준다.
   2. 교점 x, y가 정수가 아닌 경우는 저장하지 않아야 함 
      • 나머지 연산 사용
   3. x, y가 정수인 경우, 나중에 필요하기 때문에 최소 x,y 와 최대 x,y를 갱신시켜 준다.
2. 따로 1000 x 1000 배열을 만들어 둔 다음, 각각의 교점에서 최소 x, 최소 y를 빼준 지점에 * 표시를 해준다.
   • 교점들의 시작점을 모두 (0, 0)으로 설정한다고 생각하면 됨.
3. 이제 y의 범위를 (최대 y - 최소 y) ~ 0까지의 배열을 저장해주면 된다.
   • x의 범위는 (0 ~ 최대 x - 최소 x) 까지

• 헤맸던 점은.. 우선 교점 x,y가 정수가 아닌 경우도 고려해서 틀렸었고 다음으로 최댓값의 경우 초기값을 1000000000으로 해두어서 괜찮았는데, 최솟값을 0으로 두었다가 계속해서 틀린 문제점이 있었다. 최솟값도 -1000000000으로 두어 해결함.

소스 코드

def check(a, b, c, d):
    return (a*d) - (b*c) != 0

def get_xy(a, b, e, c, d, f):
    if ((b * f) - (e * d)) % ((a * d) - (b * c)) != 0 or \
       ((e * c) - (a * f)) % ((a * d) - (b * c)) != 0:
            return (-int(10e9), -int(10e9))
    
    x = ((b * f) - (e * d)) // ((a * d) - (b * c))
    y = ((e * c) - (a * f)) // ((a * d) - (b * c))
    
    return (x, y)

def solution(line):
    answer = []
    point_set = set()
    matrix = [['.'] * 1001 for _ in range(1001)] 
    min_x, max_x = int(10e9), -int(10e9)
    min_y, max_y = int(10e9), -int(10e9)
    
    for i in range(len(line)):
        for j in range(i):
            if check(line[i][0], line[i][1], line[j][0], line[j][1]):
                x, y = get_xy(line[i][0], line[i][1], line[i][2],
                             line[j][0], line[j][1], line[j][2])
                
                if x == -int(10e9):
                    continue
                
                if (x, y) not in point_set:
                    min_x, max_x = min(min_x, x), max(max_x, x)
                    min_y, max_y = min(min_y, y), max(max_y, y)
                    point_set.add((x, y))
    
    for x, y in point_set:
        if y - min_y <= 1000 and x - min_x <= 1000:
            matrix[y-min_y][x-min_x] = '*'
        
    max_y = max_y - min_y
    max_x = max_x - min_x
    
    for i in range(max_y, -1, -1):
        answer.append("".join(matrix[i][:max_x+1]))
        
    return answer

https://programmers.co.kr/learn/courses/30/lessons/86971

풀이 과정

1. 전선들중 하나씩 빼보면서 분리된 전력망에 각각 몇개의 송전탑이 들어가는지 확인
   • 각각의 송전탑이 어느 전력망에 속하는지 구하기 위해 Union-Find 알고리즘 사용
2. 트리의 특성 상, 하나의 노드라도 연결을 끊으면 두개의 그룹으로 나뉘어질거라 생각하여, 파이썬의 defaultdict를 활용하여 각 전력망에 있는 송전탑의 개수를 저장한 다음, 두 값의 차이의 절댓값과 기존 정답의 비교를 통해 정답을 갱신한다.

소스 코드

from collections import defaultdict

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

def union(parent, a, b):
    pa = find(parent, a)
    pb = find(parent, b)
    if pa != pb:
        parent[pa] = parent[pb]

def solution(n, wires):
    answer = int(10e9)
    for skip in range(len(wires)):
        parent = [i for i in range(n+1)]
        for idx, wire in enumerate(wires):
            if skip == idx:
                continue
            if find(parent, wire[0]) != find(parent, wire[1]):
                union(parent, wire[0], wire[1])
        
        group_value = defaultdict(int)
        for i in range(1, n+1):
            group_value[find(parent, i)] += 1
        values = list(group_value.values())
        groupA, groupB = values[0], values[1]
        answer = min(answer, abs(groupA - groupB))
             
    return answer

https://programmers.co.kr/learn/courses/30/lessons/86491?language=python3 

풀이 과정

1. 지갑 크기를 명함 크기들과 순차적으로 비교하면서 갱신해 나간다.
   1. 기존 지갑 크기보다 명함의 크기가 더 크다면 갱신하는 방식
   2. 명함을 가로 방향과 세로 방향으로 집어넣을수 있으므로 각각의 케이스에 맞추어서 지갑의 크기를 갱신해 보고 지갑이 최소 넓이가 되는 경우로 지갑의 크기를 갱신시켜 준다.
2. 최종적으로 갱신된 지갑의 넓이를 리턴해주면 된다.

소스 코드

def solution(sizes):
    answer = 0
    
    card_w = 0
    card_h = 0
    for w, h in sizes:
        temp_w1, temp_h1 = max(w, card_w), max(h, card_h)
        temp_w2, temp_h2 = max(w, card_h), max(h, card_w)
        
        if temp_w1 * temp_h1 < temp_w2 * temp_h2:
            card_w, card_h = temp_w1, temp_h1
        else:
            card_w, card_h = temp_w2, temp_h2
    
    answer = card_w * card_h
    return answer