문제 링크 https://www.acmicpc.net/problem/18870 문제 해설 Idea Sort 집합을 통해 압축한 unique한 좌표 목록을 정렬시키고, 정렬된 리스트 내에서 좌표와 인덱스를 딕셔너리로 맵핑 Time Complexity O(N Log N) = 13,000,000 Data Size N: 1 <= int <= 1,000,000 X: -10^9 <= int <= 10^9 해설 코드 1 2 3 4 N = int(input()) X = list(map(int, input().split())) xtoi = {x:i for i,x in enumerate(sorted(set(X)))} print(' '.join(map(lambda x: str(xtoi[x]), X)))
문제 링크 https://www.acmicpc.net/problem/1931 문제 해설 Idea Sliding Window 슬라이딩 윈도우의 전형적인 문제로, 끝 시간을 기준으로 시간을 정렬해서 겹치지 않는 수를 계산 Time Complexity O(N) = 100,000 Data Size N: 1 <= int <= 100,000 t1,t2: 0 <= int <= 2^31-1 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys input = sys.stdin.readline N = int(input()) times = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: [x[1],x[0]]) count, end_time = 0, 0 for t1,t2 in times: if t1 >= end_time: count += 1 end_time = t2 print(count)
문제 링크 https://www.acmicpc.net/problem/15686 문제 해설 Idea Combinations 최대 집의 개수가 100, 최대 치킨집의 개수가 13으로 매우 적은 경우의 수를 가지고 있기 때문에, 모든 조합에 대한 완전탐색을 통해 최소 거리를 계산 초기에는 집에 대한 치킨 거리가 작은 치킨집을 우선적으로 선발해서, 폐업하지 않은 치킨집에 대한 치킨 거리의 최소 합을 계산했지만 틀림 이후 combinations 모듈을 활용한 완전탐색을 통해 통과 Time Complexity O(N * nCr) ~ 100,000 Data Size N: 2 <= int <= 50 M: 1 <= int <= 13 cell in (0, 1, 2) count(house): 1 <= int < 2N count(chicken): M <= int <= 13 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 from itertools import combinations import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/1927 문제 해설 Idea Heapq 파이썬 heapq 모듈 자체가 최소힙이기 때문에 해당하는 기능을 활용하여 구현 Time Complexity O(Log N) = 16 Data Size N: 1 <= int <= 100,000 x: 0 <= int < 2^31 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import heapq import sys input = sys.stdin.readline N = int(input()) arr = list() for _ in range(N): x = int(input()) if x > 0: heapq....
문제 링크 https://www.acmicpc.net/problem/1780 문제 해설 Idea Divide and Conquer 2차원 배열의 요소를 완전탐색하면서 동일한 값으로 구성되지 않을 경우, 행렬을 9등분하여 재귀적 호출 수행 처음 시도에서는 행렬을 매번 슬라이싱하면서 전달하여 시간 초과가 발생 행렬의 시작 인덱스 번호를 전달하고 길이만큼 참조하는 방식으로 시간 복잡도 개선 Data Size N: 1 <= int <= 3^7 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys input = sys....