Kakao

2024년 5월 24일 알고리즘 문제풀이 문제 후보키 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 from itertools import combinations # 최소성을 만족하는지 확인하는 함수 # 검증하는 조합 target의 부분집합이 이미 찾은 조합 answer_array에 포함되어 있는지 확인 # 포함되어 있으면 target은 최소성을 만족하지 않음 def validate(answer_array,target): for i in answer_array: if set(i).issubset(target): return False return True def solution(relation): answer = [] n = len(relation) m = len(relation[0]) arr = [ i for i in range(m)] for i in range(m): # 모든 속성 조합을 구함. idx = list(combinations(arr,i+1)) for q in idx: # 유일성을 만족하는지 확인 # 속성의 값을 이은 문자열을 set에 넣어 중복을 제거 # 중복이 없다면 유일성을 만족 check = set() for j in range(n): tmp = "" for k in q: tmp += relation[j][k] check.add(tmp) # set의 길이가 n과 같다면 중복이 없단 의미로 유일성을 만족 if len(check) == n: # 최소성을 만족하는지 확인 if validate(answer,q): answer.append(q) return len(answer)

2024년 5월 21일 알고리즘 문제풀이 문제 오픈채팅방 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 def solution(record): n = len(record) answer = [] # 들어오거나 나가는 행동을 저장할 배열 arr = dict() # 각 아이디의 최종 닉네임을 저장하기 위한 배열 name = dict() # 데이터를 가공하기 위한 반복문 for i in range(n): # 데이터 분리 data = list(record[i].split(" ")) tmp = dict() # 들어오고 나가는 행동이면 저장 if data[0] != "Change": tmp["message"] = data[0] tmp["id"] = data[1] arr[i] = tmp # 들어올 때 닉네임을 바꾸는 경우 추적 if data[0] == 'Enter': name[data[1]] = data[2] # 닉네임을 바꾸는 행동일땐 저장하지 않고 이름만 갱신 else: name[data[1]] = data[2] # 출력하기 위한 반복문 for i in range(n): # i번째일때 바꾸는 행동이였으면 arr에 해당 키 값은 존재하지 않음 if i not in arr: continue # 각 아이디의 최종 닉네임으로 출력 if arr[i]["message"] == "Enter": c = name[arr[i]["id"]] + "님이 들어왔습니다." elif arr[i]["message"] == "Leave": c = name[arr[i]["id"]] + "님이 나갔습니다." answer.append(c) return answer

2024년 4월 29일 알고리즘 문제풀이 문제 메뉴 리뉴얼 난이도 Lv. 2 코드 1차시도 85/100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 def solution(orders, course): answer = [] arr_set = set() for i in range(len(orders)): for j in range(len(orders[i])): arr_set.add(orders[i][j]) orders[i] = set(orders[i]) for n in course: arr = [] cnt = 2 nCr = itertools.combinations(arr_set,n) for x in list(nCr): tmp = 0 for p in orders: if set(x) <= p: tmp += 1 k = sorted(x) word = ''.join(k) if tmp > cnt: cnt = tmp arr = [word] elif tmp == cnt: arr.append(word) answer += arr answer.sort() return answer 반복문을 남발하여서 그런지, 4개 정도의 테스트케이스가 시간초과로 통과하지 못했다. ...

2024년 4월 12일 알고리즘 문제풀이 문제 실패율 난이도 Lv. 1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def solution(N, stages): answer = [] arr = [0 for _ in range(N+2)] arr_f = [0 for _ in range(N+2)] for i in range(len(stages)): now = stages[i] for j in range(1,now+1): arr[j] += 1 arr_f[now] += 1 tmp = [] for i in range(1,N+1): if arr[i] == 0: tmp.append([0,i]) else: tmp.append([(arr_f[i]/arr[i]),i]) tmp.sort(reverse=True, key=lambda x : (x[0],-x[1])) for i in range(N): answer.append(tmp[i][1]) return answer

