[1주차 - Day5-7]

다섯째날, 코딩테스트 연습만 주구장창 하다가 집중력의 한계를 깨닫고 다른 공부를 조금 했다.

Docker랑 Kubernetes에 대해 관심이 가고, 추후 Tensorflow 2.0과 함께 Kubeflow를 사용할 예정이다.

문제가 꽤 많아서 약 30문제? 풀다 지치고 풀다 지치고 반복하다가 모범답안도 보고 그랬다.

어우,, 모범답안 답은 왜이리 좋은지 하나하나 기록해놓고 싶다. 문제는 구글에 검색하면 왠만하면 나오니까 답만 밑에 기록해두겠다.

---

Programmers 배달

from queue import PriorityQueue # 파이썬 내장 모듈

def dijkstra(road, N):
    queue = PriorityQueue() # 우선순위 큐
    queue.put([1, 0]) # 1번 마을부터 시작

    dist = [float('inf')] * (N + 1) # 계산하기 편하게 N+1 길이만큼 리스트 생성
    dist[1] = 0 # 1번 마을은 무조건 거리가 0

    while not queue.empty():
        current, current_cost = queue.get() # 현재 선택된 노드와 비용
        for src, dest, cost in road: # 출발지, 목적지, 비용
            next_cost = cost + current_cost # 비용
            if src == current and next_cost < dist[dest]:
                # src가 현재 선택된 노드면서 목적지까지 더 저렴할 경우
                dist[dest] = next_cost # 최소 비용을 갱신
                queue.put([dest, next_cost]) # Priority Queue에 추가
            elif dest == current and next_cost < dist[src]:
                # dest가 현재 선택된 노드면서 출발지까지 더 저렴할 경우
                dist[src] = next_cost # 최소 비용을 갱신
                queue.put([src, next_cost]) # Priority Queue에 추가
    return dist

def solution(N, road, K):
    dist = dijkstra(road, N)
    return len([x for x in dist if x <= K]) # list comprehension

---

Programmers 완주하지 못한 선수

def solution(participant, completion):
    participant.sort() # 정렬은 시간복잡도가 O(n log n)이다.
    completion.sort()
    for p, c in zip(participant, completion): 
    # zip으로 같이 묶어준다 zip은 리스트를 같은 인덱스끼리 잘라서 리스트로 반환을 해준다.
        if p != c: # 만약 다른게 등장하면 그게 완주하지 못한 사람
            return p

    return participant[-1] # 끝까지 없으면 마지막에 있는 것이 완주하지 못한 사람

---

Programmers 스킬트리

def solution(skill, skill_trees):
    answer = 0

    for skill_tree in skill_trees:
        skill_list = list(skill)
        for s in skill_tree:
            if s in skill and s != skill_list.pop(0):
                break
        else: # for-else 문법을 사용하면 dirty flag를 제거할 수 있고 파이썬스럽게 푼 느낌이 든다.
            answer += 1

    return answer

---

Programmers 세 소수의 합

from itertools import combinations

def solution(n):
    sieve = [True] * n
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * 2, n, i):
                sieve[j] = False

    prime_numbers = [i for i in range(2, n) if sieve[i]]
    return [sum(c) for c in combinations(prime_numbers, 3)].count(n) 

---

Programmers 주사위 게임

from itertools import product

def solution(monster, S1, S2, S3):
    p = product(range(S1), range(S2), range(S3))
    case = len([x for x in p if sum(x) + 4 not in monster])
    return int(case / (S1 * S2 * S3) * 1000)

---

Programmers 빙고

def solution(board, nums):
    n = len(board) # board의 길이
    nums = dict.fromkeys(nums, True) # nums 리스트 값을 키로 변환하여 dict로 만들어준다, Hash가 Key point!
    row_list = [0] * n
    col_list = [0] * n
    left_diagonal = 0
    right_diagonal = 0

    for i in range(n): # O(n)
        for j in range(n): # O(n)
            if board[i][j] in nums: # O(1)
                board[i][j] = 0
                row_list[i] += 1
                col_list[j] += 1

                if i == j:
                    left_diagonal += 1
                if n - 1 - i == j:
                    right_diagonal += 1

    answer = 0
    answer += sum([1 for i in row_list if i == n]) # 세로
    answer += sum([1 for i in col_list if i == n]) # 가로
    answer += 1 if left_diagonal == n else 0 # 왼쪽 대각선
    answer += 1 if right_diagonal == n else 0 # 오른쪽 대각선

    return answer

---

Programmers 방문 길이

def solution(dirs):
    x, y = 0, 0 # 시작 좌표를 0, 0으로 지정
    map = dict() # 좌표를 키로 사용하는 해시 생성
    for command in dirs: # O(dirs)
        if command == 'U' and y < 5: # 위로
            map[(x, y, x, y+1)] = True # 현재 좌표, 이동할 좌표
            # x, y 좌표 작은게 왼쪽으로~
            y += 1
        elif command == 'D' and y > -5: # 아래로
            map[(x, y-1, x, y)] = True # 이동할 좌표, 현재 좌표
            y -= 1
        elif command == 'R' and x < 5: # 오른쪽으로
            map[(x, y, x+1, y)] = True # 현재 좌표, 이동할 좌표
            x += 1
        elif command == 'L' and x > -5: # 왼쪽으로
            map[(x-1, y, x, y)] = True # 이동할 좌표, 현재 좌표.
            x -= 1

    return len(map) # 추가된 값들이 곧 방문 길이

---

---

요고는 Tim Sort에 대한 Naver D2의 설명.

https://d2.naver.com/helloworld/0315536

블로그 글 하나하나에 전부 정성이 들어있어서 언제 봐도 감탄이 나옴...

오늘은 여기까지!