Coding Test/programmers

실패율 (list.count() 함수)

def solution(N, stages): result = {} a = len(stages) for i in range(1,N+1): if a != 0: cnt = stages.count(i) # stages에서 i의 개수 result[i] = cnt/a a-=cnt else: result[i] = 0 return sorted(result, key=lambda x: result[x], reverse=True) def solution(N, stages): answer = [] a = [0] * (N+1) for x in stages: a[x - 1] += 1 b = {} for i in range(N): if sum(a[i:]) != 0: b[i+1]=a[i]/sum(a[i:]) else: b[i+1]=..

괄호변환 (문자열, 구현)

""" p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다. 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다. """ def solution(p): if p=='': # 1 return p r=True c=0 for i in range(len(p)): # 2 if p[i]=='(': c-=1 else: c+=1 if c>0: # 순서 올바르지않음 r=False if c==0: if r: # 3 return p[:i+1]+solution(p[i+1:]) else: # 4 return '('+solution(p[i+1:])+')'+''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) )) def r(w):..

비밀지도 (리스트 zip(), 문자열 rjust() 메서드)

def solution(n, arr1, arr2): answer = [] for i, j in zip(arr1, arr2): answer.append(str(bin(i|j)[2:]).rjust(n, '0').replace('1', '#').replace('0', ' ')) return answer def solution(n, arr1, arr2): answer = [] a1 = [] a2 = [] for i in range(n): t1=bin(arr1[i])[2:] t1='0'*(n-len(t1))+t1 a1.append(t1) t2=bin(arr2[i])[2:] t2='0'*(n-len(t2))+t2 a2.append(t2) for i in range(n): temp=['#']*n for j in ra..

캐시 (구현)

def solution(cacheSize, cities): answer=0 q=[] if cacheSize==0: return len(cities)*5 for x in cities: x = x.upper() if x in q: answer+=1 q.remove(x) q.append(x) else: answer+=5 if len(q)>cacheSize-1: q=q[1:] q.append(x) return answer

문자열 압축 (구현)

def solution(s): answer=len(s) for i in range(1, len(s)//2+1): res="" prev=s[0:i] # 앞에서부터 i 문자열 추출 cnt=1 for j in range(i, len(s), i): # i만큼 증가시키며 이전 문자열과 비교 if prev==s[j:j+i]: cnt+=1 # 이전 상태와 동일하면 증가 else: # 다른 문자열이 나왔다면, 압축 불가 res += str(cnt)+prev if cnt>=2 else prev # 초기화 prev=s[j:j+i] cnt=1 # 남아있는 문자열 res+=str(cnt)+prev if cnt>=2 else prev answer=min(answer, len(res)) return answer

합승 택시 요금 (플로이드 워셜)

플로이드 워셜 알고리즘 분석 [11403] 경로 찾기 (플로이드-워셜) 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시 karla.tistory.com def solution(n, s, a, b, fares): INF = 10000000 answer = INF graph = [[INF for j in range(n)] for i in range(n)] for f in fares: i, j, k = f graph[i-1][j-1]=k graph[j-1][i-1]=k print(graph) for k in range(n): for i in range(n): for j in range(n)..

합승 택시 요금 (다익스트라)

[1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙) 다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 karla.tistory.com from heapq import heappush, heappop def solution(n, s, a, b, fares): INF = int(1e9) answer = INF graph = [[] for _ in range(n + 1)] for f in fares: i, j, k = f graph[i].append((j, k)) graph[j].append((i, k)) def dijk(start): # s를 시작점으로하는 다익..

메뉴 리뉴얼 (조합)

from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for c in course: temp = [] for order in orders: combi = combinations(sorted(order), c) temp += combi cnt = Counter(temp) if len(cnt) > 1: m = max(cnt.values()) for i in cnt: if cnt[i] >= 2 and cnt[i] == m: answer.append("".join(i)) answer.sort() return answer print(solution(["ABCFG", "AC"..

신규 아이디 추천 (문자열, 정규식)

def solution(new_id): answer = '' # 1 new_id = new_id.lower() # 2 for n in new_id: if n.islower() or n.isdigit() or n in ['-', '_', '.']: answer += n # 3 while ".." in answer: answer = answer.replace('..', '.') # 4 if answer[0] == '.': answer = answer[1:] if answer[-1] == '.': answer = answer[:-1] # 5 if len(answer) == 0: answer = 'a' # 6 if len(answer) >= 16: answer = answer[:15] # 7 if len(ans..

광고삽입 (누적합)

def str_to_int(time): # 시간 문자열 -> 숫자 변환 h, m, s = time.split(':') return int(h) * 60 * 60 + int(m) * 60 + int(s) def int_to_str(time): # 시간 숫자 -> 문자열 변환 h = time // 3600 h = '0' + str(h) if h < 10 else str(h) time = time % 3600 m = time // 60 m = '0' + str(m) if m < 10 else str(m) time = time % 60 s = '0' + str(time) if time < 10 else str(time) return h + ':' + m + ':' + s def solution(play_time..