LOEWEN LOEWEN

문제 링크 뭔가 좀 기교가 가득해보이는 코드... 흑백요리사도 아니고 코딩테스트인데 그게 나쁜 건 아니지만.from collections import defaultdictdef solution(genres, plays): genre_cnt = defaultdict(list) genre_sum = defaultdict(int) for i, zip_ in enumerate(zip(genres, plays)) : genre, play = zip_ genre_cnt[genre].append((play, i)) genre_sum[genre] += play sorted_genres = sorted(genre_sum, key=la..

문제 링크 정답 코드def solution(n, k, cmd): prev_of = {i: i - 1 for i in range(n)} post_of = {i: i + 1 for i in range(n)} post_of[n - 1] = None prev_of[0] = None deleted = [] idx = k for command in cmd: if command[0] == 'U': X = int(command.split()[1]) for _ in range(X): idx = prev_of[idx] elif command[0] == 'D': ..

문제 링크 쉽게 쉽게로봇은 두 칸을 차지하며, 상하좌우로 움직일 수 있고, 90도로 회전할 수 있다. 이때 로봇 두 칸 모두 회전의 축이 될 수 있다. 일단은 로봇의 위치를 다음과 같이 저정할 것이다. 가로로 있으면 False, 세로로 있으면 True로 저장하고, 두 칸 중 X축, Y축 값이 더 작은 좌표를 대표위치값으로 저장할 것이다. 또한 회전을 위해서는 조건 체크를 꼼꼼히 해야 한다:  회전을 하면 좌표값은 다음과 같이 된다:  회전하는 그림을 합쳐보면 : 즉, 회전을 위해서는 남동, 남서, 북동 방향을 탐색하고, 북서 방향은 탐색할 필요 없다.회전을 위한 if문이 길어지는 걸 방지하기 위해 컨디션 변수를 선언하여 이를 if문에 활용할 것이다.#컨디션 변수들 먼저 선언south_east = cx ..

문제 링크 정답 코드def solution(gems): gems_unique_count = len(set(gems)) gems_dict = dict() s, e = 0, 0 gems_dict[gems[0]] = 1 answer = [0, len(gems) - 1] while e

문제 링크 두 개의 queue를 관리하라하라는 대로 하면 되지만, 생각보다 까다롭고 섬세한 문제이다. 이게 또 은근히 실전 코테에서는 어려운 요소이다.import heapqfrom collections import dequedef solution(jobs): n = len(jobs) jobs.sort() jobs = deque(jobs) total_time, current_time = 0, 0 queue = [] while jobs or queue : while jobs and jobs[0][0]

문제 링크 무식한 방법 (시간복잡도 초과)이 문제는 상당히 쉽지 않은데, 사실 첫눈에는 쉬워보인다. 그냥 하라는 대로 하는 건 어렵지 않기 때문이다. 문제는 시간복잡도이다.from collections import Counterdef solution(land, P, Q): sqz_land = [] for wall in land : sqz_land += wall min_h = min(sqz_land) max_h = max(sqz_land) sqz_land_counter = Counter(sqz_land) min_cost = float('inf') for flattened_h in range(min_h, max_h+1) : ..

문제 링크 하란다고 진짜로 하지 말기요즘 이런 식의 문제를 많이 풀어서 느껴지는 거지만, 문제에서 정의내리는 "부분수열"을 진짜로 만들어서 그것이 스타수열인지 체크하고... 하는 것은 불가능하다. 리스트에서 원소 하나 삭제하고 할 때마다 O(N)인데, 그걸 2^N 번을 반복해서 탐색한다?*왜 2^N번 반복이냐면 nC0 + nC1 + nC2 + ... + nCn = 2^n 이니까 O(N*2^N) 같은 건, N이 24 이하여야 가능하다.  그런데 N이 500,000까지 치솟을 수 있는 상황에서 저 복잡도는 그냥 말도 안 되는 소리이다. 언제나 본질을 기억하자. 부분수열을 만들어서 뭘 한다고 해서 "진짜로" 그걸 만들 필요는 없다. 정답 코드from collections import Counter, deque..

문제 링크 "실제로 구현할 필요 없음" 구현, 특히 빡구현 문제들을 많이 풀고, 또한 BFS 문제를 많이 접하다보면 으레 까먹는 중요한 사실이 있다. 문제가 자신만의 상상의 나래를 펼쳐 죠르디가 기둥과 보를 짓는 이러한 문제를 풀 때, 기둥과 보를 설치하거나 철거하란다고 진짜로 설치하거나 철거할 필요는 없다는 것이다. 그런데 사실 그 유혹에 넘어가는 게 생각보다 쉽다. 왜냐하면, n이 겨우 100 이하이기 때문에, 100 * 100 행렬을 만들어도 공간복잡도가 10,000 밖에 되지 않아서, 마치 이게 정답인 길 같아 보이기 때문이다.  그러나 지금 이 문제에서 중요한 것은, 설치/철거 명령어 시퀀스에서 feasible한 명령만을 취한 후, 이를 sort하여 반환하는 것 뿐이다. 실제 map에 이를 구현..