나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42579 🔑 딕셔너리, 힙 music 딕셔너리 "장르" : [(-재생 횟수, 고유 번호), (-재생 횟수, 고유 번호)] value의 리스트는 힙이고 재생 횟수를 음수값으로 넣어 최대 힙 구현 play 딕셔너리 "장르" : 총 재생 횟수 앨범에 먼저 수록할 장르를 구하기 위한 딕셔너리 play 딕셔너리를 총 재생 횟수 기준으로 정렬 1번 조건 : 노래가 많이 재생된 장르를 먼저 수록합니다. 정렬한 play 리스트에서 pop() 2번 조건 : 장르 내에서 많이 재생된 노래를 먼저 수록합니다. music["장르"]에서 heappop() 장르 내에 속한 곡이 1개 일 때 처리를 try-except..

문제 : https://www.acmicpc.net/problem/1765 🔑 union, find 입력으로 친구가 들어오면 서로 union 원수가 들어오면 양방향 그래프로 원수 관계를 생성 생성된 원수 관계 그래프를 이용해 "내 원수의 원수도 내 친구이다." 조건을 해결한다. 나 → 내 원수 → 내 원수의 원수 이렇게 거쳐서 (나, 내 원수의 원수)를 union from collections import defaultdict n = int(input()) m = int(input()) def union(a, b): x = find(a) y = find(b) parent[y] = x def find(x): if parent[x] == x: return x parent[x] = find(parent[x])..

문제 : https://www.acmicpc.net/problem/1043 🔑 union, find [유니온 파인드] 진실을 아는 사람들을 모두 같은 번호로 묶어준다. union 각 파티마다 오는 사람들을 모두 같은 번호로 묶어준다. union 진실을 아는 사람들이 오는 파티면 1번 과정에서의 그룹에 포함된다. 진실을 아는 사람들의 그룹과, 각 파티의 그룹이 겹치지 않으면 거짓말을 한다. find 거짓말할 수 있는 파티의 개수를 세면 끝 ✨ 예외로 진실을 아는 사람이 없으면 파티의 횟수를 출력하고 종료했다. import sys input = sys.stdin.readline n, m = map(int, input().split()) parent = [i for i in range(n+1)] true = ..

문제 : https://www.acmicpc.net/problem/1541🔑 더하기 먼저더하기 먼저 모두 하고 나서 빼기를 진행'-'를 기준으로 split을 한다.55-50+40 → ['55', '50+40']요소가 숫자로만 구성된 문자열이면 정수로 형변환요소에 '+'가 있으면 '+'를 기준으로 split을 하고 더함 → [55, 90] 만들어진 리스트 요소들을 전부 빼면 정답 ✨ n = input()s = n.split('-')for i in range(len(s)): if '+' in s[i]: tmp = map(int, s[i].split('+')) s[i] = sum(tmp) else: s[i] = int(s[i]) answer = s[0]f..

문제 : https://www.acmicpc.net/problem/2307 🔑 다익스트라, 최단 경로 저장 처음에 n개의 노드를 하나씩 다 막아봤다. (그래도 풀리긴 함) 그다음에는 용의자가 이동하는 최단 경로만 검문을 해서 시간을 줄였다. 2316ms → 852ms 최단 경로를 딕셔너리 형식으로 저장 ex) 6 : 3 이면 3을 지나서 6으로 감 이렇게 저장해서 해당 경로를 매개 변수로 넘겨주고 이쪽 경로로는 못 가게 조건 추가 최단 경로를 전부 검문해 보고 용의자가 탈출하는데 가장 오래 걸리는 시간을 구하면 끝 ✨ import sys from collections import defaultdict from heapq import heappop, heappush input = sys.stdin.read..

문제 : https://www.acmicpc.net/problem/1202 🔑 힙, 우선순위 큐 1. 입력받은 보석들을 무게 기준 오름차순 정렬 2. 가방도 오름차순 정렬 3. 가장 작은 가방부터 시작해서 이 가방에 담을 수 있는 보석이면 힙에 보석 가격을 담는다. (음수로 담는다. 최대힙) 4. 담긴 보석이 있으면 가장 비싼 보석을 선택한다. 3, 4번 과정을 가방 개수만큼 반복한다. 크기가 작은 가방부터 담기 때문에 보석을 모두 담고 뽑아내는 게 가능하게 된다. 크기가 2인 가방에 담을 수 있는 보석이면 크기가 3인 가방에도 담을 수 있다. 가방 크기 = [2, 10] 보석 = [(1, 65), (2, 99), (5, 23)] 가방 크기 2일 때 힙 = [-99, -65] -99를 뽑아서 정답으로 올..

문제 : https://www.acmicpc.net/problem/1874 🔑 스택 나열해야 하는 수 보다 현재 숫자가 같거나 작으면 스택에 넣어놓는다. + 스택 제일 위의 수가 나열해야 하는 수와 같으면 스택에서 꺼낸다. - +, - 를 바로 출력하지 않고 저장해 놓고 수열을 만들 수 있으면 출력을 한다. 끝 ✨ import sys input = sys.stdin.readline n = int(input()) numbers = [int(input()) for _ in range(n)] stack = [] idx = 1 answer = [] for i in numbers: while idx

문제 : https://www.acmicpc.net/problem/1414 🔑 최소 비용 신장 트리, 프림 알고리즘 입력되는 문자열을 문제 형식에 맞게 숫자로 변환해서 그래프를 생성한다. ord() 함수 사용 변환한 랜선 길이의 총 합도 구해놓는다. 그리고 프림 알고리즘을 사용해 최소 비용을 구할 때마다 전체 랜선의 길이에서 빼준다. 남은 랜선의 길이가 정답인데 방문을 못한 노드가 있으면 -1을 출력한다. 더 쉬운 프림 알고리즘 문제 : https://study-yoon.tistory.com/235 import sys from heapq import heappop, heappush from collections import defaultdict input = sys.stdin.readline n = in..