[TIL Day5] 코딩테스트 더 풀어보기 (1)

🟢 푼 문제
🟡 접근 방법을 알았지만 못 푼 문제
🔴 접근 방법도 모르고 못 푼 문제

Lv1

1. 좌석 구매 🟢

• 문제 풀이 과정
  - 줄을 서 있는 사람들이 구매하려는 좌석의 좌표를 중복되지 않게 세어야 한다.
  • 사전 자료형을 이용하자.
  • [[1,1],[2,2],[3,3]] 으로 주어진 seat 인자의 원소를 key로 하려고 했더니, TypeError: unhashable type: 'list' 에러가 발생했다.
  • 리스트는 사전 자료형의 key로 쓸 수 없다.
  • 따라서 리스트의 원소를 다시 튜플에 담아 key로 썼다

def solution(seat):
    d = {}
    for x, y in seat:
        d[(x, y)] = d.get((x, y), 0) + 1
    
    return len([k for k, v in d.items()])

2. 대중소 괄호 짝 맞추기 🟢

• 문제 해결 방법
  - stack을 이용하여 여는 괄호는 집어넣고, 닫는 괄호는 stack의 가장 윗단 원소와 비교하여 짝이 맞는지 확인하자.
  • 짝이 맞으면 여는 괄호를 pop해서 제거하고, 짝이 맞지 않으면 False 리턴
  • 테스트케이스를 잡자!
    • 비어있는 stack과 닫는 괄호를 비교하려 할 경우 False
    • 모든 원소를 검사한 후 stack이 비어있지 않으면 False

# 배열로 stack을 구현해 사용하자
def solution(s):
    d = {')':'(', '}':'{', ']':'['}
    stack = []
    for x in s:
        # 여는 괄호이면 stack에 집어넣자
        if x in ['(', '{', '[']:
            stack.append(x)
        # 닫는 괄호이면 stack의 가장 위 원소와 비교하자
        else:
            # stack이 비어있으면 짝이 맞지 않는 것이므로 false
            if len(stack) == 0:
                return False
            # stack의 가장 나중에 들어간 여는 괄호와 짝이 맞으면 pop
            if d[x] == stack[-1]:
                stack.pop()
            # 여는 괄호과 짝이 맞지 않으면 false
            else:
                return False
    
    # 모든 괄호를 검사했는데 stack에 남아있는 원소가 있으면 false
    if len(stack) != 0:
        return False
    
    return True

3. 세 소수의 합 🟢

• 문제 해결 방법
  - n이하의 수 중 소수를 모두 찾아놓고 시작한다.
  - 에라토스테네스의 체를 구현해 소수들을 찾는다.
  - n보다 작은 소수들 nums에서 3개를 뽑는 경우의 수(combinations)를 모두 구한다.
  - 경우의 수를 검사(더해서 n이 되는지)하여 answer를 도출한다.
  

import itertools

def solution(n):
    answer = 0
    arr = [True] * (n + 1)
    # 0과 1은 소수가 아니다
    arr[0], arr[1] = False, False
    for i in range(2, int(n ** (1/2)) + 1):
        j = 2
        while i * j <= n:
            arr[i * j] = False
            j += 1
            
    nums = [i for i in range(n) if arr[i] == True]
    candidates = list(itertools.combinations(nums, 3))
    for x in candidates:
        if sum(x) == n:
            answer += 1
    
    return answer

4. 나머지 한 점 🟢

• 문제 해결 방법
  - 사전 자료형으로 x좌표, y좌표 각각 1개씩만 있는 값을 찾는다.

def solution(v):
    x = {}
    y = {}
    for i, j in v:
        x[i] = x.get(i, 0) + 1
        y[j] = y.get(j, 0) + 1
    
    a = [k for k, v in x.items() if v == 1][0]
    b = [k for k, v in y.items() if v == 1][0]
    
    return [a, b]

5. 운송 트럭 🟢

def solution(max_weight, specs, names):
    specs = {i:int(j) for i, j in specs}
    weight_sum = 0
    answer = 1
    for n in names:
        weight_sum += specs[n]
        if weight_sum > max_weight:
            answer += 1
            weight_sum = specs[n]
        
    return answer

6. 예산 소팅 🟢

def solution(d, budget):
    d.sort()
    answer = 0
    for x in d:
        if budget >= x:
            budget -= x
            answer += 1
        else:
            break
        
    return answer

Lv2

1. 올바른 괄호 🟢

