Level 1

완주하지 못한 선수

• hash 이용

def solution(participant, completion):
    d = {}
    for name in participant + completion:
        d[name] = d.get(name, 0) + 1
    return [k for k, v in d.items() if v % 2 == 1][0]

좌석 구매

def solution(seat):
    seat = map(tuple, seat)
    return len(set(seat))

대중소 괄호 짝 맞추기

• stack 이용

def solution(s):
    d = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for c in s:
        if c in d:
            stack.append(c)
        else:
            if len(stack) < 1:
                return False
            top = stack.pop()
            if d[top] != c:
                return False
    return len(stack) == 0

세 소수의 합

• 소수(prime number)는 에라토스테네스의 체 알고리즘을 이용하는 것이 효율적!

def solution(n):
    primes = [False, False] + [True] * (n - 1)
    for i in range(len(primes) // 2):
        if primes[i]:
            for j in range(i * 2, len(primes), i):
                primes[j] = False
    prime_nums = list(filter(lambda x: primes[x], range(n)))
    cnt = 0
    for i in range(len(prime_nums)):
        for j in range(i + 1, len(prime_nums)):
            for k in range(j + 1, len(prime_nums)):
                if prime_nums[i] + prime_nums[j] + prime_nums[k] == n:
                    cnt += 1
    return cnt

Level 2

스킬트리

• stack 이용

def solution(skill, skill_trees):
    cnt = 0
    for st in skill_trees:
        stack = []
        for c in st:
            if c in skill:
                stack.append(c)
        for a, b in zip(stack, skill):
            if a != b:
                break
        else:
            cnt += 1
    return cnt

최대 용량이 정해진 FIFO 큐 클래스

• stack 2개를 이용하여 queue 구현

class MyStack(object):
    def __init__(self):
        self.lst = list()

    def push(self, x):
        self.lst.append(x)

    def pop(self):
        return self.lst.pop()

    def size(self):
        return len(self.lst)

class MyQueue(object):
    def __init__(self, max_size):
        self.stack1 = MyStack()
        self.stack2 = MyStack()
        self.max_size = max_size

    def qsize(self):  # 빈칸
        return self.stack1.size() + self.stack2.size()

    def push(self, item):  # 빈칸
        if self.qsize() < self.max_size:
            self.stack1.push(item)
            return True
        return False

    def pop(self):  # 빈칸
        if self.qsize() == 0:
            return False

        if self.stack2.size() == 0:
            while self.stack1.size() > 0:
                self.stack2.push(self.stack1.pop())
        return self.stack2.pop()

n, max_size = map(int, input().strip().split(' '))

# 여기서부터 구현
q = MyQueue(max_size)
for _ in range(n):
    method, *item = input().strip().split(' ')
    if method.upper() == 'PUSH':
        print(q.push(item[0]))  # 리스트 언패킹 사용으로 인한 인덱싱
    elif method.upper() == 'POP':
        print(q.pop())
    elif method.upper() == 'SIZE':
        print(q.qsize())

더 맵게

• heap 이용

def solution(scoville, K):
    import heapq
    scoville_heap = scoville[:]
    heapq.heapify(scoville_heap)
    mix_cnt = 0
    while len(scoville_heap) > 1 and scoville_heap[0] < K:
        min1 = heapq.heappop(scoville_heap)
        min2 = heapq.heappop(scoville_heap)
        mix = min1 + min2 * 2
        heapq.heappush(scoville_heap, mix)
        mix_cnt += 1
    return mix_cnt if scoville_heap[0] > K else -1

배상 비용 최소화

• heaq 이용

def solution(no, works):
    import heapq
    works_heap = [-a for a in works if a > 0]
    heapq.heapify(works_heap)
    while len(works_heap) > 0 and no > 0:
        time = heapq.heappop(works_heap) + 1
        if -time > 0:
            heapq.heappush(works_heap, time)
        no -= 1
    cost = map(lambda x: x ** 2, works_heap)
    return sum(cost)

짝지어 제거하기

• stack 이용

def solution(s):
    stack = []
    for c in s:
        if len(stack) > 0 and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    return 1 if len(stack) == 0 else 0

사전순 부분문자열

• stack 이용

def solution(s):
    substring = []
    for c in s:
        while len(substring) > 0 and substring[-1] < c:
            substring.pop()
        else:
            substring.append(c)
    return ''.join(substring)

주사위 게임

def solution(monster, S1, S2, S3):
    start = 1
    total_cnt, no_meet_cnt = S1 * S2 * S3, 0
    for s1 in range(1, S1+1):
        for s2 in range(1, S2+1):
            for s3 in range(1, S3+1):
                if start + s1 + s2 + s3 not in monster:
                    no_meet_cnt += 1
    return int(no_meet_cnt / total_cnt * 1000)

문자열 압축

def solution(s):
    min_string = s
    for step in range(1, len(s) // 2 + 1):
        substring = [s[i:i + step] for i in range(0, len(s), step)]
        compressed = []
        prev, match_cnt = '', 0
        for a in substring + ['']:
            if prev == a:
                match_cnt += 1
            else:
                if match_cnt > 0:
                    compressed.append(str(match_cnt + 1))
                    compressed.append(prev)
                else:
                    compressed.append(prev)
                prev = a
                match_cnt = 0
        min_string = min(min_string, ''.join(compressed), key=lambda x: len(x))
    return len(min_string)

Level 3

배달

• 최단경로 - 다익스트라 알고리즘
• heap 이용

def solution(N, road, K):
    import heapq
    heap = [(0, 1)]  # dist, idx

    max_cost = 500001  # 1 <= K <= 500000
    visited = [None] + [False] * N
    dist = [None] + [max_cost] * N
    dist[1] = 0

    while len(heap) > 0:
        cur_cost, cur_idx = heapq.heappop(heap)
        if visited[cur_idx]: # -----> dist[cur_idx] < cur_cost
            continue
        for src, dest, cost in road:
            if src == cur_idx:
                if dist[dest] > cur_cost + cost:
                    dist[dest] = cur_cost + cost
                    heapq.heappush(heap, (dist[dest], dest))
            elif dest == cur_idx:
                if dist[src] > cur_cost + cost:
                    dist[src] = cur_cost + cost
                    heapq.heappush(heap, (dist[src], src))
        visited[cur_idx] = True
    return len([d for d in dist[1:] if d <= K])

💡여기서 visited 를 따로 두는 대신 dist[cur_idx] < cur_cost 를 써주는 것도 가능하다

→ 힙에 들어가고 나서 다른 노드에 의해 자신의 최단 경로가 갱신 되었을 수가 있다. 그런 경우 갱신 이전의 비용을 가지고 다른 노드의 최단 경로를 갱신하는 과정은 의미가 없다.

FloodFill

• BFS 알고리즘 이용

def solution(n, m, image):
    from collections import deque

    def bfs(x, y, color):
        q = deque()
        q.append((x, y))
        cnt = 0
        while len(q) > 0:
            a, b = q.popleft()
            if a < 0 or a >= n or b < 0 or b >= m:
                continue

            if image[a][b] != -1 and image[a][b] == color:
                image[a][b] = -1
                q.append((a - 1, b))
                q.append((a, b - 1))
                q.append((a + 1, b))
                q.append((a, b + 1))
                cnt += 1
        return cnt

    ans = 0
    for i in range(n):
        for j in range(m):
            if bfs(i, j, image[i][j]) > 0:
                ans += 1
    return ans

방문 길이

• set 사용

def solution(dirs):
    min_limit, max_limit = -5, 5
    move = {'U': (0, 1), 'D': (0, -1), 'L': (-1, 0), 'R': (1, 0)}
    now = [0, 0]
    log = set()
    for d in dirs:
        after = [now[i] + move[d][i] for i in range(len(now))]

        if min_limit > after[0] or max_limit < after[0]:
            continue
        elif min_limit > after[1] or max_limit < after[1]:
            continue

        if d in 'UR':
            log.add(tuple(now + after))
        else:
            log.add(tuple(after + now))
        now = after
    return len(log)

내가 구현한 코드보다 제공된 풀이가 더 깔끔해서 dict 만 set 로 바꾸어서 조금 수정하였다..😅

def solution(dirs):
    x, y = 0, 0
    log = set()
    for command in dirs:
        if command == 'U' and y < 5:  # 위로
            log.add((x, y, x, y + 1))   # 작은 값이 왼쪽으로
            y += 1
        elif command == 'D' and y > -5:  # 아래로
            log.add((x, y - 1, x, y))
            y -= 1
        elif command == 'R' and x < 5:  # 오른쪽으로
            log.add((x, y, x + 1, y))
            x += 1
        elif command == 'L' and x > -5:  # 왼쪽으로
            log.add((x - 1, y, x, y))
            x -= 1
    return len(log)

게임아이템

문제 이해가 잘 안되어서 풀이를 참고하였다.😂

1. 캐릭터의 체력 오름차순, 아이템의 깎는 체력을 내림차순으로 각각 정렬하여
2. 캐릭터의 체력을 하나씩 돌면서
   1. 사용할 수 있는 아이템들을 찾아 pop 한 후에, 그 중에서 가장 많은 공격력을 올려주는 아이템 순으로 heap 에 넣어놓고
   2. heap 이 비어있지 않으면 하나를 pop 하여 정답 리스트에 넣는다

import heapq

def solution(healths, items):
    healths = sorted(healths)
    items = sorted([(item[1], item[0], i) for i, item in enumerate(items, start=1)], reverse=True)

    ans = []
    heap = []
    for h in healths:
        while len(items) > 0:
            minus_heal, plus_power, i = items[-1]
            if h - minus_heal < 100:
                break
            items.pop()
            heapq.heappush(heap, (-plus_power, i))
        if len(heap) > 0:
            ans.append(heapq.heappop(heap)[1])
    return sorted(ans)

야근지수

• heap 사용

import heapq

def solution(n, works):
    heap_works = [-work for work in works]
    heapq.heapify(heap_works)
    while len(heap_works) > 0 and n > 0:
        work = heapq.heappop(heap_works) + 1
        if work != 0:
            heapq.heappush(heap_works, work)
        n -= 1
    print(heap_works)
    return sum(map(lambda x: x ** 2, heap_works))

빙고

• list를 set로 바꾸어서 시간을 줄인다 (set 의 요소 포함 여부 확인은 $O(1)$)

def solution(board, nums):
    n = len(board)
    nums = set(nums)

    rows = [0 for _ in range(n)]
    cols = [0 for _ in range(n)]
    left_diagonal = 0
    right_diagonal = 0

    for i in range(n):
        for j in range(n):
            if board[i][j] in nums:
                rows[i] += 1
                cols[j] += 1

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

    bingo_cnt = 0
    bingo_cnt += len([a for a in rows if a == n])
    bingo_cnt += len([a for a in cols if a == n])
    bingo_cnt += 1 if left_diagonal == n else 0
    bingo_cnt += 1 if right_diagonal == n else 0
    return bingo_cnt