프로그래머스 level 2

124 나라의 숫자

def solution(n):
    tmp = '124'
    q,r = divmod(n-1,3)
    if q == 0:
        return tmp[r]
    else:
        return solution(q) + tmp[r]

124만 사용해서 십진수를 표현해야하므로 3진법이라고 생각하면 된다. 대신 n값이 자연수이기때문에 tmp랑 맞춰주기 위해 n-1를 해야한다.

기능개발

import math
def solution(progresses, speeds):
    answer = []
    tmp = [math.ceil((100 - a) / b) for a,b in zip(progresses, speeds)]
    cnt = 0
    
    top = tmp[0]
    while tmp:
        t = tmp.pop(0)
        if t > top:
            answer.append(cnt)
            top = t
            cnt = 1
        else:
            cnt += 1
        if not tmp:
            answer.append(cnt)
    return answer

남은 시간을 담은 tmp를 먼저 만들어 놓고, 앞에서부터 값을 하나씩 빼면서 조건을 걸어줬다. t <= top 로 끝나는 경우도 있는데 if not tmp 조건이 없으면 이런 경우 마지막 cnt 값을 저장하지 않는다.

주식가격

def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in range(i+1,len(prices)):
            if prices[i] <= prices[j]:
                cnt += 1
            else:
                cnt += 1
                break
        answer.append(cnt)                
    return answer

cnt 변수를 따로 사용하지 않고 answer[i] += 1를 사용하면 메모리를 아낄 수 있다. 또한, 바로 가격이 떨어져도 1초동안은 가격이 떨어지지 않은 것으로 본다는 것을 꼭 기억해야한다. 처음에는 이 조건을 못 봐서 else: break로 했었다.😅

다리를 지나는 트럭

def solution(bridge_length, weight, truck_weights):
    answer = 0
    start = truck_weights[:]
    bridge, time, end = [], [], []
    while end != truck_weights:
        answer += 1
        if time and not time[0]:
            end.append(bridge.pop(0))
            time.pop(0)
        if start and sum(bridge) + start[0] <= weight:
            bridge.append(start.pop(0))
            time.append(bridge_length)
        time = list(map(lambda x: x-1, time))
    return answer

x and y는 항상 x값을 구하고, y 값을 구한다. 즉, x가 False가 되면 y를 구하지 않고 바로 False를 리턴한다. 물론 이는 대부분 언어에서 그렇다.
Reference

프린터

✏️ 내가 작성한 코드

  
from collections import deque

def solution(priorities, location):   
    q = deque(priorities)
    answer = 0
    while True:
        if len(q) == 1:
            return answer + 1
        doc = q.popleft()
        if doc < max(q):
            q.append(doc)
            if location:
                location -= 1
            else:
                location += len(q)-1
            continue
        else:
            answer += 1
            if location:
                location -= 1
            else:
                return answer

원소값을 id를 이용해서 특정지으려고 했는데 원소의 값이 동일하다면 id값이 같다. 쉽게 말하면 파이썬에서 변수의 값이 동일하면 모두 같은 메모리 주소를 가리키고 있다.

a = [1,2,3,4]
b = 1
c = (9,1)
print(id(a[0]))		# 140710331819808
print(id(b))		# 140710331819808
print(id(c[1]))		# 140710331819808

어쨌든 그래서 id는 사용하지 못하고, index값인 location을 연산하는 방식으로 했다. 고민을 많이 했는데, 코드가 너무 못 생겨서 아쉬웠다.

💡 흥미로운 코드

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

일단, 한눈에 봐도 내가 짠 코드보다 아름답다! any는 iterable의 요소 중 하나라도 참이면 True를 리턴한다. 만약 비어 있다면 False를 리턴한다. any를 이용하면 내 코드에서 max를 사용하지 않고 값을 비교할 수 있다.
또한, index를 구하기 위해 location의 값을 빼고 더하는 것보다 위 코드처럼, 튜플을 이용해 index와 원소값을 함께 구했으면 훨씬 더 좋았을거 같다.
Reference

소수 찾기

✏️ 내가 작성한 코드

import itertools

def solution(numbers):
    numbers = sorted(numbers, reverse=True)
    number_list = []
    for i in range(1,len(numbers)+1):	# 조합 찾기
        nums = list(itertools.permutations(numbers,i))
        for num in nums:
            number_list.append(int(''.join(map(str,num))))
    max_number = int(''.join(numbers))
    prime = [False,False]+[True]*(max_number+1)
    for i in range(2, max_number+1):	# 소수 찾기
        if prime[i]:
            for j in range(2*i,max_number+1,i):
                prime[j] = False                
    answer = sum(1 for i in set(number_list) if prime[i])
    return answer

