[Python] 프로그래머스 고득점 Kit 전체 문제 풀이

문제 풀러 가기 : programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

각각의 풀이에 대한 설명은 이후에 정리 할 예정.

문제가 갱신된 것들이 있어서 10/21 부터 22일까지 전체 문제를 다시 풀어보았습니다.

(필요하신 분들은 ctrl+f로 검색해서 보시면 됩니다.)

 

해시

 

1. 완주하지 못한 선수

from collections import defaultdict
def solution(participant, completion):
    d = defaultdict(int)
    for p in participant:
        d[p] += 1
    for c in completion:
        d[c] -= 1
        if d[c] == 0:
            d.pop(c)
    return "".join(d.keys())

 

2. 전화번호 목록

def solution(phone_book):
    len_number = [[] for _ in range(21)]
    answer = True
    for number in phone_book:
        len_number[len(number)].append(number) 
    for i in range(1,21):
        for str1 in len_number[i]:
            for j in range(i+1,21):
                for str2 in len_number[j]:
                    if str1 == str2[:i]:
                        return False
    return True

 

3. 위장

def solution(clothes):
    d = dict()
    for name,item in clothes:
        d[item] = d.get(item,0) + 1
    
    answer = 1
    for item,n in d.items():
        answer *= (n+1)
    return answer-1

 

4. 베스트 앨범

from collections import defaultdict
def solution(genres, plays):
    genre_play = defaultdict(int)
    song_play = defaultdict(list)
    
    for i in range(len(genres)):
        genre_play[genres[i]] += plays[i]
        song_play[genres[i]].append((i,plays[i]))
    
    genre_lst = sorted(genre_play.items(),key=lambda x:x[1],reverse=True)
    answer = []
    for genre,_ in genre_lst:
        musics = sorted(song_play[genre],key=lambda x:x[1],reverse=True)[:2]
        for idx,nplay in musics:
            answer.append(idx)
    return answer

 

스택/큐

 

1. 주식가격

def solution(prices):
    answer = [len(prices)-i-1 for i in range(len(prices))]
    for i in range(len(prices)):
        for j in range(i+1,len(prices)):
            if prices[i] > prices[j]:
                answer[i] = j-i
                break
    return answer

 

2. 기능개발

def solution(progresses, speeds):
    stack = []
    d = dict()
    for i in range(len(progresses)):
        cost = (100 - progresses[i])//speeds[i]
        if (100-progresses[i]) % speeds[i] > 0:
            cost += 1
        if len(stack) == 0 or cost > stack[-1]:
            stack.append(cost)
            d[cost] = 1
        else:
            d[stack[-1]] += 1
 
    return [v for k,v in sorted(d.items())]

 

3. 다리를 지나는 트럭

from collections import deque
def solution(bridge_length, weight, truck_weights):
    trucks = deque(truck_weights)
    wait = deque()
    sum_weight = 0
    time = 0
    while trucks:
        time += 1
        while wait and wait[0][0] <= time:
            t,w = wait.popleft()
            sum_weight -= w
        if sum_weight+trucks[0] <= weight:
            truck = trucks.popleft()
            wait.append((bridge_length+time,truck))
            sum_weight += truck
    return wait[-1][0]

 

4. 프린터

from collections import deque
def solution(priorities, location):
    d = [0]*11
    queue = deque()
    for i,p in enumerate(priorities):
        d[p] += 1
        queue.append((i,p))
    
    idx = 0
    while True:
        i,j = queue.popleft()
        if sum(d[j+1:])>0:
            queue.append((i,j))
        elif i == location:
            return idx+1
        else:
            idx += 1
            d[j] -= 1

 

힙(HEAP)

 

1. 더 맵게

import heapq
def solution(scoville, K):
    answer = 0
    scoville.sort()
    while scoville[0] < K:
        food1 = heapq.heappop(scoville)
        if scoville:
            food2 = heapq.heappop(scoville)
        else:
            return -1
        heapq.heappush(scoville,food1+food2*2)
        answer += 1
    return answer

 

2. 디스크컨트롤러

def solution(jobs):
    wait = 0
    curr = 0
    jobs.sort(key=lambda x:x[1])
    visited = set()
    while len(visited) < len(jobs):
        chk = True
        for i in range(len(jobs)):
            if i in visited:
                continue
            if jobs[i][0] <= curr:
                curr += jobs[i][1]
                wait += curr - jobs[i][0]
                visited.add(i)
                chk = False
                break
        if chk:
            curr += 1
    return wait // len(jobs)

 

