Coding Test/programmers

순위검색 (해시, 딕셔너리)

info 최대 50,000, query 최대 100,000로 이중 for문 불가 조합으로 모든 경우의 수 키만들고 점수를 값으로 넣음 쿼리 잘라서 리스트 만들고 키, 점수 구분 키값 있으면 키 값에 따른 점수 리스트 조회 점수 리스트에서 이분 탐색으로 인덱스 찾음 ( 몇번째 인지) 점수 리스트 길이에서 찾은 인덱스 값 빼면 몇명인지 구할 수 있음 키 값 없으면 0명 from itertools import combinations from bisect import bisect_left def solution(info, query): answer = [] infoDict={} for x in info: xl = x.split(" ") info_key=xl[:-1] score =int(xl[-1]) for i ..

1,2,3 떨어뜨리기 (트리, 구현)

분석 1) 엣지 정보로 트리 리스트 생성 {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [7], 6: [8, 9, 10], 7: [], 8: [], 9: [], 10: []} 2) 리프노드에 떨어지는 숫자 갯수 카운트 리스트 생성 (leaf) 용도 : 순서 리스트 생성할 때 타겟값과 비교해서 몇바퀴 돌아야하는지 확인하기 위해 {4: 0, 7: 0, 8: 0, 9: 0, 10: 0} 3) 하위 인덱스 방향 관리 리스트 생성 (r) 용도 : 하위노드중 몇번째로 가는지 계산해서 가기 위해 {1: 0, 2: 0, 3: 0, 4: -1, 5: 0, 6: 0, 7: -1, 8: -1, 9: -1, 10: -1} 4) 리프노드 떨어지는 순서 리스트 생성 (order) 용도 : 리프노드 돌면..

파괴되지 않은 건물 (누적합, numpy)

""" 1 ≤ board의 행의 길이 (= N) ≤ 1,000 1 ≤ board의 열의 길이 (= M) ≤ 1,000 1 ≤ skill의 행의 길이 ≤ 250,000 """ import numpy as np def solution(board, skill): answer = 0 # 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수 n=len(board) m=len(board[0]) temp=[[0 for j in range(m+1)] for i in range(n+1)] for t,r1,c1,r2,c2,d in skill: tt= -d if t==1 else d temp[r1][c1]+=tt temp[r1][c2+1]-=tt temp[r2+1][c1]-=tt temp[r2+1][..

파괴되지 않은 건물 (누적합, 2차원 합배열)

""" 1 ≤ board의 행의 길이 (= N) ≤ 1,000 1 ≤ board의 열의 길이 (= M) ≤ 1,000 1 ≤ skill의 행의 길이 ≤ 250,000 """ def solution(board, skill): answer = 0 # 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수 n = len(board) m = len(board[0]) temp = [[0 for j in range(m + 1)] for i in range(n + 1)] for t, r1, c1, r2, c2, d in skill: tt = -d if t == 1 else d temp[r1][c1] += tt temp[r1][c2 + 1] -= tt temp[r2 + 1][c1] -= tt te..

주차 요금 계산 (구현)

def calTime(stime, etime): st, sm = map(int, stime.split(":")) et, em = map(int, etime.split(":")) mtemp = em - sm if mtemp < 0: et -= 1 em += 60 mtemp = em - sm ttemp = et - st minutes = ttemp * 60 + mtemp return minutes def solution(fees, records): # 1 ≤ records의 길이 ≤ 1,000 import math answer = [] # 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return # 차번호, 시간순 정렬 r = [] for i in records: r.appe..

양궁대회 (재귀)

from copy import deepcopy max_diff, max_board = 0, [] def solution(n, info): def dfs(ascore, lscore, cnt, idx, board): global max_diff, max_board if cnt > n: return if idx > 10: diff = lscore - ascore if diff > max_diff: board[10] = n - cnt max_board = board max_diff = diff return if cnt < n: board2 = deepcopy(board) board2[10 - idx] = info[10 - idx] + 1 dfs(ascore, lscore + idx, cnt + info[10 -..

양궁대회 (조합, 완전 탐색)

순열조합 이터레이터 인자 결과 product() p, q, … [repeat=1] 데카르트 곱(cartesian product), 중첩된 for 루프와 동등합니다 permutations() p[, r] r-길이 튜플들, 모든 가능한 순서, 반복되는 요소 없음 combinations() p, r r-길이 튜플들, 정렬된 순서, 반복되는 요소 없음 combinations_with_replacement() p, r r-길이 튜플들, 정렬된 순서, 반복되는 요소 있음 예 결과 product('ABCD', repeat=2) AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD permutations('ABCD', 2) AB AC AD BA BC BD CA CB CD DA DB DC..

양과 늑대 (DFS)

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr """ 2 ≤ info의 길이 ≤ 17 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다. """ def solution(info, edges): answer = [] n = len(info) # 노드수 def dfs(scnt, wcnt)..

신고 결과 받기 (구현)

array [] tuple () dictionary {} def solution(id_list, report, k): answer = [0] * len(id_list) r = {x: 0 for x in id_list} for x in set(report): r[x.split()[1]] += 1 for x in set(report): s, e = x.split() if r[e] >= k: answer[id_list.index(s)] += 1 return answer

K진수에서 소수의 개수 구하기

def solution(n, k): import math # k진수 변환 word = '' while n: word = str(n % k) + word n = n // k arr = word.split("0") answer = 0 for i in arr: if len(i) == 0: continue if int(i) < 2: continue flag = True for j in range(2, int(math.sqrt(int(i)) + 1)): if int(i) % j == 0: flag = False break if flag: answer += 1 return answer print(solution(437674,3))