큰 수 만들기

✏️ 내가 작성한 코드

def solution(number, k):
    stack = []
    
    for i in number:
        while stack and stack[-1] < i and k:
            stack.pop()
            k -= 1
        stack.append(i)
    if k:
        stack = stack[:-k]
    return ''.join(stack)

스택에 값을 하나씩 넣는데 이때, 스택의 top부분이 넣으려고 하는 값보다 작을 경우 pop을 수행해 스택에서 빼버린다. 그리고 k를 1개 빼 k=0이 되면 더이상 값을 빼지않게 한다. k를 모두 사용하지 않았는데 조건이 끝나면 끝에서 남은 k만큼 뺀다

짝지어 제거하기

✏️ 내가 작성한 코드

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

이런 문제는 스택을 이용해서 풀면 되는데 왜 바로 생각이 안날까?

멀쩡한 사각형

✏️ 내가 작성한 코드

def solution(w,h):
    answer = 0
    for i in range(1, w):
        answer += int(-(h/w)*i + h)*2
    return answer

시간 초과. 좌표평면 위의 1차 그래프라고 생각하고 수식을 만들었다. x값이 1 ~ w-1일 때 y 값을 구하면 된다. 대신 y값이 소수이면 int로 바꿔 내림하였다. 그러나 w와 h의 값이 1억 이하의 자연수여서 O(n)으로는 풀지 못한다.

def solution(w,h):
    x,y = w,h
    while y:
        x,y = y,x%y
    return w*h-(w+h-x)

O(n)으로 풀지 못하고, 그렇다고 O(logN)도 될거 같지 않았다. 내가 놓친 규칙이 있고 O(1)로 풀 수 있는 방법이 있을거 같았다. 그래서 이리저리 살펴보다가 새로운 규칙을 찾았다. 첫번째로 푼 방법과는 다르게 빼야할 부분만 찾는 규칙을 보다가 기울기와 관련이 있을거 같았다. w+h에 두 수의 최대 공약수를 빼면 제외할 부분이 나온다. 이를 이용해 코드를 작성하였다.

더 맵게

✏️ 내가 작성한 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        if len(scoville) > 1:
            f,s = heapq.heappop(scoville), heapq.heappop(scoville)
            heapq.heappush(scoville, f+s*2)
            answer += 1
        else:
            return -1
    return answer

heap을 전혀 생각하지 못했다. 항상 최소값 또는 최대값을 구하고, 효율성을 따질때는 heap을 기억해야겠다.

타켓 넘버

✏️ 내가 작성한 코드

def solution(numbers, target):
    global cnt
    cnt, i = 0, 0
    def dfs(i, x, sn):
        global cnt
        if i >= len(numbers) or i < 0:
            return
        sn[i] = numbers[i]*x
        if i == len(numbers)-1 and target == sum(sn):
            cnt += 1
        dfs(i + 1, 1, sn)
        dfs(i + 1, -1, sn)
        return cnt

    numbers = [0] + numbers
    sn = [0]*(len(numbers))
    return dfs(i, 1, sn)

dfs문제인데 stack보단 재귀를 이용하는 게 훨씬 우아한 코드라고 해서 최대한 재귀를 사용하려고 했다. 그래서 나온 결과물인데... global도 거슬리고 참.. 마음에 안드는 코드다.

💡 흥미로운 코드

def solution(numbers, target):
    if not numbers and target == 0 :	# 타켓을 만들 경우
        return 1
    elif not numbers:	# 만들지 못 할 경우
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])	# 원소를 더했을 때 + 원소를 뺐을 때

감탄만 나왔던 코드. 이래서 스택보단 재귀가 우아한 코드라고 하는구나 싶었다.

게임 맵 최단거리

✏️ 내가 작성한 코드

from collections import deque

def solution(maps):
    q = deque([(0,0,1)])    # x,y,cnt

    while q:
        x, y, cnt = q.popleft()
        if maps[x][y] == 1:
            if x == len(maps)-1 and y == len(maps[0])-1:
                return cnt
            maps[x][y] = 0
            if x+1 < len(maps): q.append((x+1,y,cnt+1))
            if x-1 >= 0: q.append((x-1,y,cnt+1))
            if y+1 < len(maps[0]): q.append((x,y+1,cnt+1))
            if y-1 >= 0: q.append((x,y-1,cnt+1))

    return -1