3. 이중우선순위큐

import heapq
def solution(operations):
    minq = []
    maxq = []
    removed = set()
    for oper in operations:
        op,digit = oper.split(" ")
        digit = int(digit)
        if op == "I":
            heapq.heappush(minq,digit)
            heapq.heappush(maxq,-digit)
        elif digit == -1 and minq:
            temp = heapq.heappop(minq)
            while temp in removed and minq:
                temp = heapq.heappop(minq)
            removed.add(temp)
        elif digit == 1 and maxq:
            temp = -heapq.heappop(maxq)
            while temp in removed and maxq:
                temp = -heapq.heappop(maxq)
            removed.add(temp)
    
    maxval = 0
    minval = 0
    while maxq:
        temp = -heapq.heappop(maxq)
        if temp not in removed:
            maxval = temp
            break
    
    while minq:
        temp = heapq.heappop(minq)
        if temp not in removed:
            minval = temp
            break
            
    return [maxval,minval]

 

정렬

 

1. K번째 수

def solution(array, commands):
    answer = []
    for i,j,k in commands:
        answer.append(sorted(array[i-1:j])[k-1])
    return answer

 

2. 가장 큰 수

def solution(numbers):
    numbers.sort(key=lambda x: str(x)*3, reverse=True)
    if numbers[0] == 0:
        return "0"
    else:
        return "".join(map(str,numbers))

 

3. H-Index

def solution(citations):
    citations.sort()
    n = len(citations)
    for h in range(n):
        if citations[h] >= n-h: ## n-h보다 크거나 같은 n-h개, h보다 작거나 같은 h개의 논문들
            return n-h
    return 0

 

완전탐색

 

1. 모의고사

def solution(answers):
    first = [1,2,3,4,5]
    second = [2,1,2,3,2,4,2,5]
    third = [3,3,1,1,2,2,4,4,5,5]
    ret = [0,0,0]
    for i in range(len(answers)):
        if answers[i] == first[i%5]:
            ret[0] += 1
        if answers[i] == second[i%8]:
            ret[1] += 1
        if answers[i] == third[i%10]:
            ret[2] += 1
    maxval = max(ret)
    answer = []
    for i in range(len(ret)):
        if ret[i] == maxval:
            answer.append(i+1)
    return answer

 

2. 소수 찾기

from itertools import permutations
def prime_check(x):
    if x<2:
        return 0
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            return 0
    return 1
    
def solution(numbers):
    numbers = list(numbers)
    cand = set()
    for i in range(1,len(numbers)+1):
        for string in permutations(numbers,i):
            cand.add(int(''.join(string)))
            
    answer = 0
    for x in list(cand):
        answer += prime_check(x)
    return answer

 

3. 카펫

