one Book a Day

조합 검사 중 조건을 만족할 시 조합의 부분조합을 구해 중복되는것이 있으면 세주지 않았습니다. from itertools import combinations def solution(relation): n = len(relation[0]) cnt = 0 checked = set() for i in range(1, n + 1): for comb in combinations([k for k in range(n)], i): dicts = set() tmp = [] for row in relation: tmp.append(''.join(row[each] for each in comb)) flag = 0 for c in tmp: if flag: break if c not in dicts: dicts.add(c) e..

단순히 조건이 여러개 주어지는 걸 보고 교집합으로 풀려고 했다. 하지만 넓은 범위의 쿼리가 여려개 주어진다면 매번 교집합 연산을 해주어야 한다는 점에서 효율성이 부족했다. 오히려 상태조건이 4 * 3 * 3 * 3 으로 몇개 되지 않았기 때문에 dp로 배열을 만들거나 경우의 수에 따라 최초 배열에 삽입시켜 준 후 정렬하는게 약 3배정도 빨랐다. 조건이 적을 땐 모든 조건에 대해 입력해두는게 후에 쿼리를 수행함에 있어 유리한걸 잊지말자. 쿼리문제. 상태인자별로 미리 정리하자. 검색을 단순화 하자. 아래는 교집합 코드 그 아래 상태조사 코드 def solution(info, query): answer = [] lang_set = defaultdict(set) job_set = defaultdict(set) ..

최초 문자열 길이의 반까지 올려주면서 단위별로 탐색 def solution(s): n = len(s) answer = n for unit in range(1, n//2 + 1): cnt = 1 now = s[:unit] tmp_answer = '' for i in range(unit, n + unit, unit): if s[i:i + unit] == now: cnt += 1 else: if cnt > 1: tmp_answer += str(cnt) + now else: tmp_answer += now now = s[i:i + unit] cnt = 1 answer = min(answer, len(tmp_answer)) return answer

요구하는 순서대로 구현 def solution(p): if not p: return p n = len(p) left, right = 0, 0 for i in range(n): if p[i] == '(': left += 1 else: right += 1 if left == right: break u = p[:i+1] v = p[i+1:] stack = [] for char in u: if char == '(': stack.append(char) else: if stack: stack.pop() else: new_u = u[1:-1] tmp = '' for char in new_u: if char == '(': tmp += ')' else: tmp += '(' return '(' + solution(v) +..

sets에 조합 출현 갯수 cnt ans_set에 2번이상이고 최고 많이 나온 comb 입력 answer에 ans_set에 들어간 comb만 추출 후 정렬 반환 from collections import defaultdict from itertools import combinations def solution(orders, course): answer = [] sets = defaultdict(int) for order in orders: order = sorted(list(order)) for num in course: for new_comb in combinations(order, num): sets[''.join(list(new_comb))] += 1 ans_set = {num: [] for num..

규칙에 따라 parsing def solution(new_id): answer = '' for char in new_id: if char.isalpha(): answer += char.lower() elif char == '.' and answer and answer[-1] != '.': answer += '.' elif char.isdigit() or char in '-_': answer += char if not answer: answer += 'a' elif len(answer) > 15: answer = answer[:15] if answer[-1] == '.': answer = answer[:-1] while len(answer) < 3: answer = answer + answer[-1] re..

dfs로 각 순열의 카드 순서를 맞춰가며 카드를 2장씩 뒤집는 로직. 백트래킹, dijkstra로 최단 거리 측정. shift이동은 ctrl_move로 for문 이용. from collections import defaultdict from heapq import heappush, heappop from itertools import permutations def solution(board, r, c): def ctrl_move(x, y, dx, dy, visited): for i in range(1, 4): nx, ny = x + dx * i, y + dy * i if (nx, ny) in visited and not visited[(nx, ny)]: return (nx, ny) if dx == 1 a..

위클리 3주차이며 네이버 기출문제 중 하나인 퍼즐조각 채우기입니다. 가로세로퍼즐에 fit이 맞는 block을 채우는 문제로 이 문제는 빈칸없이 꽉 채워야 하기 때문에 hashing을 이용할 수 있을 것이라 생각했고 각 모양을 tuple형태의 key로 dictionary에서 관리하는 식으로 풀었습니다. from collections import defaultdict, deque def solution(game_board, table): answer = 0 n = len(game_board) delta = ((-1, 0), (0, 1), (1, 0), (0, -1)) def bfs(graph, start_x, start_y, num): ret = [(0, 0)] q = deque() q.append((sta..

보자마자 price(1~count) 가 생각나서 제출. 했으나 제출 누르자마자 음수인 경우 예외처리 안해줬다는 생각이 나서 결과보니 아니나다를까 testcase 하나 오답.. 음수처리 해주었더니 통과 def solution(price, money, count): answer = price * count * (count + 1) // 2 - money if answer < 0: answer = 0 return answer

방에 들어갔다 나왔다. def solution(enter, leave): n = len(enter) answer = [0] * (n+1) enter_idx = 0 leave_idx = 0 room = set() while leave_idx < n: if leave[leave_idx] in room: room.discard(leave[leave_idx]) leave_idx += 1 continue if enter[enter_idx] not in room: for man in room: answer[man] += 1 answer[enter[enter_idx]] = len(room) room.add(enter[enter_idx]) enter_idx += 1 return answer[1:]