Algorithm Problem/Python

[python] 백준 - 12764. 싸지방에 간 준하

🤔문제 해결 우선순위 큐 대기중인 사람과 먼저 사용중인 사람 중 가장 빨리 끝나는 곳과 비교 대기중인 사람보다 늦게 끝나면 새로운 자리로 배정 기존의 사람이 끝나는 곳이 있으면 그게 여러 곳이 있으면 끝나는 곳을 다 뽑아서 남는 자리 우선순위 큐에 넣는다. 더 이상 없을 때 남는 자리 우선순위 큐에서 자리르 하나 뽑아서 배정한다. 사용중인 컴퓨터 끝나는 시간과 자리번호가 담긴 우선순위 큐 남아있는 자리가 담긴 우선순위 큐 이렇게 해서 두개를 사용했다. 우선순위 큐를 두개 써야해서 헷갈렸던 문제 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) logs = [list(map(int, input().split())) for ..

[python] 백준 - 11085. 군사 이동

🤔문제 해결 크루스칼 C에서 출발! 갈 수 있는 곳을 찾아서 우선순위 큐에 넣는다. 우선순위 큐에서 넓이가 가장 넓은 녀석을 뽑는다. 거기서 또 갈 수 있는 곳을 찾아서 큐에 넣는다. (단, 재방문 X) V를 만나면 끝! 노드를 이동하는 동안 최소값을 계속 갱신해준다. (답을 찾아야하므로) 💻소스 코드 import sys from collections import defaultdict import heapq input = sys.stdin.readline P, W = map(int, input().split()) # P개의 지점, W개의 길 C, V = map(int, input().split()) # C 백준수도, V 큐브수도 # 인접노드 만들기 nodes = [input() for _ in range..

[python] 백준 - 19598. 최소 회의실 개수

🤔문제 해결 우선순위큐 회의를 오름차순으로 정렬한다. 사용한 회의실의 끝나는 시각을 배열로 만든다. 우선순위큐로 사용할 것 회의를 하나씩 꺼내서 가장 빨리 끝나는 회의실과 회의 시작 시간을 비교 회의 시작 시간이 더 빠르면 회의실 추가 회의 시작 시간이 더 늦으면 해당 회의실의 끝나는 시각 업데이트 🍞 heapreplace는 가장 작은 요소를 빼고, 추가할 요소를 집어 넣는다. ( pop 후 push 를 합친것 - 더 빠르다고 한다.) 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(..

[python] 백준 - 1013. Contact

🤔문제 해결 정규표현식 정규표현식 문제인줄 모르고 열심히 풀었는데.... 하🤣 💥 match 를 쓰면 포함되어있는걸 찾기 때문에 fullmatch 를 써서 전체가 맞는 지 확인해줘야한다. match로도 맞는 구간이 나오기 때문에 답을 찾을 순 있지만 fullmatch가 있기 때문에 저걸로 찾으면 된다. 💻소스 코드 import re import sys input = sys.stdin.readline for tc in range(int(input())): p = re.compile('(100+1+|01)+') # 정규표현식 준비 m = p.fullmatch(input().strip()) # 매칭 print('YES') if m else print('NO') 📕문제 확인 출처: BACKJOON ONLINE ..

[python] 백준 - 1174. 줄어드는 숫자

🤔문제 해결 못풀다가 문제 유형에 백트래킹이 있길래 힌트를 얻어 백트래킹으로 구현해봤다. 아이디어는 현재 숫자의 끝자리보다 낮은 숫자들을 뒤에 추가하는 재귀함수를 만들었다. 현재 764이면 7640 => 끝 7641 => 76410 => 끝 7642 => 76420 => 76421 => 764210 => 끝 마지막에 sort만 해주면 빠른 시간 내에 모든 경우의 수를 순서대로 다 얻을 수 있다. 가끔 안풀리면 다른 사람의 코드를 참고하기 전에 유형으로 힌트를 얻어보자😀 💻소스 코드 N = int(input()) # 백트래킹을 이용한 문제 풀이 def bt(cur): answer.append(int(cur)) for j in range(0, int(cur[-1])): # 현재 숫자의 끝자리보다 낮은 숫자들..

[python] 백준 - 1148. 단어 만들기

🤔문제 해결 딕셔너리에 퍼즐의 각 알파벳을 키, 그 알파벳의 개수와 사용된 횟수의 딕셔너리를 벨류로 가진다. 퍼즐에 있는 알파벳으로 낱말을 만들 수 있다면 퍼즐에서 사용될 알파벳의 used_cnt 를 +1 해준다. 위와 같은 결과가 나오게 되고, used_cnt 가 가장 적은 값들, 가장 많은 값들을 알파벳 오름차순으로 출력해준다. 💻소스 코드 import pprint import sys input = sys.stdin.readline # 인풋 받아서 단어 or 퍼즐 따로 배열로 만드는 함수 (두번 반복할거 같아서 함수로 만듦) def input_func(arr, sign): arr = [] while True: input_value = input().strip() if input_value == sig..