• 문제 해결 방법
  - Lv1의 대중소 괄호 짝 맞추기 문제를 조금 변형해서 풀었다.

def solution(s):
    stack = []
    for x in s:
        # 여는 괄호이면 stack에 집어넣자
        if x == '(':
            stack.append(x)
        # 닫는 괄호이면 
        else:
            # stack이 비어있으면 짝이 맞지 않는 것이므로 false
            if len(stack) == 0:
                return False
            # stack의 가장 나중에 들어간 여는 괄호와 짝이 맞으면 pop
            if stack[-1] == '(':
                stack.pop()
            # 여는 괄호과 짝이 맞지 않으면 false
            else:
                return False
    
    # 모든 괄호를 검사했는데 stack에 남아있는 원소가 있으면 false
    if len(stack) != 0:
        return False
    
    return True

2. 스킬트리 🟢

• 문제 해결 방법
  - 우선, 선행 스킬 순서에 포함되지 않은 문자들을 skill_trees에서 제거한다.
  - 정규표현식을 이용했다.
  - skill_trees의 원소 x를 검사하면서, skill을 x의 길이만큼 슬라이싱 했을 때 x와 같은지 확인한다.

import re

def solution(skill, skill_trees):
    answer = 0
    for x in skill_trees:
        # 선행 스킬 순서에 상관 없는 스킬들은 제거하고 시작하자
        x = re.sub('[^' + skill + ']', '', x)
        if x == skill[:len(x)]:
            answer += 1
    
    
    return answer

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

• 문제 해결 방법
  - stack1과 stack2 2개로 queue를 구현할 수 있다.
  • push: stack1에 원소를 push한다.
  • pop: stack1에 들어있는 원소를 차례대로 stack2에 옮겨 담는다. stack1에 가장 먼저 들어갔던 원소가 stack2의 가장 위에 놓이게 된다. 이 때 stack2에서 pop하면 FIFO가 구현된다. 그 후에는 stack2의 원소들을 다시 차례대로 stack1에 옮겨 담는다.

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()
    
    def push(self, item):
        # 큐가 꽉 찬 경우 False 리턴
        if self.stack1.size() == self.max_size:
            return False
        else:
            self.stack1.push(item)
            return True

    def pop(self):
        # 큐에 원소가 없다면 에러 발생
        try:
            if self.stack1.size() == 0:
                raise emptyException
        
            # stack1의 원소를 모두 stack2에 옮겨 담자
            # stack2에는 나중에 stack1에 들어간 원소가 가장 바닥에(처음 들어간 원소는 가장 위에) 있게 된다
            while self.stack1.size() > 0:
                self.stack2.push(self.stack1.pop())
        
            item = self.stack2.pop()
        
            # 다시 stack1에 옮겨 담아 순서를 유지하자
            while self.stack2.size() > 0:
                self.stack1.push(self.stack2.pop())
        
            return item
        
        except emptyException:
            return False

class emptyException(Exception):
    pass
        
n, max_size = map(int, input().strip().split(' '))
q = MyQueue(max_size)
for i in range(n):
    order = input()
    if order == 'POP':
        print(q.pop())
    elif order == 'SIZE':
        print(q.qsize())
    else:
        order, x = order.strip().split(" ")
        print(q.push(int(x)))

4. 더 맵게 🟢

• 문제 해결 방법
  - 매번 가장 맵지 않은 음식과 두번째로 맵지 않은 음식을 찾아야 하므로, 스코빌지수가 작은대로 정렬되어 있으면 좋겠다.
  - 최소 힙을 이용하자.

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    answer = 0
    while True:
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) > 0:
            min2 = heapq.heappop(scoville)
            new_scoville = min1 + (min2 * 2)
            answer += 1
            heapq.heappush(scoville, new_scoville)
        elif len(scoville) == 0:
            answer = -1
            break
            
    return answer

5. 배상 비용 최소화 🟢

• 문제 해결 방법
  - 매번 가장 최대로 남은 작업을 해야한다.
  - 최소 힙에 원소의 부호를 바꾸어 넣어서 최대 힙을 구현하자.

import heapq

def solution(n, works):
    # 최대 힙을 구현해야 한다
    # works = [4, 3, 3]인 경우 원소의 부호를 바꾸면 최소 힙에 [-4, -3, -3]으로 들어간다 
    works = [-w for w in works]
    heapq.heapify(works)
    while n > 0:
        if -works[0] <= 0:
            break
        max_work = -(heapq.heappop(works))
        heapq.heappush(works, -(max_work - 1))
        n -= 1

    return sum([w ** 2 for w in works])