최단거리 문제는 bfs로 푸는 것이 정석이다. 파이썬에서는 bfs를 구현하기 위해 list를 사용하는데 list는 큐에서 값을 빼낼 때(제일 앞쪽 값을 빼낼 때) 속도가 느리기 때문에 deque를 이용한다.

수식 최대화

✏️ 내가 작성한 코드

import re
import itertools

def solution(expression):
    answer = 0
    o = re.compile('[-+*]')
    n = re.compile('\d+')
    op = o.findall(expression)
    num = list(map(int, n.findall(expression)))
    case_list = itertools.permutations(['-', '+', '*'], 3)
    for case in case_list:
        operator = op[:]
        numbers = num[:]
        for oper in case:
            while oper in operator:
                idx = operator.index(oper)
                if idx >= 0 and oper == '*':
                    v = numbers.pop(idx) * numbers.pop(idx)
                    numbers.insert(idx, v)
                    del operator[idx]
                if idx >= 0 and oper == '+':
                    v = numbers.pop(idx) + numbers.pop(idx)
                    numbers.insert(idx, v)
                    del operator[idx]
                if idx >= 0 and oper == '-':
                    v = numbers.pop(idx) - numbers.pop(idx)
                    numbers.insert(idx, v)
                    del operator[idx]
        answer = max(answer, abs(*numbers))

    return answer

eval를 쓰면 간편할거라 생각했지만, eval은 보안에 취약성이 있기 때문에 안쓰는게 맞다고 판단했다. 그래서 방법을 찾다가 카카오에 올라온 풀이를 참고해서 구현했다.

예상 대진표

✏️ 내가 작성한 코드

import math
def solution(n,a,b):
    answer = 0
    while a != b:
        a = math.ceil(a/2)
        b = math.ceil(b/2)
        answer += 1
    return answer

어떻게 풀까 조금만 생각하니 방법이 떠올랐다. a,b 위치에서 /2를 하고 반올림을 한 값이 다음 라운드에서 자신의 참가 번호가 된다.

메뉴 리뉴얼

✏️ 내가 작성한 코드

import itertools
import collections

def solution(orders, course):
    answer = []
    for c in course:
        cases = []
        for o in orders:
            for i in itertools.combinations(o,c):
                cases.append(''.join(sorted(''.join(i))))
        x = collections.Counter(cases)
        if x:
            big_cnt = max(x.values())
        for v, n in x.items():
            if n == big_cnt and n > 1:
                answer.append(''.join(v))
    return sorted(answer)

문제에서 조합이라고 대놓고 키워드를 던져준다. 각 course별로 조합을 구해 Counter를 이용해 가장 많이 주문한 조합을 찾으면 된다. 다만 xy와 yx를 같은 조합이라고 봐야하는데 튜플이나 문자열은 정렬이 안되기 때문에 tuple -> str -> list(정렬하기) -> str로 타입을 변경하는 방법을 사용했다.

💡 흥미로운 코드

import itertools
import collections

def solution(orders, course):
    answer = []
    for c in course:
        cases = []
        for o in orders:
            cases = itertools.combinations(sorted(o),c):
        x = collections.Counter(cases)
        if x:
            big_cnt = max(x.values())
        for v, n in x.items():
            if n == big_cnt and n > 1:
                answer.append(''.join(v))
    return sorted(answer)

tuple -> str -> list(정렬하기) -> str를 하지 말고, 애초에 조합을 구할 때 sort를 하면 되는 거였다.

괄호 회전하기

✏️ 내가 작성한 코드

import collections

def solution(s):
    answer = 0
    q = collections.deque(s)
    for _ in range(len(s)):
        stack = []
        for i in q:
            if not stack:
                stack.append(i)
            elif i == ']'and stack[-1] == '[':
                stack.pop()
            elif i == ')'and stack[-1] == '(':
                stack.pop()
            elif i == '}'and stack[-1] == '{':
                stack.pop()
            elif i in '[{(':
                stack.append(i)
            else:
                break
        if not stack:
            answer += 1
        q.rotate(1)
    return answer

deque에 rotate 기능이 있는 걸 잊고 있었다. 이를 이용해서 괄호가 회전할 때마다 올바른 괄호 문자열이면 answer에 +1를 한다.

