✅ Hash 문제풀이
🎈 폰켓몬
폰켓몬 종류는 숫자로 표시되고, nums 길이의 절반만큼 폰켓몬을 데려갈 수 있을 때 최대한 다양한 종류의 폰켓몬을 가져가려 한다. 데려갈 수 있는 폰켓몬의 최대 종류 수를 구하는 문제
def solution(nums):
answer = 0
check = set(nums)
if len(check) >= len(nums)//2:
answer = len(nums)//2
else:
answer = len(check)
return answer< 풀이 과정 >
주어진 nums를 set 자료구조로 변환하여, set 자료구조의 길이가 nums의 절반 크기보다 크다면, 종류가 다양한 폰켓몬이 있음을 의미하므로 nums 절반 크기를 리턴하고, 아닌 경우 set자료형 길이만 리턴한다.
🎈 완주하지 못한 선수
마라톤에 참여한 선수 목록 participant와 완주자들의 목록인 completion이 주어질 때 완주하지 못한 선수를 리턴하는 문제
def solution(participant, completion):
member = {}
value = 0
for i in participant:
member[hash(i)] = i
value += hash(i)
for i in completion:
value -= hash(i)
return member[value]< 풀이 과정 >
해시 자료구조를 이용해 구현하였다.
member딕셔너리와 value를 만들어주고 마라톤 참여자들을 해시로 저장한다.
이후 완주자들에 한해 value에서 빼주면 member[value]에는 결국 완주하지 못한 사람만 남게된다.
🎈 전화번호 목록
전화번호 목록인 phone_book이 주어지고, 일부번호가 phone_book내 번호의 접두사인 경우 false를 아니면 true를 리턴하는 문제
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i] in phone_book[i+1][:len(phone_book[i])]:
return False
return True< 풀이 과정 >
phone_book을 번호순대로 정렬한 이후, for문으로 이전 전화번호가 다음 전화번호의 접두어인 경우 False를, 아니면 True를 리턴한다.
🎈 위장
스파이는 매번 옷을 다르게 입고, 같은 종류를 2개 이상 겹쳐서 착용할 수 없다. 이때 여러 종류들을 조합하여 입을 수 있는 경우의 수를 구하는 문제
def solution(clothes):
answer = 1
closet = {}
for cloth in clothes:
if cloth[1] not in closet:
closet[cloth[1]] = 1
else:
closet[cloth[1]] += 1
for i in closet.values():
answer *= (i+1)
return answer - 1 < 풀이 과정 >
closet 딕셔너리를 만들어서, clothes들의 1번째 인덱스를 통해 해당 종류가 없다면 1을, 있으면 +1 하여 개수를 저장한다.
이후, closet 딕셔너리의 값들을 i+1만큼 곱해 answer를 계산하여 아무것도 안입은 경우인 1을 빼서 리턴한다.
예로, headgear가 3개, eyewear가 2개라면, 총 경우의 수는 각 개수 5개 + headgear 1개 당 eyewear 2개씩 6개로 총 11가지다. 따라서 각 종류 개수 +1을 곱한 후 -1해주는 방식으로 구현했다.
🎈 베스트앨범
노래의 장르를 나타내는 genres와 각 노래 별 재생 횟수를 나타낸 plays를 입력받아 각 장르별로 가장 많이 재생된 2개의 노래를 리턴하는 문제
def solution(genres, plays):
answer = []
# 장르 별 총 재생횟수 저장
total_play = {}
# 음악 고유 번호 별 재생횟수, 고유번호 저장
genre_play = {}
# 장르 별로 총 재생횟수 목록에 재생횟수 값 저장
for i in range(len(genres)):
if genres[i] not in total_play:
total_play[genres[i]] = plays[i]
else:
total_play[genres[i]] += plays[i]
# 음악 고유번호 별로 재생횟수, 고유번호 저장
if genres[i] not in genre_play:
genre_play[genres[i]] = [[plays[i], i]]
else:
genre_play[genres[i]].append([plays[i], i])
# 총 재생횟수 시간 value를 기준으로 내림차순 정렬
total_rank = sorted(total_play, key = total_play.get, reverse=True)
# genre_play를 재생횟수 기준으로 내림차순 정렬
for i in total_rank:
play_rank = sorted(genre_play[i], key = lambda x : (-x[0]))
# 재생목록이 1개라면 해당 값만 append
if len(play_rank) == 1:
answer.append(play_rank[0][1])
else:
아닌 경우, 2개의 노래만 저장하므로 for문으로 재생횟수 가장 많은 2개 노래 append
for i in range(2):
answer.append(play_rank[i][1])
return answer< 풀이 과정 >
장르 별로 재생횟수를 다 더한 정보를 저장할 변수 total_play와 음악 고유번호 별 재생횟수와 고유번호를 리스트로 저장한 딕셔너리 genre_play를 만들어준다.
for문으로 장르 길이만큼 순회하며 genre정보를 total_play와 genre_play에 저장해준다.
genre정보를 담은 total_play를 바탕으로 재생횟수를 내림차순 정렬해 total_rank를 만들고 genre_play를 바탕으로 내림차순 정렬하여 같은 장르 내 재생횟수가 많은 노래들을 정렬해준다.
이후 play_rank길이가 2개 이상인 경우, 1개인 경우를 나누어 answer에 추가해준다.
✅ 완전 탐색
🎈 최소직사각형
명함 별로 가로, 세로가 주어지고 주어진 명함들을 모두 넣을 수 있는 지갑의 가로 세로 길이를 리턴하는 문제
def solution(sizes):
for i in range(len(sizes)):
if sizes[i][0] < sizes[i][1]:
sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0]
print(sizes)
sizes.sort(key = lambda x: x[0], reverse = True)
w = sizes[0][0]
sizes.sort(key = lambda x: x[1], reverse = True)
h = sizes[0][1]
return w*h< 풀이 과정 >
주어진 sizes에서 가로보다 세로가 길다면 값을 바꿔준 후, 가로,세로를 기준으로 내림차순 정렬하여 큰 값들을 변수로 저장한뒤, 두 변수를 곱하여 리턴하는 문제
🎈 모의고사
1,2,3 번 학생의 수포자가 찍는 방식으로, 주어진 답안인 answers에 많이 맞춘 순서대로 결과를 리턴하는 문제
def solution(answers):
answer = []
score = [0, 0, 0]
student_1 = [1,2,3,4,5]
student_2 = [2,1,2,3,2,4,2,5]
student_3 = [3,3,1,1,2,2,4,4,5,5]
for i, ans in enumerate(answers):
if ans == student_1[i%5]:
score[0] += 1
if ans == student_2[i%8]:
score[1] += 1
if ans == student_3[i%10]:
score[2] += 1
for i in range(len(score)):
if score[i] == max(score):
answer.append(i+1)
return answer< 풀이 과정 >
각 학생 별로 찍는 방식이 상이하기에 미리만들어주고 학생 별 answers와 비교해 score를 산출하기 위해 score = [0, 0, 0]을 만들었다.
이후 for문으로 score길이만큼 돌아 score내부의 값이 max값이면 answer에 인덱스+1을 추가해 리턴한다.
🎈 소수찾기
한자리 숫자가 적힌 종이로 만들 수 있는 소수의 개수를 구하는 문제.
ex) 17이 주어진 경우, 소수는 7, 17, 71로 3개를 만들 수 있다.
from itertools import permutations
def solution(numbers):
answer = []
nums = [i for i in numbers]
case = []
for i in range(1, len(numbers)+1):
case += list(permutations(nums, i))
check_num = [int(''.join(j)) for j in case]
for n in check_num:
check = True
if n < 2:
continue
for i in range(2, int(n**0.5)+1):
if n % i == 0:
check = False
break
if check:
answer.append(n)
return len(set(answer))< 풀이 과정 >
주어진 numbers 문자를 그대로 for문을 돌려 case리스트에 numsPi로 순열 조합을 한 후, 리스트 내 모든 문자를 숫자로 변환한 check_num리스트를 만들어준다.
그 후, check_num내 숫자들이 소수인 경우 check = False로 만들고, True에 한해 answer에 추가해준다. 순열조합이므로 중복값이 포함되어 있기에 set(answer)로 만든 후 answer set자료구조의 길이를 리턴한다.
🎈 전력망을 둘로 나누기
n개이 송전탑이 주어지고 n-1개의 wires가 주어진다. 송전탑은 트리 형태로 연결되어 있고 전선 중 하나를 끊어서 송전탑 개수가 비슷하도록 만들 때, 두개로 나뉜 송전탑의 개수 차이를 리턴하는 문제
from collections import deque
def solution(n, wires):
graph = [[] for _ in range(n+1)]
for a, b in wires:
graph[a].append(b)
graph[b].append(a)
def bfs(start):
queue = deque([start])
visited = [0]*(n+1)
visited[start] = 1
cnt = 1
while queue:
v = queue.popleft()
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = 1
cnt += 1
return cnt
answer = 1e9
for a, b in wires:
graph[a].remove(b)
graph[b].remove(a)
answer = min(answer, abs(bfs(a) - bfs(b)))
graph[a].append(b)
graph[b].append(a)
return answer< 풀이 과정 >
deque를 활용한 BFS 풀이를 하였다.
빈 그래프를 n+1 크기로 2차원 배열을 만들고, wires를 통해 전선을 양방향 그래프로 표현하였다. 시작점을 입력받아 visited(방문처리)후, queue가 빌때까지 진행하여 연결된 간선들 중, 방문하지 않은 곳에 한해 방문하며 탑의 개수 cnt를 리턴하는 BFS함수를 만들었다.
이후, answer를 1e9로 큰 값으로 저장해놓고, 그래프 내 간선을 제거하면서 answer 최솟값을 구해낸다. 다음 전선이 끊긴 후 값 비교를 위해 다시 양방향 append를 해준 후 answer를 리턴한다.
🎈 모음 사전
사전에 알파벳 모음 A,E,I,O,U로 만들 수 있는 모든 단어가 수록되어 있다. 첫 단어는 A이고 마지막 단어는 UUUUU일때 주어진 WORD가 몇번째 단어인지 리턴하는 문제
def solution(word):
answer = 0
alphabet = ['A', 'E', 'I', 'O', 'U']
alpha_idx = [5**i for i in range(len(alphabet))]
for i in range(len(word)-1, -1, -1):
idx = alphabet.index(word[i])
for j in range(5-i):
answer += alpha_idx[j] * idx
answer += 1
return answer < 풀이 과정 >
수학적으로 접근하여 풀이하였다. 예제로 주어진 AAAAE를 살펴보면 맨 앞자리 A부터 (5^4 + 5^3 + 5^2 + 5^1 + 5^0) 0 + 1 이고, 두번째 A는 (5^3 + 5^2 + 5^1 + 5^0) 0 + 1, 마지막 E는 5^0 2이다.
이를 보아, 5의 자리수 별 제곱수 인덱스임을 알게되었다.
따라서 이를 구현하기 위해, 우선 5의 제곱수들을 alpha_idx리스트로 미리 만들어 주었다. 이후, for문으로 4>0순으로 돌며 알파벳 모음들의 인덱스를 저장하고 for문으로 j는 1부터 5까지 시작하는 인덱스를 만들어 answer = 5의 제곱수 * 알파벳 모음의 인덱스로 값을 만들고, 1의 자리수는 answer + 1로 처리하여 해결하였다.
