공부기록

🍀문제 설명 🍀내 풀이 참고: https://esoongan.tistory.com/103 # 문자열 형태로 바꾼 숫자들을 세번 반복해서 대소 비교 def solution(numbers): if sum(numbers) == 0: return '0' numbers = [str(num) for num in numbers] numbers.sort(key = lambda x: x*3, reverse=True) return ''.join(numbers) 문자열로 바꿔서 자리마다 대소비교까지는 생각했는데 숫자로 변환한 문자열로 바꾸고 세번 반복해서 비교하는건 생각도 못했다..! 세상에는 똑똑한 사람들이 많구나 ,,,,,,,,, 나올 수 있는 숫자가 최대 1000까지니까 최대 세자리까지 비교하기 위해서 세번 반복해준다..

🍀문제 설명 🍀내 풀이 (오답) def solution(topping): answer = 0 for i in range(1, len(topping)): left = set(topping[:i]) right = set(topping[i:]) if len(left) == len(right): answer += 1 return answer 단순히 리스트 내에서 나눌 수 있는 모든 구간을 나눠보고, 그 때 왼쪽과 오른쪽 리스트를 set으로 바꿔 개수가 같은지 확인했다. 예시문제 2개는 맞췄지만 테스트케이스는 2개 제외하고 모두 시간초과로 실패했다. 🍀모범 답안 참고: https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%EB%A..

🍀문제 설명 🍀내 풀이 최대공약수 관련 참고: https://school.programmers.co.kr/questions/40997 from math import gcd # 리스트의 최대공약수 찾는 함수 def getGCD(arr): g = arr[0] for i in range(1, len(arr)): g = gcd(g, arr[i]) return g def check(arr1, arr2): # arr1의 최대공약수가 arr2를 다 나눌 수 없는지 확인 g = getGCD(arr1) if 0 not in [i%g for i in arr2] and g != 1: return g else: return 0 def solution(arrayA, arrayB): answer = 0 g1 = check(arr..

🍀문제 설명 🍀내 풀이 참고: https://hbj0209.tistory.com/104 def solution(routes): answer = 0 routes.sort(key = lambda x: x[1]) # 진출 지점 기준으로 정렬 now = routes[0][1] # 가장 첫번째 차량의 진출 지점에 카메라 하나 설치 answer += 1 for i in range(1, len(routes)): # 다음 차량이 카메라 설치 지점 이후에 들어오면 해당 차량의 진출 지점에 새로운 카메라 설치 if now < routes[i][0]: answer += 1 now = routes[i][1] return answer greedy를 이용해서, 차량의 진출 지점에 처음 카메라를 설치한 뒤 그 다음 차량들이 카메라..

🍀문제 설명 🍀내 풀이 def solution(n, times): answer = 0 start = min(times) end = max(times)*n # 걸릴 수 있는 최대 시간: 모든 사람이 제일 오래 걸리는 심사대에서 받을 때 while start = n: answer = mid end = mid -1 elif pos < n: start = mid + 1 return answer 이진 탐색으로 풀 수 있다는 걸 알고 풀려고 해도 쉽게 구현이 어려워서 예전에 내가 풀었던 코드를 참고해서 다시 풀었다. 최대값을 가장 시간이 오래 걸리는 심사대에서만 받았을 때의 시간으로 설정해서, 탐색을 통해 최적의 값을 찾아 나가는 식이다. 걸리는 시간을 mid라고 했을 때 각 심사대에서 mid분동안 받을 수 있는 ..

🍀문제 설명 🍀내 풀이 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) # 가장 작은 값이 K보다 커질때까지 / 더 합칠 수 없을 때까지(scoville에 남은 원소가 1개) while문을 실행 while scoville[0] 1: a = heapq.heappop(scoville) b = heapq.heappop(scoville) heapq.heappush(scoville, a+b*2) answer += 1 return answer if scoville[0] >= K else -1 # scoville에 남은 1개의 원소가 K보다 작으면 실패 --> -1 출력 힙 자료구조를 사용..

🍀문제 설명 🍀내 풀이 def solution(s): stack = [] for i in s: if i == '(': # ( 일 경우 stack.append(i) else: if len(stack) == 0: # stack이 비어있는데 )가 나온 경우 -> 올바르지 않음 return False else: # stack에 (가 있고 다음으로 )가 온 상태 -> 괄호 한 쌍 찾음 -> stack에서 ( 꺼내기 stack.pop() return len(stack) == 0 stack 구조를 사용해서 문제를 풀었다. 각 괄호를 확인하면서 ( 일 경우 stack에 넣고, ) 일 경우에는 stack을 확인했을 때 stack이 비어있으면 괄호가 완성될 수 없으므로 False를 return하고, stack 안에 하나 ..

🍀문제 설명 🍀모범 답안 참고: https://velog.io/@henrynoowah/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-PYTHON def solution(n, costs): answer = 0 # 비용을 기준으로 오름차순 정렬 costs.sort(key = lambda x: x[2]) # 연결된 섬 - 최소비용인 간선의 출발지에서부터 시작 node = set([costs[0][0]]) # 크루스칼 알고리즘 while len(node) != n: for cost in costs: # 출발, 도착 모두 node에 있는 경우 -> 이미 낮은 비용으로 연결 완 -..

🍀문제 설명 🍀내 풀이(오답) from collections import defaultdict def dfs(now, answer, graph): if now in graph.keys() and len(graph[now]) != 0: arr = graph[now].pop(0) answer.append(arr) dfs(arr, answer, graph) def solution(tickets): answer = [] # 출발지, 도착지 기록: 도착지가 겹치는 티켓이 있으므로 원소를 list로 갖는 defaultdict 생성 graph = defaultdict(list) for ticket in tickets: graph[ticket[0]].append(ticket[1]) # 도착지 list 정렬 for k ..

🍀문제 설명 🍀내 풀이 from collections import deque def bfs(begin, target, words): visited = [False]*len(words) # 각 단어 방문 여부 wnum = len(begin) # 단어 길이 q = deque() q.append([begin, 0]) # [현재 단어, 바뀐 횟수] while q: now, num = q.popleft() # target을 찾은 경우, 현재까지 바뀐 횟수를 return if now == target: return num for i in range(len(words)): if not visited[i] and sum([True if now[j]!=words[i][j] else False for j in range(..