튜플

✏️ 내가 작성한 코드

def solution(s):
    answer = []
    s = s[2:-2].split('},{')
    s = sorted(s, key = len)
    for i in s:
        i = i.split(',')
        for j in i:
            if int(j) not in answer:
                answer.append(int(j))
    return answer

집합 원소의 길이를 기준으로 정렬한 뒤, 이미 answer에 들어있는 원소를 제외하고 하나씩 answer에 추가하면 된다. 집합원소에 많이 속해 있는 숫자 순으로 구해도 되는데 어떻게 해야하는지 방법을 알아내지 못했다. 다른 사람의 코드를 보니 Counter를 이용해서 구하는데 시간 복잡도를 생각하면 내 방법보다 더 좋은듯?

괄호 변환

✏️ 내가 작성한 코드

def corret(s):
    stack = []
    for i in s:
        if not stack or i == '(':
            stack.append(i)
        elif i == ')' and stack[-1] == '(':
            stack.pop()
    if not stack:
        return True
    else:
        return False

def reverse(s):
    result = ''
    for i in s:
        if i == '(':
            result += ')'
        elif i == ')':
            result += '('
    return result


def solution(p):
    l,r = 0, 0
    if not p:
        return p
    for i,v in enumerate(p):
        if v == '(':
            l += 1
        else:
            r += 1
        if l == r:
            u,v = p[:i+1], p[i+1:]
            if corret(u):
                return u + solution(v)
            else:
                answer = '(' + solution(v) + ')' + reverse(u[1:-1])    
                return answer

카카오에서는 항상 문제 해결 방법을 제시해주고 이를 잘 구현하는지 확인할 수 있는 문제를 1개씩 꼭 내는거 같다. 이 문제 또한, 문제에서 해결 방법까지 알려주는데, 그대로 구현만 하면 되서 쉽다. 다만, 좀 더 효율적인 방법이 있을거 같은데 그걸 아는게 어려운거 같다.

행렬 테두리 회전하기

✏️ 내가 작성한 코드

def solution(rows, columns, queries):
    answer = []
    graph = []
    for i in range(1, rows * columns + 1, columns):
        graph.append([j for j in range(i, i + columns)])

    for query in queries:
        x1, x2, y1, y2 = query
        tmp = []
        for i in range(x2-1,y2):
            tmp.append(graph[x1-1][i])
        for j in range(x1, y1):
            tmp.append(graph[j][y2-1])
        for p in range(y2-2,x2-2,-1):
            tmp.append(graph[y1-1][p])
        for q in range(y1-2,x1-1,-1):
            tmp.append(graph[q][x2-1])
        answer.append(min(tmp))
        tmp = tmp[-1:]+tmp[:-1]
        for i in range(x2-1,y2):
            graph[x1-1][i] = tmp.pop(0)
        for j in range(x1, y1):
            graph[j][y2-1] = tmp.pop(0)
        for p in range(y2-2,x2-2,-1):
            graph[y1-1][p] = tmp.pop(0)
        for q in range(y1-2,x1-1,-1):
            graph[q][x2-1] = tmp.pop(0)

    return answer

행렬의 테두리를 4부분으로 나누어서 값을 구하고 그 값을 rotate를 이용해 순환해주는 방식으로 구현했다.

가장 큰 수

✏️ 내가 작성한 코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = sorted(numbers, key=lambda x: (x[0],x[1%len(x)],x[2%len(x)],x[3%len(x)]) , reverse=True)
    return ''.join(numbers) if int(''.join(numbers)) != 0 else '0'

숫자의 각 자릿수별로 정렬을 하면 되는 아이디어는 빨리 생각났는데 막상 코드를 구현하기가 어려웠다. 왜냐하면 숫자의 자릿수가 다 다를 경우 해당 자릿수에 값이 없으면 오류가 나기때문이다. 그러다 누가 위의 방법처럼 나머지를 이용해서 푼 것을 보았다. 나머지를 이용하면 자릿수가 달라도 x[0]으로 계산 되기 때문에 상관없어진다.

전화번호 목록

✏️ 내가 작성한 코드

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
    return True

문제에서 접두어인 경우라는 걸 읽지 못해서 포함하는 전화번호면 다 찾아내는 알고리즘을 짰다... 문제를 자세히 읽어봐야겠다.

💡 흥미로운 코드

def solution(phoneBook):
    phone_book.sort()
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
    return True