2024년 4월 1일 알고리즘 문제풀이 문제 n진수 게임 난이도 Lv.2 코드 1차 실패 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def find_limit(a,b): # a를 b진법으로 바꿀 때 자릿수를 반환 idx = 0 while b**idx < a: idx += 1 return idx def change(k,m): # k를 m진법으로 변환하는 함수 max_val = find_limit(k,m) arr = [0 for _ in range(max_val)] for i in range(max_val): arr[i] = k//(m**(max_val-(i+1))) k -= arr[i]*(m**(max_val-(i+1))) return str(''.join(arr)) def solution(n, t, m, p): answer = '' arr = [] numbers = [str(i) for i in range(10)] + ['A', 'B', 'C', 'D', 'E', 'F'] n_numbers = numbers[:n] for i in range(m*t): num = change(i,n) print(num) return answer m명이 t개를 불러야 하므로 m*t까지 숫자를 구한다음, 모두 n진법으로 바꾸려 했다. 문자열로 조각내 배열에 담은다음 찾으면 될 듯 했다. 진법 변환을 못하겠다.. ...

2024년 3월 28일 알고리즘 문제풀이 문제 다트 게임 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 def solution(dartResult): idx = 0 scores = [] # while문 1회 마다 1차례의 결과를 체크 while idx < len(dartResult): # 점수 부분을 담을 변수 tmp = 0 # 문자열이 숫자 부분이라면 점수를 의미 if dartResult[idx].isdigit(): # 그 다음 문자도 숫자라면 10이라는 의미이므로 2글자 모두 담는다. if dartResult[idx+1].isdigit(): tmp = int(dartResult[idx]+dartResult[idx+1]) # 다다음 글자를 보기위해 index 증가 idx += 2 # 아니면 1자리 숫자이므로 1글자만 담는다. else: tmp = int(dartResult[idx]) # 다음 글자를 보기위해 index 증가 idx += 1 # 알파벳이 나오면 보너스를 의미 if dartResult[idx].isalpha(): if dartResult[idx] == 'D': tmp = tmp**2 elif dartResult[idx] == 'T': tmp = tmp**3 # 다음 글자를 살피기 위해 idx 증가 idx += 1 scores.append(tmp) # 옵션은 없을수도 있음 # 마지막 차례에 옵션이 없어서 더이상 글자가 없을 경우를 고려하여 예외처리가 필요 if idx >= len(dartResult): break # 옵션이 있다면 if dartResult[idx] in ['*','#']: # 스타상의 경우 가장 최근 점수의 2배 증가 if dartResult[idx] == '*': scores[-1] = 2*scores[-1] # 첫번째 다트 기회에 스타상이 나올 경우에는 그 이전 점수는 증가시키지 않음 # 따라서 그 이전 점수가 존재할때만 그것도 2배 증가 if len(scores) > 1: scores[-2] = 2*scores[-2] # 아차상은 그 전점수의 부호를 변경 else: if scores: scores[-1] = -1*scores[-1] idx += 1 return sum(scores)

2024년 3월 26일 알고리즘 문제풀이 문제 압축 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 def solution(msg): answer = [] alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' arr = dict() for i in range(len(alphabet)): arr[alphabet[i]] = i+1 # 다음 추가될 색인 번호는 마지막보다 1 큰 수 last_num = len(alphabet)+1 # idx까지 볼때 idx-1 까지만 포함되므로 1로 설정 idx = 1 n = len(msg) while idx <= n: # 이미 있다면 다음이 더 긴지 확인하기 위해 idx만 1 증가 if msg[:idx] in arr: idx += 1 continue else: # 사전에 없다면, 길이가 1 작을 때가 가장 긴 단어이므로(2단계) 그 번호를 출력 answer.append(arr[msg[:idx-1]]) # 없는 단어와 색인 번호를 추가 arr[msg[:idx]] = last_num # 다음 추가될 색인 번호 1 증가 last_num += 1 # 찾아낸 가장 긴 단어는 삭제 msg = msg[idx-1:] # 인덱스 오류를 방지하기 위해 매 반복마다 길이 체크 n = len(msg) # 인덱스 초기화 idx = 1 # 마지막 반복 때 사전에 있는 단어로 끝났다면 추가되지 않는 단어가 생기므로 추가 # KAKAO에서 마지막 O는 별도로 추가해야함 if msg: answer.append(arr[msg]) return answer 매 번 느끼는 거지만, 문제가 길 때(특히 카카오)는 차근차근 시키는대로 하는게 정답이다. ...

