Study

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월 15일 알고리즘 문제풀이 문제 체육복 난이도 Lv.1 코드 1차 93.3점 / 100점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(n, lost, reserve): lost.sort() reserve.sort() arr = set() for loser in lost: if loser in reserve: reserve.remove(loser) continue if loser - 1 in reserve: reserve.remove(loser - 1) elif loser + 1 in reserve: reserve.remove(loser + 1) else: arr.add(loser) return n - len(arr) 2개의 테스트 케이스에서 오답처리 되었다. 생각해보니 이렇게 작성할 경우 여벌이 있었으나 도둑맞은 사람의 것을 다른사람에게 빌려주게 될 수도 있다는 생각이 들었다. 따라서 우선, 여벌이 있었으나 도둑 맞아 더이상 빌려줄 여력이 없으며 다른 사람의 것도 필요 없는 사람을 제외하도록 수정했다. ...

2024년 3월 14일 알고리즘 문제풀이 문제 음양 더하기 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 def solution(absolutes, signs): answer = 0 for i in range(len(signs)): if signs[i]: answer += absolutes[i] else: answer -= absolutes[i] return answer

2024년 3월 12일 알고리즘 문제풀이 문제 파일명 정렬 난이도 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 def seperate(name): # head와 number를 분리하는 함수 idx = 0 head = "" number = "" # 처음 숫자가 나오기 전까지가 head while True: if name[idx] in "0123456789": head = name[:idx] break idx += 1 # idx는 number의 첫글자로 유지된 상태에서 시작 # 숫자가 나오면 계속 number로 추가 # 5자리가 넘어가거나, tail이 존재하지 않으면 종료 while len(number) < 5 and idx < len(name): if name[idx] in "0123456789": number += name[idx] idx += 1 else: break # head는 소문자로 변환 return head.lower(), number def solution(files): # 정답을 담을 배열 answer = [] # 각기 다른 head만 담을 배열 # 첫번째 정렬을 위해 사용 head_order = [] # 동일한 head를 가진 number들을 담을 배열 # 두번째 정렬을 위해 사용 # key는 head로, value는 list로 만들 것. # 원소는 [number, index] 형태로 만들어 number로 정렬한다. # index는 files 내에서 index를 뜻하며 원래 파일 이름을 찾을 수 있도록 한다. arr = dict() for i in range(len(files)): file = files[i] # 파일명에서 head, number 추출 head, number = seperate(file) # 이번 파일의 head가 이전에 나온 적 있는 head라면? if arr.get(head): # dict에서 head가 key인 value를 찾아 추가 arr[head].append([int(number), i]) else: # 처음 나온 head라면 dict에 추가 arr[head] = [[int(number), i]] # 새로운 head 이므로 head 배열에도 추가 head_order.append(head) # head 배열을 사전순으로 정렬 head_order.sort() # 가장 먼저 나와야할 head 선택 for head in head_order: # 선택된 것을 head로 가지는 number 들을 정렬 arr[head].sort() for num, idx in arr[head]: # 순서대로 원래 파일 이름을 정답 배열에 추가 answer.append(files[idx]) return answer

2024년 3월 11일 알고리즘 문제풀이 문제 예상 대진표 난이도 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 def solution(n,a,b): answer = 0 # 다음 라운드로 진출하여 새로운 번호를 부여하는 함수 def victory(num): if num%2: tmp = num//2 + 1 else: tmp = num//2 return tmp # 만났는지 확인하는 함수 def check(p,q): if abs(p-q) == 1 and p//2 != q//2: return True else: return False cnt = 1 while True: if check(a,b): return cnt a = victory(a) b = victory(b) cnt += 1 return cnt 두 사람의 번호가 1 차이가 나지만 2로 나누었을 때 몫이 달라야 한다. 한 사람의 번호가 3일 때, 1 차이가 나는 수는 2와 4지만, 실제로 만나는건 몫이 다른 4이기 때문이다

2024년 3월 8일 알고리즘 문제풀이 문제 완주하지 못한 선수 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(participant, completion): arr = {} for runner in completion: if runner not in arr: arr[runner] = 1 else: arr[runner] += 1 for player in participant: if arr.get(player): arr[player] -= 1 else: return player n-1개의 참가자 목록을 길이가 n인 리스트에서 탐색할 때 최악의 경우 n*(n-1), O(n**2)의 수행시간이 걸린다. 길이가 n인 리스트에서 1개를 탐색할 때 최악의 경우 n만큼 반복해야 하기 때문. 하지만 dictionary에선 상수의 값이라 O(1)이 n번 소요된다. dictionary에서 in 연산자는 해당 key가 존재하는지 찾아주고 get은 value 값을 반환해준다.

2024년 3월 7일 알고리즘 문제풀이 문제 두 정수 사이의 합 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(a, b): high = max(a,b) low = min(a,b) answer = 0 for i in range(low,high+1): answer += i return answer

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 진짜 너무 복잡하다.. 풀면서도 이게 정답일 것 같지는 않다고 느꼈는데 역시나였다. 조건을 단순화해야한다. #이 붙었을 때를 제대로 처리하지 않은게 문제인듯 하다. ...

2024년 3월 4일 알고리즘 문제풀이 문제 점프와 순간 이동 난이도 Lv.2 코드 일반적인 DP문제라고 생각했다. 조금 어려운 편이긴 하지만, 기존에 충분히 풀어봤던 유형이라 금방 풀 수 있었다. 도착지로 이동하는 마지막 방법을 점프라고 고정하고 생각했다. 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 def solution(n): # 3칸까지는 고려할 필요 없음 if n <= 3: dp = [0, 1, 1, 2] return dp[n] # 그 이상일 때는 DP # 가장 최대 건전지 사용량은 그곳까지 점프로만 도달했을 때이므로 모든 곳을 최댓값으로 초기화한다. dp = [] for i in range(n + 1): dp.append(i) # 2,3일 때는 알맞게 초기화 dp[2] = 1 dp[3] = 2 # 4 이상일 때부터 DP for i in range(4, n + 1): # 반으로 나누었을 때 몫 k = i // 2 # 홀수여서 딱 절반인 곳이 존재하지 않을 때 if i % 2: # i까지 도달 비용 = 몫까지 도달하는 비용(dp[j]) + 몫부터 i까지 점프하는 비용(i-j) for j in range(k, i): dp[i] = min(dp[i], dp[j] + i - j) # 짝수여서 절반인 곳이 존재할 때 else: # 절반인 곳에서 순간이동하면 도착할 수 있으므로 절반에 도착하는 것과 같은 값 dp[i] = min(dp[i], dp[k]) for j in range(k + 1, i): dp[i] = min(dp[i], dp[j] + i - j) return dp[n] n칸 까지 갈 때, 절반인 n//2를 기준으로 생각하면 된다. 절반도 오지 못했을 떄 점프를 하는 것은 거기서 순간이동 하는 것보다 더 건전지 사용량이 소모될 것이기 때문이다. 예를 들어, 10 칸을 이동한다고 했을 때 ...

2024년 3월 1일 알고리즘 문제풀이 문제 둘만의 암호 난이도 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 def solution(s, skip, index): answer = [] alphabet = list('abcdefghijklmnopqrstuvwxyz') n = len(alphabet) def check(num,x): idx = alphabet.index(x) while num: idx += 1 # 알파벳의 끝에 도달하면 맨 처음으로 보냄 if idx == n: idx = 0 result = alphabet[idx] # skip에 포함되지 않을때만 갯수를 셈 if result not in skip: num -= 1 return result arr = list(s) for i in arr: answer.append(check(index,i)) return ''.join(answer)