[프로그래밍 강의]_프로그래머스 고득점 Kit 예제

파트1. 해시(Hash) 대표 문제 풀이: 완주하지 못한 선수 (0 / 3)

• 사전(dictionary) / O(1)

d = {"leo" : 30, "kiki" : 62, "eden" : 5}
x = d["leo"]
d["leo"] = 58 # 새로 갱신 가능

def solution(participant, completion):
    d = {}
    for x in participant:
    	d[x] = d.get(x, 0) + 1
    for x in completion:
    	d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0]
    answer = dnf[0]
    return answer

• 정렬사용 / O(NlogN)

def solution(participant, completion):
	participant.sort()
    completion.sort()
    for i in range(len(completion)):
    	if participant[i] != completion[i]:
        	return participant[i]
        return participant[len(participant)-1]

파트2. 탐욕법(Greedy) 대표 문제 풀이: 체육복 (0 / 3)

def solution(n, lost, reserve):
   	u = [1] * (n + 2)
    for i in reserve:
    	u[i] += 1
   	for i in lost:
    	u[i] -= 1
    for in range(1, n + 1):
    	if u[i - 1] == 0 and u[i] == 2:
        	u[i - 1:i + 1] = [1, 1]
        elif u[i] == 2 and u[i + 1] == 0:
        	u[i:i + 2] = [1, 1]
    return len([x for x in u[1:-1] if x > 0])

def solution(n, lost, reserve):
	s = set(lost) & set(reserve) # set을 사용
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):
    	if x - l in l:
        	l.remove(x - 1)
        elif x + 1 in l:
        	l.remove(x + 1)
    return n - len(l) 

파트3. 정렬(Sort) 대표 문제 풀이: 가장 큰 수 (0 / 3)

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key = lambda x : (x * 4)[:4], reverse=True)
    answer = ''.join(numbers)
    return answer

시간초과, 수정한 결과

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key = lambda x : (x * 4)[:4], reverse=True)
    if numbers[0] == '0':
    	answer = '0'
    else:
    	answer = ''.join(numbers)
    return answer

파트4. 탐욕법(Greedy) 대표 문제 풀이: 큰 수 만들기 (0 / 3)

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
    	while len(collected) > 0 and collected[-1] < num and k > 0:
        	collected.pop()
            k -= 1
        if k == 0:
        	collected += list(number[i:])
            break
        collected.append(num)
    
    collected = collected[:-k] if k > 0 else collected
    answer = ''.join(collected)
    return answer

파트5. 힙(Heap) 대표 문제 풀이: 더 맵게 (0 / 3)

	import heapq
    heapq.heapify(L)
    m = heapq.heappop(L)
    heapq.heappush(L, x)

import heapq

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

파트6. 동적계획법(Dynamic Programming) 대표 문제 풀이: N으로 표현 (0 / 3)

def solution(N, number):
    s = [set() for x in range(8)]
    for i, x in enumerate(s, start = 1):
    	x.add(int(str(N) * i))
    for i in range(1, len(s)):
    	for j in range(i):
        	for op1 in s[j]:
            	for op2 in s[i - j - 1]:
                	s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                    	s[i].add(op1 // op2)
        if number in s[i]:
        	answer = i + 1
            break
    else:
    	answer = -1
    return answer

파트7. 깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이: 여행경로 (0 / 3)

def solution(tickets):
    routes = {}
    for t in tickets:
    	routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for r in routes:
    	routes[r].sort(reverse = True)
    stack = ["ICN"]
    path = []
    while len(stack) > 0:
    	top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
        	path.append(stack.pop())
        else:
        	stack.append(routes[top][-1])
            routes[top] = routes[top[:-1]]
    return path[::-1]