이런 식으로 zip을 이용하여 바로 뒤의 문자와 비교할 수 있다. 또한, startswith는 처음 봤는데 문자열의 접두사가 같은지 배교해주는 메소드이다. 여기서 시작과 끝을 정할 수도 있다. 또한 endswith도 있다.

조이스틱

✏️ 내가 작성한 코드

def solution(name):
    if set(name) == {'A'}:
        return 0
    tmp = [min(ord(i) - ord('A'), ord('Z')+1 - ord(i)) for i in name]
    answer = sum(tmp)
    idx = 0
    while True:
        tmp[idx] = 0
        if not sum(tmp):
            return answer
        left, right = -1, 1
        while tmp[idx+right] == 0:
            right += 1
        while tmp[idx+left] == 0:
            left -= 1
        answer += -left if right > -left else right
        idx += left if right > -left else right

[min(ord(i) - ord('A'), ord('Z')+1 - ord(i)) for i in name]로 알파벳을 완성하는데 몇 번 위,아래 키를 눌러야 하는지를 구한 리스트이다. 처음에는 굉장히 복잡하게 구했는데 컴프리헨션을 사용하니 간단히 구현되었다.
left와 right로 두 개의 포인터를 두고 움직이며 가장 적게 움직인 값을 택하는 방식을 사용했다.

후보키

✏️ 내가 작성한 코드

import itertools 
import collections

def solution(relation):
    r, c = len(relation), len(relation[0])
    keys = []
    comb = []
    
    for i in range(1, c+1):
        comb += list(itertools.combinations(range(c), i)) 
    for i in comb:
        check_list = [tuple(row[j] for j in i) for row in relation]
        if len(set(check_list)) == len(check_list):
            keys.append(i)
    answer = set(keys[:])
    for k in range(len(keys)):
        for kn in range(k+1,len(keys)):
            if keys[k] != keys[kn] and set(keys[k]).issubset(set(keys[kn])):
                answer.discard(keys[kn])
    return len(answer)

combinations를 통해 모든 조합을 구한다.
set을 해서 중복된 값이 있는지 확인하여 중복된 값이 있으면 유일성에 위배되므로 제외한다.
issubset을 이용해 교집합인 경우 최소성에 위배되므로 제거한다.

위장

✏️ 내가 작성한 코드

import collections
import functools

def solution(clothes):
    a = collections.Counter([k for v, k in clothes])
    b = list(map(lambda x: x+1, dict(a).values()))
    answer = functools.reduce(lambda x,y: x*y,b,1)-1
    return answer

(의상종류+1)를 해서 모두 곱한후 모든 옷을 안 입는 경우(1)를 빼줘야 한다.
reduce는 reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])일 경우, ((((1+2)+3)+4)+5)를 계산 해준다. 즉, iterable한 객체를 왼쪽에서 오른쪽으로 function에 맞게 연산을 한다. reduce를 이용하면 간단히 풀수 있는 문제이다.
reference

💡 흥미로운 코드

import collections
import functools

def solution(clothes):
    a = collections.Counter([k for v, k in clothes])
    answer = functools.reduce(lambda x,y: x*(y+1),a,1)-1
    return answer

초기값이 1로 셋팅을 했기 때문에 y+1를 하면 굳이 이전에 모든 원소에 +1를 하지 않아도 된다.

배달

✏️ 내가 작성한 코드

import collections 

def solution(N, road, K):
    dist = [0,0]+[float('INF')]*(N-1)
    graph = collections.defaultdict(list)
    for n1,n2,t in road:
        graph[n1].append((n2,t))
        graph[n2].append((n1,t))        
    queue = collections.deque([1])
    while queue:
        n= queue.popleft()
        for wn,wt in graph[n]:
            if dist[wn] > dist[n]+wt:
                dist[wn] = dist[n]+wt
                queue.append(wn)
    return len([d for d in dist if d <= K])-1

다익스트라 알고리즘으로 bfs구현하면 된다. 노드 1에서 노드 N까지의 시간을 dist에 담아 가장 최소 시간일때 dist를 업데이트하면 된다.

H-Index

✏️ 내가 작성한 코드

def solution(citations):
    citations.sort(reverse=True)
    for i in range(len(citations),0,-1):
        if list(map(lambda x: x>=i, citations[:i])).count(True) == i:
            return i
    return 0

