Algorithm

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월 23일 알고리즘 문제풀이 문제 Container With Most Water 난이도 medium 코드 1차시도 시간초과(50/62) 모두 탐색했는데 시간초과가 떴다. 1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def check(self,a,b,height): val = min(height[a], height[b]) return abs(b-a)*val def maxArea(self, height: List[int]) -> int: n = len(height) ans = 0 for a in range(n-1): for b in range(a+1,n): ans = max(ans, self.check(a,b,height)) return ans 2차시도 메모리초과(49/62) 인덱스 중 2개를 골라 처리하려 했는데 2개의 숫자 조합을 만들기 위한 배열이 메모리초과가 떴다. 아무래도 접근 방법 자체가 틀린것같다. ...

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년 5월 20일 알고리즘 문제풀이 문제 카펫 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(brown, yellow): answer = [] arr = [] # 가로길이와 세로길이에서 모두 2를 빼고 곱한 값이 노란색 카펫의 개수와 같아야 한다. for i in range(1, int((yellow)**0.5)+1): if not yellow % i: arr.append([i, yellow//i]) # 따라서 위에서 구한 값에 2를 더하면 카펫의 가로 길이와 세로 길이가 된다. # 모든 칸의 갯수를 구한 후 노란색 카펫의 갯수를 빼면 갈색 카펫의 갯수가 나온다. # 가로가 길어야 하므로 y, x 순으로 정렬한다. for x, y in arr: x += 2 y += 2 if x*y - yellow == brown: answer = [y, x] return answer

2024년 5월 17일 알고리즘 문제풀이 문제 모의고사 난이도 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 53 54 55 56 57 58 59 60 61 62 63 64 # 수포자 1이 찍은 답을 문제 번호로 찾기 def first_answer(idx): if (idx+1) % 5: return (idx+1) % 5 else: return 5 # 수포자 2가 찍은 답을 문제 번호로 찾기 def second_answer(idx): if not idx % 2: return 2 else: if idx % 8 == 1: return 1 elif idx % 8 == 3: return 3 elif idx % 8 == 5: return 4 else: return 5 # 수포자 3이 찍은 답을 문제 번호로 찾기 def third_answer(idx): idx %= 10 if idx < 2: return 3 elif idx < 4: return 1 elif idx < 6: return 2 elif idx < 8: return 4 else: return 5 def solution(answers): ans = [] # 맞춘 갯수를 담는 배열 arr = [0, 0, 0] # 채점 for idx in range(len(answers)): if answers[idx] == first_answer(idx): arr[0] += 1 if answers[idx] == second_answer(idx): arr[1] += 1 if answers[idx] == third_answer(idx): arr[2] += 1 # 가장 많이 맞춘 사람 찾기 max_val = max(arr) # 고득점자가 한 명일 경우 if len(set(arr)) == 3: ans.append(arr.index(max_val)+1) # 고득점자가 둘 이상일 경우 else: for i in range(3): if arr[i] == max_val: ans.append(i+1) return ans

2024년 5월 16일 알고리즘 문제풀이 문제 Longest Common Prefix 난이도 Easy 코드 1 2 3 4 5 6 7 8 9 10 class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: word = strs[0] for i in range(1,len(strs)): for j in range(1,len(word)+1): if word[:j] != strs[i][:j]: word = word[:j-1] break return word Set로 풀어보려했는데, 맨 앞에서부터 공통을 찾아야 했다. 더 좋은 방법은 안 떠오르는데.. ...

2024년 5월 14일 알고리즘 문제풀이 문제 조이스틱 난이도 Lv.2 코드 1차 55.6점 / 100점 진짜 어려웠다. A글자를 원하는 글자로 바꾸는 것은 어렵지 않았으나, 어떤 방향으로 커서를 움직이도록 설정할지가 고민됐다. 양 옆의 글자를 보고 바꾸기 위해 조작을 많이해야 하는 쪽으로 움직이도록 설정해주었다. 그래야 혹시 바꿀 필요가 없는 쪽으로 이동하지 않을 거라고 생각했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def solution(name): def cal(x): max_val = ord("Z")+1 return min(ord(name[x])-ord(tmp[x]),(max_val-ord(name[x]))) n = len(name) name = list(name) answer = 0 idx = 0 tmp = list('A'*n) while True: if name[idx] != tmp[idx]: answer += cal(idx) tmp[idx] = name[idx] if name == tmp: break if cal((idx-1)%n) >= cal((idx+1)%n): idx = (idx-1)%n else: idx = (idx+1)%n answer += 1 return answer 2차 51.9점 / 100점 ...

2024년 5월 13일 알고리즘 문제풀이 문제 H-Index 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(citations): answer = 0 left = 0 right = 10000 while left <= right: cnt = 0 mid = (left+right)//2 for i in citations: if i >= mid: cnt += 1 if cnt < mid: right = mid -1 else: left = mid +1 answer = (left+right)//2 return answer 가능한 값 중 최솟값 혹은 최댓값을 찾는 문제는 이제 자연스레 이진탐색이 떠오른다. ...

2024년 5월 10일 알고리즘 문제풀이 문제 덧칠하기 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 from heapq import heappop, heappush def solution(n, m, section): answer = 0 arr = [] for x in section: heappush(arr,x) idx = heappop(arr) end = idx + m -1 cnt = 1 while arr: if arr[0] <= end: heappop(arr) continue else: idx = heappop(arr) end = idx + m -1 cnt += 1 return cnt 최소힙을 사용하는 아이디어가 금방 떠올라서 쉽게 풀었다. ...

2024년 5월 9일 알고리즘 문제풀이 문제 two-sum 난이도 Easy 코드 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 class Solution: def twoSum(self, nums, target: int): board = dict() idx_arr = dict() answer = [] for i in range(len(nums)): if nums[i] not in board: board[nums[i]] = 1 else: board[nums[i]] += 1 for i in range(len(nums)): if nums[i] not in idx_arr: idx_arr[nums[i]] = [i] else: idx_arr[nums[i]].append(i) for i in range(-target,target+1,1): if i in board and target-i in board: if i != target-i: answer = [idx_arr[i][0],idx_arr[target-i][0]] break else: if board[i] >= 2: answer = [idx_arr[i][0], idx_arr[i][1]] break return answer 다 조회하면 시간이 초과될 것 같아, dictionary를 이용하려 했다. target이 0일 떈 조합을 찾는 반복문이 제대로 작동하지 않아 오답처리되었다. ...