6. 짝지어 제거하기 🟢

• 문제 해결 방법
  - 스택을 이용해 같은 문자가 붙을 때마다 제거해주자.
  - 모든 문자를 처리했는데 스택이 비어있지 않으면 False, 스택이 비어있으면 True
  

def solution(s):
    stack = []
    for x in s:
        # 스택이 비어있으면 x를 집어넣자
        if len(stack) == 0:
            stack.append(x)
        # 비어있지 않으면
        else:
            # 스택에 마지막에 들어간 원소와 x가 같으면 pop
            if stack[-1] == x:
                stack.pop()
            # 그렇지 않으면 
            else:
                stack.append(x)

    if len(stack) == 0:
        return 1
    else:
        return 0

7. 사전순 부분문자열 🟡

• 문제 해결 방법
  - 스택을 이용해 사전순으로 가장 큰(뒤쪽인) 문자가 앞에 오도록 한다.
  - 한번씩만 비교하면 테스트케이스(s='acbcdd', return='dd')를 잡을 수 없다.
  - while문으로 stack에 원소가 남아있는 한, 앞에 있는 문자가 뒤에 있는 문자보다 크지 않도록 pop 하자.
  

def solution(s):
    stack = []
    for x in s:
    	# 스택에 문자가 남아있고,
        # 가장 마지막에 들어간 문자가 x보다 사전순으로 앞에 오는 문자일 경우 pop
        while len(stack) > 0 and stack[-1] < x:
            stack.pop()
        stack.append(x)
        
    return ''.join(stack)

8. 주사위 게임 🟢

• 문제 해결 방법
  - 완전 탐색으로 모든 경우의 수를 검사하자.
  

import itertools
import math

def solution(monster, S1, S2, S3):
    monster.sort()
    
    game_map = [0] * (monster[-1] + 1)
    for m in monster:
        game_map[m] = 1
        
    # 몬스터를 만나지 않는 경우
    not_mon = 0
    for i in range(1, S1 + 1):
        for j in range(1, S2 + 1):
            for k in range(1, S3 + 1):
                sum_value = i + j + k + 1
                if sum_value > monster[-1]:
                    not_mon += 1
                elif game_map[sum_value] == 0:
                    not_mon += 1
    total = S1 * S2 * S3
    return math.floor((not_mon / total) * 1000)

9. 카펫 🟢

• 문제 해결 방법
  - carpet의 가로, 세로 길이가 될 수 있는 것은 약수 쌍들이다.
  

def solution(brown, red):
    carpet = brown + red
    # 전체 격자의 수 carpet의 약수 쌍을 구한다
    c = [(i, carpet // i) for i in range(2, int(carpet ** 0.5) + 1) if carpet % i == 0]
    # 가로, 세로의 길이로 brown을 만들 수 있는지 확인한다
    for a, b in c:
        if (a * 2) + (b * 2) - 4 == brown:
            return [b, a]

10. 사탕 담기 🟢

• 문제 해결 방법
  - weights의 길이가 15 이하이므로 모든 경우의 수를 고려하여 완전 탐색으로 풀자.

import itertools

def solution(m, weights):
    candidates = []
    for i in range(1, len(weights)):
        candidates += map(sum, itertools.combinations(weights, i))
    return len([c for c in candidates if c == m])

11. 기능개발 🟢

• 문제 해결 방법
  - queue를 이용해서 앞에서부터 원소를 삭제하기 편하게 만든다.
  • queue에 원소가 남아있는지 잘 확인하자.

import math
from collections import deque

def solution(progresses, speeds):
    answer = []
    # 남은 작업일을 먼저 계산해두자
    days_left = [math.ceil((100 - i) / j) for i, j in zip(progresses, speeds)]
    
    queue = deque(days_left)

    while queue:
        max_days = queue.popleft()
        result = 1
        
        while queue:
            next_days = queue[0]
            
            # 다음 작업의 남은 일수가 max_days보다 작을 경우
            # 배포될 작업 개수 + 1
            if max_days >= next_days:
                result += 1
                queue.popleft()
            else:
                answer.append(result)
                break
                
        if not queue:
            answer.append(result)
    
    return answer

12. 최솟값 만들기 🟢

• 문제 해결 방법
  - 가장 큰 수와 가장 작은 수를 곱해야 모두 더했을 때 최소로 만들 수 있다.
  

def solution(A,B):
    A.sort()
    B.sort(reverse=True)

    return sum([a * b for a, b in zip(A, B)])