728x90
반응형
* 계속 업데이트 중
해시
폰켓몬
from collections import Counter
def solution(nums):
count_nums = Counter(nums)
return len(nums) // 2 if len(count_nums) >= len(nums) // 2 else len(count_nums)
완주하지 못한 선수
from collections import Counter
def solution(participant, completion):
partici = Counter(participant)
comple = Counter(completion)
partici_keys = partici.keys()
for i in partici_keys:
if partici[i] != comple[i]:
return i
전화번호 목록
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
return False
return True
의상
def solution(clothes):
name = dict(clothes).keys()
type = set(dict(clothes).values())
type2 = list(dict(clothes).values())
num = []
for i in type:
num.append(type2.count(i) + 1)
answer = 1
for i in range(0, len(num)):
answer *= num[i]
return answer - 1
베스트앨범
def solution(genres, plays):
song_dict = {}
play_count_dict = {}
# 고유 번호와 재생 횟수를 딕셔너리로 매핑
for i in range(len(genres)):
genre = genres[i]
play_count = plays[i]
if genre not in song_dict:
song_dict[genre] = []
play_count_dict[genre] = 0
song_dict[genre].append((i, play_count))
play_count_dict[genre] += play_count
# 장르별 재생 횟수를 내림차순으로 정렬
sorted_genres = sorted(play_count_dict.keys(), key=lambda x: play_count_dict[x], reverse=True)
answer = []
for genre in sorted_genres:
# 장르 내에서 재생 횟수가 높은 순으로 정렬하되, 고유 번호가 낮은 순으로 정렬
song_dict[genre].sort(key=lambda x: (x[1], -x[0]), reverse=True)
# 최대 2곡까지 선택
answer.extend([song[0] for song in song_dict[genre][:2]])
return answer
스택/큐
같은 숫자는 싫어
def solution(arr):
stack = []
stack.append(arr[0])
for i in range(1, len(arr)):
if arr[i-1] != arr[i]:
stack.append(arr[i])
return stack
올바른 괄호
def solution(s):
stack = []
for i in s:
if len(stack) == 0:
if i == "(":
stack.append(i)
continue
else:
return False
if len(stack) != 0 and i == ")":
stack.pop()
if len(stack) != 0 and i == "(":
stack.append(i)
return True if len(stack) == 0 else False
기능개발
import math
def solution(progresses, speeds):
max_day = 0
count = 1
answer = []
for i in range(len(progresses)):
day = math.ceil((100 - progresses[i]) / speeds[i])
if day > max_day:
max_day = day
answer.append(count)
count = 1
else:
count += 1
return answer[1:] + [count]
프로세스
from collections import deque
def solution(priorities, location):
order = deque(priorities)
cnt = 0
my_index = [0] * len(priorities)
my_index[location] = 1
while True:
if not my_index or max(my_index) == 0:
break
if order[0] != max(order):
order.append(order[0])
my_index.append(my_index[0])
order.popleft()
del my_index[0]
else:
cnt += 1
order.popleft()
del my_index[0]
return cnt
다리를 지나는 트럭
from collections import deque
def solution(bridge_length, weight, truck_weights):
queue = deque(truck_weights)
answer = 0
bridge = deque([0] * bridge_length)
current_weight = 0
while queue:
answer += 1
current_weight -= bridge.popleft()
if current_weight + queue[0] <= weight:
truck = queue.popleft()
bridge.append(truck)
current_weight += truck
else:
bridge.append(0)
answer += bridge_length
return answer
주식가격(효율성 테스트는 통과 못함)
from collections import deque
def solution(prices):
queue = deque(prices)
answer = [0] * len(prices)
order = 0
while queue:
if len(queue) == 1:
break
cnt = 0
for i in range(1, len(queue)):
if queue[0] <= queue[i]:
cnt += 1
else:
cnt += 1
break
answer[order] = cnt
queue.popleft()
order += 1
return answer
힙
더 맵게
import heapq
def solution(scoville, K):
heapq.heapify(scoville)
count = 0
if scoville[0] >= K:
return count
while scoville[0] < K:
if len(scoville) == 1:
return -1
min_heapq = heapq.heappop(scoville)
min_heapq2 = heapq.heappop(scoville)
heapq.heappush(scoville, min_heapq + (2 * min_heapq2))
count += 1
return count
디스크 컨트롤러
import heapq
def solution(jobs):
answer = 0
start_time = 0
end_time = 0
jobs.sort()
my_len = len(jobs)
heap = []
while jobs or heap:
while jobs and jobs[0][0] <= end_time:
request_time, duration = jobs.pop(0)
heapq.heappush(heap, (duration, request_time))
if heap:
duration, request_time = heapq.heappop(heap)
start_time = end_time
end_time += duration
answer += end_time - request_time
else:
end_time = jobs[0][0]
return answer // my_len
정렬
K번째 수
def solution(array, commands):
answer = []
for i in range(len(commands)):
array1 = array[commands[i][0] - 1 : commands[i][1]]
array1.sort()
answer.append(array1[commands[i][2] - 1])
return answer
가장 큰 수
아래 코드는 기초 테스트는 통과하지만, 심화 테스트는 통과하지 못한다.
이유는 배열의 길이가 최대 10만이고, 순열은 팩토리얼로 계산되기 때문에,
100000!는 1.59 * 10^456571라는 말도 안되는 숫자이기 때문에 당연히 시간 초과가 난다.
(대략 1초에 3~5억의 연산까지만 허용된다고 계산하면 된다)
그러므로 permutations를 써서 해결할 수 없다.
import itertools
def solution(numbers):
comb = itertools.permutations(numbers, len(numbers))
max_num = 0
for i in comb:
result = int(''.join(map(str, i)))
max_num = max(max_num, result)
return str(max_num)
정답
def solution(numbers):
my_list = list(map(str, numbers))
# 문자열을 정렬하면 0부터 9 순으로 정렬된다.
# x를 4번 반복한 후, 1부터 4까지의 숫자를 비교해서 정렬(원소는 1000 이하이므로)
my_list.sort(key=lambda x: (x * 4) [:4], reverse=True)
answer = ''.join(my_list)
# 0이 답일 경우, 0이 하나만 나와야지 테스트 통과됨
# 00, 000, 0000 등은 오답 처리됨
if answer[0] == '0':
return '0'
else:
return answer
H-Index
def solution(citations):
n = len(citations)
citations.sort() # 인용 횟수를 오름차순으로 정렬
h_index = 0
for i in range(n):
if citations[i] >= n - i: # 현재 인용 횟수가 남은 논문 수와 같거나 큰 경우
h_index = n - i # H-Index 갱신
break
return h_index
완전탐색
최소직사각형
def solution(sizes):
width = []
height = []
for i in range(len(sizes)):
width.append(max(sizes[i]))
height.append(min(sizes[i]))
print(width)
print(height)
return max(width) * max(height)
모의고사
*완전탐색형 문제여서 시간 초과를 피하고 가능한 코드.
# 1번: 12345 반복
# 2번: 21232425 반복
# 3번: 3311224455 반복
from collections import deque
def solution(answers):
stu_1 = [1, 2, 3, 4, 5]
stu_2 = [2, 1, 2, 3, 2, 4, 2, 5]
stu_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
answer = []
# 1번 수포자 풀이
index = 0
cnt = 0
for i in range(len(answers)):
if answers[i] == stu_1[index]:
cnt += 1
index = (index + 1) % len(stu_1)
answer.append(cnt)
# 2번 수포자 풀이
index = 0
cnt = 0
for i in range(len(answers)):
if answers[i] == stu_2[index]:
cnt += 1
index = (index + 1) % len(stu_2)
answer.append(cnt)
# 3번 수포자 풀이
index = 0
cnt = 0
for i in range(len(answers)):
if answers[i] == stu_3[index]:
cnt += 1
index = (index + 1) % len(stu_3)
answer.append(cnt)
# 최대 정답자 배열에 담기
real_answer = []
for i in range(len(answer)):
if answer[i] == max(answer):
real_answer.append(i+1)
return real_answer
소수 찾기
* 소수 판별할 때는 "에라토스테네스의 체" 방법을 사용한다.
* 2부터 n의 제곱근을 정수형으로 변환한 값으로 나눠서 떨어지면 소수가 아니다.
(소수가 아닐 경우, 이 범위 안에 약수가 존재하게 된다.)
* 연산을 줄일 수 있다.
import itertools
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def solution(numbers):
answer = 0
num_list = list(numbers)
prime_set = set()
# 가능한 모든 숫자 조합 생성
for i in range(1, len(num_list) + 1):
perm = itertools.permutations(num_list, i)
for p in perm:
num = int(''.join(p))
if is_prime(num):
prime_set.add(num)
answer = len(prime_set)
return answer
카펫
def solution(brown, yellow):
num = brown + yellow
answer = []
for i in reversed(range(1, num+1)):
if num % i == 0:
if ((num // i) * 2) + ((i - 2) * 2) == brown:
answer.append(i)
if i * i == num:
answer.append(i)
return answer
피로도
from itertools import permutations
def solution(k, dungeons):
order = list(permutations(dungeons))
answer = []
hp = k
for i in order:
count = 0
for j in range(len(i)):
if hp >= i[j][0]:
count += 1
hp -= i[j][1]
else:
continue
answer.append(count)
hp = k
return max(answer)
모음사전
def solution(word):
vowels = ['A', 'E', 'I', 'O', 'U'] # 알파벳 모음 리스트
answer = 0
count = 1 # 단어의 순서를 나타내는 변수
for i in range(len(word)):
# 현재 위치의 알파벳이 알파벳 모음 리스트에서 몇 번째인지 계산하여 더해줌
answer += vowels.index(word[i]) * ((5 ** (5 - i)) - 1) / 4
return int(answer + len(word))
탐욕법
체육복
from collections import deque
def solution(n, lost, reserve):
my_lost = set(lost) - set(reserve)
my_reserve = set(reserve) - set(lost)
queue = deque(my_reserve)
cnt = 0
for i in my_lost:
for j in range(len(queue)):
if i - 1 == queue[j]:
cnt += 1
queue.popleft()
break
if i + 1 == queue[j]:
cnt += 1
queue.popleft()
break
return cnt + (n-len(my_lost))
큐 사용하지 않은 코드
def solution(n, lost, reserve):
my_lost = set(lost) - set(reserve)
my_reserve = set(reserve) - set(lost)
for i in my_lost:
if i - 1 in my_reserve:
my_reserve.remove(i-1)
continue
if i + 1 in my_reserve:
my_reserve.remove(i+1)
continue
else:
n -= 1
return n
조이스틱
*실패한 코드.
역시 초반에 어떻게 접근할 지 고민해보고 접근하는 게 중요하다.
초반 설계가 잘못되었다면 코드를 고친다고 해도 실패할 확률이 크다.
def solution(name):
order = 0
count = 0
for i in range(len(name)):
if name[i] == 'A':
left = 0
right = 0
while name[order - left] == 'A':
left += 1
while name[order + right] == 'A':
right += 1
count += min(left, right)
if left < right:
order -= left
else:
order += right
if ord(name[i]) <= ord('N'):
count += ord(name[i]) - 65
if i <= len(name) - 2:
if name[i+1] == 'A':
continue
else:
count += 1
order += 1
continue
if ord(name[i]) > ord('N'):
count += (91 - ord(name[i]))
if i <= len(name) - 2:
if name[i+1] == 'A':
continue
else:
count += 1
order += 1
continue
return count
*아래 코드 수정중
def solution(name):
name = list(name) # 문자열을 리스트로 변환
count = 0 # 조작 횟수
idx = 0 # 커서 위치
while True:
# 현재 위치의 알파벳을 조작하여 바꾸는 횟수 계산
count += min(ord(name[idx]) - ord('A'), ord('Z') - ord(name[idx]) + 1)
name[idx] = 'A' # 현재 위치의 알파벳을 'A'로 변경
if all(char == 'A' for char in name): # 모든 알파벳이 'A'인 경우 종료
break
left = 1 # 왼쪽으로 이동할 거리
right = 1 # 오른쪽으로 이동할 거리
# 왼쪽으로 이동할 거리 계산
while name[(idx - left) % len(name)] == 'A':
left += 1
# 오른쪽으로 이동할 거리 계산
while name[(idx + right) % len(name)] == 'A':
right += 1
# 커서 이동 및 조작 횟수 추가
if left < right:
idx = (idx - left) % len(name)
count += left
else:
idx = (idx + right) % len(name)
count += right
return count
큰 수 만들기
def solution(number, k):
answer = []
for i in number:
if not answer:
answer.append(i)
continue
while answer[-1] < i and k > 0:
answer.pop()
k -= 1
if not answer or k <= 0:
break
answer.append(i)
if len(answer) == len(number) - k:
break
return ''.join(answer)
구명보트
from collections import deque
def solution(people, limit):
my_list = sorted(people, reverse = True)
queue = deque(my_list)
count = 0
while queue:
if queue[0] + queue[-1] <= limit and len(queue) >= 2:
queue.popleft()
queue.pop()
count += 1
else:
queue.popleft()
count += 1
return count
동적계획법
N으로 표현
def solution(N, number):
dp = [set() for _ in range(9)]
# N을 한 번 사용한 경우
dp[1].add(N)
if number in dp[1]:
return 1
for i in range(2, 9):
dp[i].add(int(str(N) * i))
for j in range(1, i):
for x in dp[j]:
for y in dp[i - j]:
dp[i].add(x + y)
dp[i].add(x - y)
dp[i].add(y - x)
dp[i].add(x * y)
if y != 0:
dp[i].add(x // y)
if x != 0:
dp[i].add(y // x)
if y != 0 and x % y == 0:
dp[i].add(x // y)
if number in dp[i]:
return i
return -1
정수 삼각형
def solution(triangle):
memo = [[0] * len(triangle[i]) for i in range(len(triangle))]
memo[0][0] = triangle[0][0]
for i in range(len(triangle)):
for j in range(i):
memo[i][j] = max(memo[i][j], memo[i-1][j] + triangle[i][j])
memo[i][j+1] = memo[i-1][j] + triangle[i][j+1]
return max(memo[-1])
DFS/BFS
타켓 넘버
def solution(numbers, target):
def dfs(idx, current_sum):
nonlocal answer
if idx == len(numbers): # 모든 숫자를 확인한 경우
if current_sum == target: # 타겟 넘버와 일치하는 경우
answer += 1
return
# 현재 인덱스의 숫자를 더하거나 뺀 뒤 다음 인덱스로 재귀 호출
dfs(idx + 1, current_sum + numbers[idx])
dfs(idx + 1, current_sum - numbers[idx])
answer = 0
dfs(0, 0)
return answer
네트워크
def solution(n, computers):
visited = [[0] * n for _ in range(n)]
def dfs(node):
visited[node][node] = 1
for i in range(n):
if computers[node][i] == 1 and visited[i][i] == 0:
dfs(i)
count = 0
for i in range(n):
if visited[i][i] == 0:
dfs(i)
count += 1
return count
게임 맵 최단거리
from collections import deque
def solution(maps):
# 동서남북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[False] * len(maps[0]) for _ in range(len(maps))]
queue = deque()
queue.append((0, 0, 1))
visited[0][0] = True
answer = []
while queue:
x, y, distance = queue.popleft()
if x == len(maps) - 1 and y == len(maps[0]) - 1:
answer.append(distance)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
if maps[nx][ny] == 1 and visited[nx][ny] == False:
visited[nx][ny] = True
queue.append((nx, ny, distance+1))
if len(answer) == 0:
return -1
else:
return min(answer)
단어 변환
from collections import deque
def solution(begin, target, words):
if target not in words:
return 0
queue = deque()
visited = [0] * len(words)
queue.append((begin, 0))
while queue:
to_word, step = queue.popleft()
if to_word == target:
return step
for i, from_word in enumerate(words):
if visited[i] == 0 and verify(to_word, from_word):
visited[i] == 1
queue.append((from_word, step + 1))
return 0
def verify(word1, word2):
count = sum(w1 != w2 for w1, w2 in zip(word1, word2))
return count == 1
여행경로
from collections import defaultdict, deque
def solution(tickets):
# 그래프 생성
graph = defaultdict(list)
for ticket in tickets:
departure, arrival = ticket
graph[departure].append(arrival)
# 그래프 정렬
for key in graph:
graph[key].sort()
# BFS 탐색
answer = []
stack = ["ICN"]
while stack:
current = stack[-1]
if current not in graph or len(graph[current]) == 0:
answer.append(stack.pop())
else:
stack.append(graph[current].pop(0))
# 경로를 반대로 저장했으므로 역순으로 반환
return answer[::-1]
이분탐색
입국심사
def solution(n, times):
start = 1
end = max(times) * n
answer = 0
while start <= end:
mid = (start + end) // 2
count = 0
for time in times:
count += mid // time
if count >= n:
answer = mid
end = mid - 1
else:
start = mid + 1
return answer
징검다리
*10번 테스트 케이스는 통과 못함(런타임 에러)
def solution(distance, rocks, n):
rocks.sort()
start = 0
end = distance
answer = 0
while start <= end:
mid = (start + end) // 2
removed_rocks = 0
prev_rock = 0
min_distance = float('inf')
for rock in rocks:
if rock - prev_rock < mid:
removed_rocks += 1
else:
min_distance = min(min_distance, rock - prev_rock)
prev_rock = rock
if distance - prev_rock < mid:
removed_rocks += 1
if removed_rocks > n:
end = mid - 1
else:
answer = min_distance
start = mid + 1
return answer
그래프
문제
728x90
반응형