Coding Test
-
[프로그래머스 42626번] 더 맵게Coding Test/프로그래머스 2021. 4. 22. 21:05
# 문제 내 풀이 import heapq def solution(scoville, K): answer = 0 # 최소 힙 생성하기 h = [] for i in scoville: heapq.heappush(h, i) while True: low1 = heapq.heappop(h) # 첫 번째 원소가 K보다 크거나 같다면, 루프를 탈출하고 최소 횟수 리턴 if low1 >= K: break # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우, -1 리턴 if not h: return -1 low2 = heapq.heappop(h) # 가장 덜 매운 두 요소의 스코빌 지수가 0이라면, -1 리턴 if low1 == 0 and low2 == 0: return -1 mixed_s = low1 + 2 *..
-
[프로그래머스 43165] 타겟 넘버Coding Test/프로그래머스 2021. 4. 15. 13:54
# 문제 내 풀이 from collections import deque def solution(numbers, target): answer = 0 # 큐 생성 및 초기화 queue = deque([numbers[0], -numbers[0]]) idx = 1 # BFS 수행 # numbers의 마지막 숫자를 더하고 뺄 때까지 while idx < len(numbers): for _ in range(len(queue)): num = queue.popleft() # 해당 순서의 숫자를 더한 값과 뺀 값을 큐에 삽입 queue.append(num + numbers[idx]) queue.append(num - numbers[idx]) idx += 1 # 큐가 빌 때까지 while queue: if queue.po..
-
[프로그래머스 43162번] 네트워크Coding Test/프로그래머스 2021. 4. 15. 13:50
# 문제 내 풀이 # DFS 정의 def dfs(computers, v, visited, n): # 현재 노드를 방문 visited[v] = True # 현재 노드의 인접 노드를 재귀적으로 방문 for i in range(n): if computers[v][i] and not visited[i]: dfs(computers, i, visited, n) def solution(n, computers): answer = 0 visited = [False] * n # 각 노드의 방문 정보를 표현 # 첫번째 노드부터 순서대로 확인 for v in range(n): # 아직 방문하지 않은 노드라면 if not visited[v]: # dfs를 수행하고 네트워크 수를 하나 셈 dfs(computers, v, visi..
-
[프로그래머스 43163번] 단어 변환Coding Test/프로그래머스 2021. 4. 15. 13:45
# 문제 내 풀이 from collections import deque # 두 단어가 한 글자가 다른 관계인지 체크하는 함수 정의 def one_diff(word, cmp_word): cnt = 0 for i in range(len(word)): if word[i] != cmp_word[i]: cnt += 1 if cnt > 1: break if cnt == 1: return True return False def solution(begin, target, words): answer = 0 n = len(words) visited = [[False] * n for _ in range(n)] # 2차원 방문 정보 테이블 # 큐 생성 및 초기화 # begin과 철자가 하나만 다른 단어를 찾아, 방문 처리하고..
-
[백준 2581 math] 소수Coding Test/백준 2021. 3. 22. 06:13
# 문제 내 풀이 m = int(input()) n = int(input()) # 처음엔 모두가 소수인 것으로 초기화 (0과 1 제외) array = [True for _ in range(n + 1)] array[0], array[1] = False, False # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(n ** 0.5) + 1): if array[i]: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j
-
[백준 1644번] 소수의 연속합Coding Test/백준 2021. 3. 22. 06:08
# 문제 내 풀이 # 2부터 4000000까지의 모든 수에 대하여 소수 판별 (n의 최대 입력) limit_num = 4000000 # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for _ in range(limit_num + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 limit_num의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(limit_num ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j
-
[백준 1436번] 영화감독 숌Coding Test/백준 2021. 3. 19. 19:02
# 문제 내 풀이 n = int(input()) title = 666 # 영화 제목에 들어간 수 series = 1 # 해당 영화의 시리즈 순서 # n번째 영화를 찾을 때까지 완전 탐색 while series < n: # 숫자를 하나씩 늘려가며 title += 1 # 숫자에 '666'이 들어가면 영화 시리즈 개수로 셈 if '666' in str(title): series += 1 # n번째 영화의 제목에 포함된 수 출력 print(title) 시간 복잡도 O(N)