2024년 3월 18일 알고리즘 문제풀이 문제 캐시 난이도 Lv.2 코드 1차 80점 / 100점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def solution(cacheSize, cities): answer = 0 if not cacheSize: answer = 5 * len(cities) return answer arr = [] for i in cities: city = i.lower() if len(arr) < cacheSize: answer += 5 arr.append(city) continue if city in arr: answer += 1 arr.remove(city) arr.append(city) continue else: answer += 5 arr.pop(0) arr.append(city) return answer 캐시에 여유공간이 있을 때는 우선적으로 채워주었다. 캐시가 가득 찼을 때, 가장 사용된지 오래된 캐시가 삭제되야 하므로 이에 대한 구별이 필요했다. 따라서 사용한 캐시는 배열에서 삭제후 다시 추가하였다. 이렇게 되면 캐시 배열의 0번 index의 값이 1순위로 삭제될 캐시가 된다. 테스트 케이스가 몇개 있어 실패하였는데, 생각해보니 캐시가 가득 차지 않았을 때도 이미 캐시에 존재하여 추가할 필요가 없는 경우가 있었다. 예를 들어, 첫 번째 두 번쨰 도시가 같다면 내 로직에선 둘 다 캐시에 들어 가버린다. 이 경우를 위해 조건을 추가했다. ...

2024년 3월 5일 알고리즘 문제풀이 문제 방금그곡 난이도 Lv.2 코드 언제나 카카오 문제는 일단 문제 이해가 힘들다. 1차 62.9/100 점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 def solution(m, musicinfos): # 정답 음악 제목 answer = '' # 정답 음악이 라디오에서 재생된 시간 answer_t = 0 for x in musicinfos: # 시작 시간, 종료 시간, 음악 제목, 악보 start,end,title,content = x.split(",") # 시작 시와 분 start_h, start_m = start.split(":") # 종료 시와 분 end_h, end_m = end.split(":") # 재생된 시간 계산 playtime = 60*(int(end_h)-int(start_h)) + (int(end_m) - int(start_m)) # 악보를 list화 tmp = list(content) # 재생된 시간이 악보보다 길다면, 악보를 반복한다. while len(tmp) < playtime: tmp += list(content) # 가장 처음부터 len(m)글자씩 보기 위한 반복 for i in range(len(tmp)-len(m)): # i번째글자부터 i+m번째 글자까지 합쳐, 길이가 m과 같은 글자를 만든다 k = "".join(tmp[i:i+len(m)]) if k == m: # 만든 글자가 m과 같지만, 맨마지막에 #이 온다면 정답이 아니다. # "ABC" 를 찾았지만 악보상 "ABC#"으로 되어있다면 찾은 것으로 되겠지만 실제론 찾은게 아니기 때문 # 첫번째 조건문은 그 다음이 #인지 확인할 때, 그 다음이 없을 경우를 위한 설정 if i+len(m)+1 < len(tmp) and tmp[i+len(m)] != "#": # 처음으로 찾은 음악이라면 정답으로 설정 if not answer_t: answer = title answer_t = playtime # 이미 찾은 음악이 있다면, 재생된 시간이 더 길 때만 업데이트한다. # 짧다면 업데이트할 필요가 없다. # 같다면 이미 찾은 음악이 더 먼저 재생되었기 때문에 업데이트할 필요가 없다. else: if answer_t < playtime: answer = title return answer 진짜 너무 복잡하다.. 풀면서도 이게 정답일 것 같지는 않다고 느꼈는데 역시나였다. 조건을 단순화해야한다. #이 붙었을 때를 제대로 처리하지 않은게 문제인듯 하다. ...