[프로그래머스] Level3 문제풀이

프로그래머스 Level3을 정답률 높은 순으로 푼 문제 모음입니다.

 

# 야근 지수

- 효율성 테케 통과 못한 풀이

def solution(n, works):
    answer = 0
    works.sort(reverse=True)
    if sum(works) <= n:
        return 0
    
    i = 0
    count = 0 
    while True:  
        if n == 0 or i == len(works)-1:
            break
        
        if n > 0:
            works[works.index(max(works))] -= 1
            n -= 1
    
    for a in works:
        answer += a * a 
    
    return answer

- 최대힙 써서 효율성 통과

import heapq

def solution(n, works):
    answer = 0
    works.sort(reverse=True)
    if sum(works) <= n:
        return 0
    
    # 최대 힙 
    works = [-w for w in works]
    heapq.heapify(works) # 힙으로 변환
    
    for _ in range(n):
        #print(works)
        i = heapq.heappop(works)
        i += 1
        heapq.heappush(works, i)
          
    for a in works:
        answer += a * a 
    
    return answer

 

# 네트워크 - dfs

def solution(n, computers):
    
    def dfs(i):
        visited[i] = True
        
        for j in range(n):
            if not visited[j] and computers[i][j] == 1:
                dfs(j)
                
    answer = 0
    visited = [False for _ in range(n)]
 
    for a in range(n): 
        if not visited[a]:
            dfs(a)
            answer += 1
    
    
    return answer

 

# 최고의 집합 - 연산 아이디어

def solution(n, s):
    answer = []
    
    if s < n: 
        return [-1]
     
    while n >= 1:
        answer.append(s // n)
        s -= s // n 
        n -= 1 
        
    answer.sort()
        
    return answer

# 이중우선순위 큐

import heapq
def solution(operations):
    answer = []
    heap = []
    for s in operations:
        command, num = s.split(" ") 
        num = int(num) 
        if command == "I":
            heapq.heappush(heap, num) 
        else:
            if heap and num == -1:
                heapq.heappop(heap) # 최소값 pop
            elif heap and num == 1: 
                heap.pop() # 최대값 pop
     
    if not heap:
        return [0, 0]
    else: 
        heap.sort()
        answer.append(heap[-1])
        answer.append(heap[0])
    return answer

# 정수사각형 - DP

def solution(triangle):
    answer = 0
    dp = []
    li = []
    for i in range(len(triangle)): 
        li = []
        for _ in range(i+1):
            li.append(0)
        dp.append(li) 
     
    dp[0][0] = triangle[0][0] 
    for i in range(len(triangle)):
        for j in range(i):
            dp[i][j] = max(dp[i][j], dp[i-1][j] + triangle[i][j]) # 전꺼 + 지금꺼
            dp[i][j+1] = dp[i-1][j] + triangle[i][j+1] # 다음단계 = 전꺼 + 다음단계꺼
             
    answer = max(dp[-1])
    
    return answer

 

# 등굣길 - DP(~로 나눈 나머지를 return 어쩌구면 대부분 DP문제임)

def solution(m, n, puddles):
    answer = 0
    puddles = [[x, y] for [y, x] in puddles] # 좌표 꺼꾸로
    
    dp = [[0] * (m+1) for _ in range(n+1)] # 1부터 시작이니까
    dp[1][1] = 1 # 시작 위치
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            if [i, j] in puddles:
                dp[i][j] = 0 # 길없음
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
                    
    answer = dp[n][m] 
    return answer

 

# 단어 변환 - bfs - 변환 가능한 문자만 큐에 넣기

from collections import deque
def solution(begin, target, words):
    answer = 0
    q = deque()
    q.append([begin, 0])
    visited = [False for _ in range(len(words))]
    
    while q:
        begin, count = q.popleft()
        if begin == target:
            answer = count
            break
        for i in range(len(words)):
            check_count = 0
            if not visited[i]:
                for a, b in zip(words[i], begin):
                    if a != b:
                        check_count += 1
                if check_count == 1:
                    q.append([words[i], count+1])
                    visited[i] = True
                    
    return answer

# 단속 카메라 - 그리디 - 차량 나가는 걸 기준으로 정렬 *

def solution(routes):
    answer = 0 
    routes.sort(key = lambda x : x[1]) 
    target = -30000
    count = 0
    for a in routes:
        if a[0] > target:
            count += 1
            target = a[1]
            
         
    return count

 

# 베스트 앨범 - 딕셔너리, 정렬 사용

def solution(genres, plays):
    answer = []
    genres_set = set(genres) 
    dic = dict()
    counts = [] 
    lis = []
    for i in genres_set:
        count = 0
        li = []
        for j in range(len(genres)):
            if i == genres[j]:
                count += plays[j]
                li.append(j)
        dic[count] = li 
                  
    dic = sorted(dic.items(), reverse=True)   
    
    for a, b in dic:
        c = []
        for i in b:
            c.append([plays[i], i])
        c.sort(key = lambda x : (-x[0], x[1])) # 많이 재생된 순, 고유번호 낮은 순 정렬
        if len(c) >= 2:
            for i in range(2):
                answer.append(c[i][1])
        else:
            for i in c:
                answer.append(i[1])
                 
        
    return answer

# 보석쇼핑 - 효율성이 중요한 문제, 투포인터 이용해서 해결

def solution(gems):
    answer = []
    n = len(set(gems))
    short = len(gems) + 1
    li = [] 
    start, end = 0, 0
    contain = {} # 딕셔너리 
    if n == 1:
        return [1, 1]
    
    while end < len(gems):
        if gems[end] not in contain:
            contain[gems[end]] = 1
        else:
            contain[gems[end]] += 1
        
        end += 1
        
        if len(contain) == n:
            while start < end:
                if contain[gems[start]] > 1:
                    contain[gems[start]] -= 1
                    start += 1
                elif (end - (start+1) + 1) < short:
                    short = end - start
                    answer = [start+1, end]
                    break
                else:
                    break
         
                       
    return answer