2024년 4월 8일 알고리즘 문제풀이 문제 전화번호 목록 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def solution(phone_book): answer = True arr =dict() for phone_number in phone_book: arr[phone_number] = True for phone_number in phone_book: temp="" for num in phone_number: temp +=num if temp in arr and temp!=phone_number: answer = False return answer
2024년 4월 6일 알고리즘 문제풀이 문제 옹알이 (2) 난이도 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 def search_index(arr,k): result = -1 if k in arr: result = arr.index(k) return result def solution(babbling): answer = 0 arr = ["aya", "ye", "woo", "ma"] for word in babbling: idx = 0 n = len(word) last_find_idx = -1 while idx <= n: if not n: answer += 1 break tmp = word[:idx+1] search_result = search_index(arr,tmp) if search_result != -1 and search_result != last_find_idx: last_find_idx = search_index(arr,tmp) word = word[idx+1:] n = len(word) idx = 0 else: idx += 1 return answer
2024년 4월 5일 알고리즘 문제풀이 문제 없는 숫자 더하기 난이도 Lv. 1 코드 1 2 3 4 5 def solution(numbers): answer = -1 arr = set(numbers) answer = 45 - sum(arr) return answer
2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 실버 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys k,n = map(int,sys.stdin.readline().split()) lan = [] for _ in range(k): lan.append(int(sys.stdin.readline())) low = 0 high = 2**31-1 while low <= high: mid = (low+high)//2 cnt = 0 for thing in lan: cnt += thing//mid if cnt >= n: low = mid+1 else: high = mid-1 print((high+low)//2) 생각보다 평범한 이진탐색문제였다. ...
2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 골드 4 코드 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 import sys from heapq import heappop, heappush def check(k:int): if not k%2: return False for i in range(3,int(k**(0.5))+1): if not k%i: return False else: return True prime_numbs = [ False for _ in range(10000)] for i in range(1000,10000): if check(i): prime_numbs[i] = True def change_num(arr: list): result = [] for i in range(10): for j in range(4): tmp = arr.copy() tmp[j] = str(i) if int("".join(tmp)) > 999 and prime_numbs[int("".join(tmp))] and tmp != arr: result.append(tmp) return result t = int(sys.stdin.readline()) for _ in range(t): answer = 'Impossible' a,b = map(int,sys.stdin.readline().split()) visited = [False for _ in range(10000)] visited[a] = True q = [] a_arr = list(str(a)) b_arr = list(str(b)) heappush(q,[0,a_arr]) while q: cnt, now = heappop(q) if now == b_arr: answer = cnt break change_arr = change_num(now) for num in change_arr: if not visited[int("".join(num))]: visited[int("".join(num))] = True heappush(q,[cnt+1, num]) print(answer) 매 번 소수 여부를 체크하지 않고, 1000부터 9999까지 소수 여부를 표시한 배열을 만들었다. change_num() 함수는 특정 수에서 1자리만 바꾼 수이다. 배열에 넣을 때, 몇 번 바뀌었는지를 함께 넣고 최소힙을 이용하여 최대한 적게 바꿀때를 찾을 수 있도록 했다. ...
2024년 4월 2일 알고리즘 문제풀이 문제 가장 큰 수 난이도 Lv.2 코드 1차 실패 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def check_first(s): if len(str(s)) == 1: return int(s) else: return int(str(s)[0]) def solution(numbers): n = len(numbers) answer = '' arr = [] for _ in range(10): arr.append([]) for num in numbers: tmp = check_first(num) arr[num].append(num) return answer 두 수 중 먼저 와야할 수는 가장 앞에 있는 수가 큰 수면 되겠다 싶었다. 그래서 모든 수를 맨 앞이 1인 수, 2인 수, … , 9인 수 까지 분류하려했다. 생각해보니 그 다음은? 그 안을 또 나누기엔 컴퓨터가 터지지 않을까? 수 두 개를 비교할 때, 길이는 중요하지 않다는 걸 파악했다. 그리고 가장 앞에 있는 수가 중요하다는 것도 캐치했다. 두번 째로 오는 수는 앞자리 수와의 비교가 중요하다. 예를 들어, 30,31,32 는 두 번째 자리가 0,1,2 로 모두 3보다 작으므로 그냥 ‘3’보다 늦게 올 애들이다. 반면 34,35 등은 3보다 더 앞에 나타나야 한다. 비교를 쉽게 하기 위해 앞자리를 복붙하면 되겠다고 생각했는데, 1000 이하이니 싹 다 3자리 짜리로 만들어주면 되겠다. ...
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월 28일 알고리즘 문제풀이 문제 서울에서 김서방 찾기 난이도 Lv.1 코드 1 2 3 4 def solution(seoul): answer = '' answer = str(seoul.index('Kim')) return f"김서방은 {answer}에 있다"
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 매 번 느끼는 거지만, 문제가 길 때(특히 카카오)는 차근차근 시키는대로 하는게 정답이다. ...