citations를 먼저 정렬을 한다. i는 논문의 수를 의미하는데, map을 이용하여 논문의 수이상인 값을 찾아 비교한다.

카펫

✏️ 내가 작성한 코드

def solution(brown, yellow):
    for i in range(1,int((brown+yellow)**0.5+1)):
        if not (brown+yellow)%i:
            if (i-2) *((brown+yellow)//i-2) == yellow:
                return [(brown+yellow)//i,i]

(brown+yellow)의 공약수들 중 -2를 더하고 두 값을 곱해서 yellow가 나오면 그 값이 정답이다.

순위 검색

✏️ 내가 작성한 코드

import bisect, itertools, collections

def bisearch(p,q):
    return bisect.bisect_left(p,q)

def make_group(infos):
    group = collections.defaultdict(list)
    for v in infos:
        for i in range(5):
            for j in itertools.combinations(v[:-1],i):
                group[''.join(j)].append(int(v[-1]))
    return group
            
def solution(info, query):
    infos = sorted([i.split() for i in info], key=lambda x: int(x[-1]))
    querys = [q.replace('and', '').replace('-','').split() for q in query]
    answer = [0]*len(querys)
    group = make_group(infos)
    keys = group.keys()
    for i in range(len(querys)):
        if ''.join(querys[i][:-1]) in keys:
            points = group[''.join(querys[i][:-1])]
            n = bisearch(points,int(querys[i][-1]))
            answer[i] = len(points)-n    
    return answer

효율성을 통과하기 위해 info를 점수 기준으로 오름차순으로 정렬했다. query는 필요없는 and와 -를 제외했고, 속도를 조금 더 높이고 싶어 미리 answer의 크기를 할당했다.
make_group 함수를 통해 info의 요소마다 모든 경우의 수를 만들어 group에 넣어줬다.
group은 딕셔너리로 언어, 직군, 경력, 소울푸드를 key로 해당 키에 포함되는 점수들을 value로 생성했다.
정렬된 값들은 binary search로 빠르게 원하는 값을 찾을 수 있으므로 bisect 모듈을 사용했다.

스킬트리

✏️ 내가 작성한 코드

from collections import deque

def solution(skill, skill_trees):
    answer = len(skill_trees)
    for tree in skill_trees:
        que = deque(skill)
        for t in tree:
            if que and t in skill and t != que[0]:
                answer -= 1
                break
            elif que and t == que[0]:
                que.popleft()
    return answer

선행 스킬 순서를 que에 넣고 값을 비교하여 같을 경우 que에서 빼고, 다르면서 선행스킬트리에 있는 스킬일 경우 잘못된 스킬트리이기 때문에 바로 break를 걸어 다음 스킬트리를 비교하면 된다.

피보나치 수

✏️ 내가 작성한 코드

def solution(n):
    x,y = 0,1
    for i in range(n):
        x, y = y, x+y
    return x%1234567

최댓값과 최솟값

✏️ 내가 작성한 코드

def solution(s):
    s = list(map(int,s.split()))
    return str(min(s))+' '+str(max(s))

구명보트

✏️ 내가 작성한 코드

from collections import deque

def solution(people, limit):
    people.sort()
    que = deque(people)
    answer = 0
    while que:
        if len(que) == 1:
            answer += 1
            return answer
        if que[-1]+que[0] > limit:
            que.pop()
        elif que[-1]+que[0] <= limit:
            que.pop()
            que.popleft()
        answer += 1
    return answer

가장 작은 사람 + 가장 큰 사람으로 매칭을 해야한다. 그래서 정렬을 하고 가장 작은 사람과 큰 사람을 효율적으로 리스트에서 제외 시킬 수 있도록 que를 생성한다. 만약 가장 작은 사람 + 가장 큰 사람이 limit보다 클 경우 가장 큰 사람은 무조건 혼자서 배를 타야한다. 가장 작은 사람 + 가장 큰 사람이 limit보다 작을 경우 두 사람을 함께 배에 태울 수 있다.

💡 흥미로운 코드

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

투 포인터를 생각 했었는데 구현하기 귀찮고 큐로 푸는 것이 더 깔끔할 거라 생각했는데 투 포인터로 푸는 것이 훨씬 코드도 깔끔하고 속도도 빠르다.

최솟값 만들기

✏️ 내가 작성한 코드

def solution(A,B):
    A.sort()
    B.sort(reverse=True)
    return sum(map(lambda x: x[0]*x[1], zip(A,B)))