본문 바로가기
728x90

알고리즘14

[python] 프로그래머스_카카오21_메뉴 리뉴얼 (완전탐색, combinations) 문제 풀이 itertools 에서 combinations 을 import 해서 문자열의 조합을 이용한다. combinations 를 사용하면 아래처럼 각 튜플에 하나의 조합이 각 원소별로 쪼개져서 출력되므로, 필요에 따라 후처리가 필요하다. a = 'abcd' b = list(combinations(a,2)) print(b) for i in range(len(b)): b[i] = ''.join(b[i]) print(b) 문제는 order 문자열을 순회하면서 각 주문별로 모든 조합의 개수를 foodMap으로 카운트하고, 세트의 메뉴 개수별 max값을 카운트해둔다. 그리고 마지막에 course를 순회하면서 foodMap에서 value값이 maxCnt와 동일한 key만 answer에 append하고 마지막에 .. 2022. 2. 21.
[python] 백준3190_뱀 (구현) 문제 풀이 이차원 리스트상의 맵에서 뱀이 이동하도록 리스트의 특정 위치에서 동,남,서,북의 위치로 이동하는 기능을 구현해야 한다. 또한, 뱀의 머리가 뱀의 몸에 닿는 순간 종료해야 하므로, 매 시점마다 뱀이 존재하는 위치를 항상 이차원 리스트에 기록해야 한다. n = int(input()) k = int(input()) data= [[0]*(n+1) for _ in range(n+1)] info = [] for _ in range(k): a,b = map(int,input().split()) data[a][b] = 1 l = int(input()) for _ in range(l): x,c = input().split() info.append((int(x),c)) # 동,남,서,북 dx = [0,1,0,-.. 2022. 2. 15.
[python] 프로그래머스_신고 결과 받기 (구현) 문제 풀이 def solution(id_list, report, k): answer = [0]*len(id_list) report = list(set(report)) id = dict() ans_dict = dict() for i in range(len(id_list)): id[id_list[i]]=0 ans_dict[id_list[i]]=0 for i in report: a = i.split(' ')[0] b = i.split(' ')[1] id[b] +=1 for i in range(len(report)): a = report[i].split(' ')[0] b = report[i].split(' ')[1] if id[b] >= k: ans_dict[a] += 1 for i in range(len(id.. 2022. 2. 15.
[python] 프로그래머스_실패율 (정렬) 문제 풀이 우선 스테이지 번호와 실패율을 함께 저장할 딕셔너리 answer을 만든다. 스테이지를 정렬하고 스테이지에서 for문을 돌면서 각 인덱스를 카운트해서 0개이면 answer에 0을, 그렇지 않으면 answer에 실패율을 계산해서 넣고 유저수는 카운트했던 수는 빼준다. for문을 다 돌고 answer을 실패율에 따라 정렬해서 리턴해준다. def solution(N, stages): answer = {} stages.sort() numUser = len(stages) for i in range(1,N+1): cnt = stages.count(i) if cnt==0: answer[i]=0 else: answer[i]=(cnt/numUser) numUser=numUser-cnt answer = dict(.. 2022. 2. 15.
[python] 프로그래머스_프린터 (스택큐) 문제 풀이 큐에 우선 순위, index 순으로 저장하고 while 문을 돌면서 큐에서 하나씩 빼고 우선순위에 더 높은게 큐에 남아있으면 현재 값을 다시 큐에 집어넣는다. 그렇지 않은 경우에 result에 +1 하고 현재 index가 location과 동일하면 while 문 break하고 result를 리턴해준다. from collections import deque def solution(priorities, location): result = 0 d = deque([(v,i) for i,v in enumerate(priorities)]) # priority, index 순으로 que에 저장 while len(d): item = d.popleft() if d and max(d)[0] > item[0]: .. 2022. 2. 14.
[python] 프로그래머스_문자열 압축 (완전 탐색) 문제 풀이 입력으로 주어지는 문자가 1000 이하이기 때문에 완전탐색을 수행할 수 있다. 길이가 N인 문자열이 입력되면 1부터 N/2 까지의 모든 수를 단위로 하여 문자열을 압축하는 모든 방법을 확인하고, 가장 짧게 압축되는 길이를 출력하면 된다. 구체적인 방법은 step 사이즈로 문자열을 잘라서 prev에 저장해두고, 다음 위치를 step 사이즈로 자르고 prev와 똑같은지 비교하면서 진행한다. def solution(s): answer = len(s) # step을 1부터 문자열 길이 반까지 늘려가며 확인 for step in range(1, len(s)//2 +1): compressed = "" prev = s[0:step] # 앞에서 부터 step 만큼의 문자열 추출 count = 1 # step.. 2022. 2. 14.
728x90

티스토리툴바