Total

카드 짝 맞추기 (순열 permutations, BFS, DFS)

""" 1,2,3 짝을 맞춰야하는데 123,132,231,213,312,324 어떤 순서로 맞추는게 빠른지 -> 순열 구해서 인덱스 dfs 123도 어떤 1로 먼저 가야되는지 -> 2가지 경우 bfs 최솟값 출력 """ from collections import defaultdict, deque from itertools import permutations from copy import deepcopy def bfs(board, start, end): if start==end: return 0 q, visit = deque([[start[0], start[1], 0]]), {start} while q: # BFS x, y, c = q.popleft() for dx, dy in [(0,1),(0,-1),(..

뉴스 클러스터링 (문자열 리스트 합집합, 교집합, 중복 허용 다중집합)

from collections import Counter def solution(str1, str2): answer = 0 str1,str2=str1.upper(), str2.upper() a=[] for i in range(1,len(str1)): if str1[i-1].isalpha() and str1[i].isalpha(): a.append(str1[i-1]+str1[i]) b=[] for i in range(1,len(str2)): if str2[i-1].isalpha() and str2[i].isalpha(): b.append(str2[i-1]+str2[i]) if len(a)==len(b)==0: return 65536 a = Counter(a) b = Counter(b) c = list((a..

다트 게임 (구현)

def solution(dartResult): n='' temp=[] for i in range(len(dartResult)): x = dartResult[i] if x.isdecimal(): n+=x elif x.isalpha(): j=1 if x=='D': j=2 elif x=='T': j=3 temp.append(int(n)**j) n='' else: if x=='*': if len(temp)>1: temp[-2]=temp[-2]*2 temp[-1]=temp[-1]*2 elif x=='#': temp[-1]=temp[-1]*(-1) return sum(temp)

압축 (ascii_uppercase, 알파벳 딕셔너리)

from string import ascii_uppercase def solution(msg): answer = [] c = [i for i in range(1,27)] a= dict(zip(ascii_uppercase,c)) w='' for x in msg: w+=x if w not in a: a[w]=len(a)+1 answer.append(a[w[:-1]]) w = w[-1] answer.append(a[w]) return answer

실패율 (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)..