def solution(brown, yellow):
    n = brown + yellow
    for i in range(1,(n+1)//2):
        if n % i ==0:
            j = n // i
            if i*2+j*2-4 == brown: ##가로둘레*2 + 세로둘레*2 - 4(외곽 네모칸 4개 중복 되므로 4로 빼줌)
                return [j,i]
    return False

 

탐욕법(GREEDY)

 

1. 체육복

def solution(n, lost, reserve):
    reallost = set(lost) - set(reserve)
    realres = set(reserve) - set(lost)
    for r in sorted(list(realres)):
        if r-1 in reallost:
            reallost.remove(r-1)
        elif r+1 in reallost:
            reallost.remove(r+1)
    return n - len(reallost)

 

2. 큰 수 만들기

def solution(number, k):
    answer = []
    for i in range(len(number)):
        while answer and k>0 and number[i] > answer[-1]:
            answer.pop()
            k -= 1
        answer.append(number[i])
    return ''.join(answer[:len(answer)-k])

 

3. 조이스틱

def dfs(goal,idx,ans,finish):
    global minval
    if finish == 0:
        minval = min(ans,minval)
    else:
        for i in range(len(goal)):
            if goal[i]:
                temp = goal[i]
                goal[i] = 0
                ## 좌우이동 cost + 위아래이동 cost
                dfs(goal,i,ans+min(abs(idx-i),abs(len(goal)+idx-i))+temp,finish-temp)
                goal[i] = temp
 
def solution(name):
    global minval
    goal = []
    for x in list(map(ord, name)):
        goal.append(min(abs(65 - x), abs(91 - x)))
    minval = 1e9
    dfs(goal,0,0,sum(goal))
    return minval

 

4. 구명보트

def solution(people, limit):
    people.sort()
    p1 = 0
    p2 = len(people)-1
    couple = 0
    while p1<p2:
        if people[p1] + people[p2] <= limit:
            p1 += 1
            couple += 1
        p2 -= 1
    return len(people) - couple

 

5. 섬 연결하기

def find_parent(parent,x):
    if parent[x] == x:
        return x
    else:
        return find_parent(parent,parent[x])
 
def solution(n, costs):
    edges = sorted([(c,a,b) for a,b,c in costs])
    parent = [x for x in range(n)]
    answer = 0
    bridge = 0
    for c,a,b in edges:
        a = find_parent(parent,a)
        b = find_parent(parent,b)
        if a != b:
            if a<b:
                parent[b] = a
            else:
                parent[a] = b
            answer += c
    return answer if sum(parent) == 0 else -1

 

6. 단속카메라

def solution(routes):
    routes.sort(key=lambda x:x[1])
    last_camera = -30000
    answer = 0
    for s,e in routes:
        if last_camera < s:
            last_camera = e
            answer += 1
    return answer

 

동적 프로그래밍(Dynamic Programming)

 

1. N으로 표현

def solution(N, number):
    if N == number:
        return 1
 
    memo = [set() for _ in range(9)]
    for i in range(1,len(memo)):
        memo[i].add(N*int(str(1)*i))
 
    for i in range(2, 9):
        for j in range(1, i):
            temp = list(memo[j])
            for k in range(1,i):
                if j+k != i:
                    continue
                temp2= list(memo[k])
                for x in temp:
                    for y in temp2:
                        memo[i].add(x + y)
                        memo[i].add(x * y)
                        memo[i].add(x - y)
                        if y != 0:
                            memo[i].add(x // y)
        if number in memo[i]:
            return i
    return -1

 

2. 정수삼각형

def solution(triangle):
    for i in range(1,len(triangle)):
        for j in range(i+1):
            left = triangle[i-1][j-1] if j!=0 else 0
            right = triangle[i-1][j] if j!=i else 0
            triangle[i][j] = triangle[i][j] + max(left,right)
    return max(triangle[-1])

 

3. 등굣길

def solution(m, n, puddles):
    board = [[0]*(m+1) for _ in range(n+1)]
    for x,y in puddles:
        board[y][x] = -1
    
    board[1][1] = 1
    for x in range(1,n+1):
        for y in range(1,m+1):
            if x==1 and y==1:
                continue
            if board[x][y] != -1:
                board[x][y] = max(0,board[x-1][y]) + max(0,board[x][y-1])
                
    return board[n][m]%1000000007

 

4. 도둑질

def solution(money):
    a = [money[0],money[0]]
    b = [0,money[1]]
    for i in range(2,len(money)-1):
        a.append(max(a[i-2]+money[i],a[i-1]))
        b.append(max(b[i-2]+money[i],b[i-1]))
    answer = max(a[-1],b[-2]+money[-1])
    return answer

 

깊이/너비 우선탐색(DFS/BFS)

 

1. 타겟넘버

def dfs(idx,ans):
    global answer,nb,tg
    if idx == len(nb):
        if ans==tg:
            answer += 1
        return
    else:
        dfs(idx+1,ans+nb[idx])
        dfs(idx+1,ans-nb[idx])
        return
    
def solution(numbers, target):
    global answer,nb,tg
    nb = numbers
    tg = target
    answer = 0
    dfs(0,0)
    return answer

 

2. 네트워크

def solution(n, computers):
    parent = [x for x in range(n)]
    for i in range(n): ## start
        for j in range(n): ## end
            if i == j:
                continue
            if computers[i][j]: ##edge
                for k in range(n):
                    if parent[k] == parent[i]: ##start -> end update
                        parent[k] = parent[j]
    return len(set(parent))

 

3. 단어 변환

def WordDist(w1,w2):
    dist = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            dist += 1
            if dist>1:
                return False
    return True if dist == 1 else False
 
def dfs(begin,target,words,count,visited):
    global minval
    if begin == target:
        minval = min(minval,count)
    else:
        for i in range(len(words)):
            if i in visited:
                continue
            if WordDist(begin,words[i]):
                visited.add(i)
                dfs(words[i],target,words,count+1,visited)
                visited.remove(i)
 
def solution(begin, target, words):
    global minval
    minval = 51
    dfs(begin,target,words,0,set())
    return minval if minval<51 else 0

 

4. 여행경로

from collections import defaultdict
def solution(tickets):
    route = defaultdict(list)
    for s,a in tickets:
        route[s].append(a)
    for k in route.keys():
        route[k].sort(reverse=True)
    
    ## dfs using stack
    stack = ["ICN"]
    visit = []
    while stack:
        top = stack[-1]
        if route[top]: ##갈 수 있는 곳이 있다면(빈 리스트가 아니라면)
            stack.append(route[top].pop())
        else: ##없다면 가장 마지막 노드
            visit.append(stack.pop())
    return visit[::-1]

 

이분탐색

 

1. 입국심사

def check(t,times):
    ret = 0
    for time in times:
        ret += t//time
    return ret
    
def solution(n, times):
    answer = 0
    left = 0
    right = max(times)*n ##가장 오래걸리는 사람이 모두 처리하는 상황
    while left <= right:
        mid = (left+right)//2
        chk = check(mid,times)
        if chk < n:
            left = mid+1
        else: ##n명보다 많이 처리할 수 있다면(answer는 될 수 있지만, 더작은 것 찾기)
            answer = mid
            right = mid-1
    return answer

 

2. 징검다리

def check(term, rocks):
    count = 0
    start = 0
    minval = 1e9
    for i in range(len(rocks)):
        if rocks[i] - start<term: #start위치부터 못건널때까지 체크(지나가는 돌들 체크)
            count += 1
        else:
            minval = min(minval,rocks[i]-start)
            start = rocks[i]
    return count,minval
 
 
def solution(distance, rocks, n):
    answer = 0
    rocks.append(distance)
    rocks.sort()
 
    left = 0
    right = distance
    while left <= right:
        mid = (left + right) // 2
        count,minval = check(mid, rocks)
        if count > n:
            right = mid - 1
        else:
            answer = minval
            left = mid + 1
    return answer

 

그래프

 

1. 가장 먼 노드

def solution(n, edge):
    graph = [set() for _ in range(n + 1)]
    for s, e in edge:
        graph[s].add(e)
        graph[e].add(s)
 
    queue = set([1])
    visited = set([1])
 
    while len(visited) < n:
        next_queue = set()
 
        while queue:
            node = queue.pop()
            next_queue |= graph[node]
 
        queue = next_queue - visited
        visited |= queue
 
    return len(queue)

 

2. 순위

import copy
def solution(n, results):
    linked = [[set(),set()] for _ in range(n+1)]
    for w,l in results:
        linked[w][1].add(l)
        linked[l][0].add(w)
    
    answer = 0
    for i in range(1,n+1):
        front,back = copy.deepcopy(linked[i])
        visited = set()
        
        while front:
            linked[i][0] |= front
            visited |= front
            next_front = set()
            for _ in range(len(front)):
                next_front |= linked[front.pop()][0]
            front |= (next_front - visited)
        
        while back:
            linked[i][1] |= back
            visited |= back
            next_back = set()
            for _ in range(len(back)):
                next_back |= linked[back.pop()][1]
            back |= (next_back - visited)
        
        if len(linked[i][0]) + len(linked[i][1]) == n-1:
            answer += 1
    return answer

 

3. 방의 개수

from collections import defaultdict
def solution(arrows):
    dx = [-1,-1,0,1,1,1,0,-1]
    dy = [0,1,1,1,0,-1,-1,-1]
    x,y = 0,0
    answer = 0
    visited = set([(0,0)])
    edges = defaultdict(int)
    for d in arrows:
        for _ in range(2):
            nx,ny = x+dx[d], y+dy[d]
            if (nx,ny) in visited and edges[(x,y,nx,ny)] == 0:
                answer += 1
            edges[(x,y,nx,ny)] += 1
            edges[(nx,ny,x,y)] += 1
            visited.add((nx,ny))
            x,y = nx,ny
    return answer