베스트 앨범
1. Problem
2. My Solution
- genres_dict : key = 장르, value = 총 재생수
- genres_song : key = 장르, value = [(i번째곡, 재생수),...]
- genres_rank : genres_dict 에서 총 재생수를 기준으로 내림차순 정렬한 결과
- 재생수를 기준으로 장르를 내림차순 정렬 -> 높은 장르부터 꺼내서 해당 장르에 속한 노래와 재생수를 담고 있는 리스트를 정렬한 뒤 1개 또는 2개 pop()
def solution(genres, plays):
answer = []
genres_dict = dict()
genres_song = dict()
genres_rank = []
for i in range(len(genres)):
genres_dict[genres[i]] = genres_dict.get(genres[i],0) + plays[i]
genres_song[genres[i]] = genres_song.get(genres[i],[]) + [(i,plays[i])]
# print(genres_dict) = {'classic': 1450, 'pop': 3100}
# print(genres_song) = {'classic': [(0, 500), (2, 150), (3, 800)], 'pop': [(1, 600), (4, 2500)]}
for i in genres_dict.items():
genres_rank.append(i)
genres_rank.sort(key = lambda x:x[1], reverse = True)
# print(genres_rank) = [('pop', 3100), ('classic', 1450)]
for i in range(len(genres_dict)):
# 재생횟수를 기준으로 1차정렬(오름차순), 인덱스를 기준으로 2차정렬(내림차순)
genres_song[genres_rank[i][0]].sort(key = lambda x:(x[1], -x[0]))
for _ in range(min(2,len(genres_song[genres_rank[i][0]]))):
answer.append(genres_song[genres_rank[i][0]].pop()[0])
return answer
3. Learned
- sort(key = lambda x:x[0]) 에서 내림차순 정렬하려면 -x[0] 지정
3진법 뒤집기
1. Problem
2. My Solution
def change(n):
result = []
while(n > 0):
n,mod = divmod(n,3)
result.append(mod)
return "".join(map(str,result))
def solution(n):
return int(change(n),3)
3. Learned
- 의외로 진법 변환하는 기능을 많이 요구함. 구글링이 되면 그냥 변환 부분을 가져오면 되지만 구글링이 안된다고 한다면 직접 구현해야되므로 어느정도 공식처럼 외우고 있어야함
- 10진법 -> 2,8,16 진법으로 변환은 bin(), oct(), hex() 함수를 이용
- n진법 -> 10 진법으로 변환은 int(num, n진법) 함수를 이용
최소 직사각형
1. Problem
2. My Solution
- 명함의 가로 또는 세로중에서 가장 큰 길이로 지갑의 가로 또는 세로를 지정해야함
- 가장 큰 길이를 정했으면 명함에서 작은 길이중 (큰 길이는 위에서 구한 길이에 맞추면 됨) 제일 큰 길이를 지갑의 나머지 부분으로 지정
def solution(sizes):
w = sorted(sizes, key = lambda x:x[0])
h = sorted(sizes, key = lambda x:x[1])
max_value = max(w[-1][0], h[-1][1])
second_value = 1
for i in sizes:
if second_value < min(i):
second_value = min(i)
return max_value * second_value
3. Others' Solution
def solution(sizes):
return max(max(x) for x in sizes) * max(min(x) for x in sizes)
4. Learned
- 코드 리팩토링을 통하여 코드의 사이즈를 줄이고 가독성을 높임
// 길이가 가장 큰 부분을 구하는 코드
w = sorted(sizes, key = lambda x:x[0])
h = sorted(sizes, key = lambda x:x[1])
max_value = max(w[-1][0], h[-1][1])
=> max(max(x) for x in sizes)
// 명함에서 길이가 작은 것들 중에서 가장 큰 부분을 구하는 코드
for i in sizes:
if second_value < min(i):
second_value = min(i)
=> max(min(x) for x in sizes)2016년 (요일구하기)
1. Problem
2. My Solution
- datetime 모듈의 weekday() 함수를 이용하여 해당 날짜의 요일에 대한 정수값을 얻어냄
- 0 : 월요일 ~ 6 : 일요일
import datetime
def solution(a, b):
weekday_match = ["MON","TUE","WED","THU","FRI","SAT","SUN"]
return weekday_match[datetime.datetime(2016,a,b).weekday()]
3. Learned
- 날짜 계산을 필요로하는 문제가 종종 출제되므로 날짜 관련 모듈인 datetime 모듈에 대한 사용법을 알고있어야함 (참고사이트)
시저암호
1. Problem
2. My Solution
def solution(s, n):
answer = ""
for alphabet in s:
asci = ord(alphabet)+n
if alphabet.isspace():
answer += " "
elif alphabet.islower():
if asci > 122:
answer += chr(96+asci-122)
else:
answer += chr(asci)
else:
if asci > 90:
answer += chr(64+asci-90)
else:
answer += chr(asci)
return answer
3. Others' Solution
def solution(s, n):
answer = ""
for alphabet in s:
if alphabet.isspace():
answer += " "
elif alphabet.islower():
answer += chr(((ord(alphabet)-97+n)%26)+97)
else:
answer += chr(((ord(alphabet)-65+n)%26)+65)
return answer
4. Learned
- 알파벳을 순환하는 문제도 종종 출제되는데, 이 때 정방향 또는 역방향으로 순환하게 됨
// n 번 만큼 정방향으로 이동한다고 할 때
// -1%26 = 25 이므로 -n 번 만큼 역방향으로 이동한다고 할 때도 동일하게 사용
chr(((ord(alphabet)-65+n)%26)+65)모두 0으로 만들기
1. Problem
2. My Solution
- 가중치의 총합이 0이 아니면 -1을 출력해야함
- 행동을 최소로 하기 위해서는 연결된 간선의 수가 작은 노드부터 0으로 만들어야된다고 생각해서 노드에 연결된 간선의 수를 각각 계산하고, 간선의 수를 기준으로 오름차순 정렬하여 해당 노드 순서대로 0을 만들어 나감 -> 실패 (행동을 취할 노드를 정할 때 순서의 기준없이 랜덤으로 정하게되고, 중간에 끊기는 경우도 생김)
def solution(a, edges):
graph = [[] for _ in range(len(a))]
conn_cnt = [0] * len(a)
order = []
answer = 0
# 가중치의 총합이 0이 아니면 만들 수 없으므로 return -1
if sum(a) != 0:
return -1
# 연결된 간선의 수를 기준으로 오름차순 정렬하는 부분
for edge in edges:
conn_cnt[edge[0]] += 1
conn_cnt[edge[1]] += 1
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
for idx,cnt in enumerate(conn_cnt):
order.append((idx,cnt))
order.sort(key = lambda x:x[1])
# 간선의 수가 작은 노드부터 0으로 만듬
for node, _ in order:
for victim in graph[node]:
if a[victim] != 0:
a[victim] += a[node]
answer += abs(a[node])
a[node] = 0
return answer
3. Others' Solution
- 그래프가 항상 트리로 주어지므로 임의의 노드를 루트로 설정하고 리프노드부터 루트까지 올라가면서 0으로 만들면 됨
- dfs 를 이용하면 dfs 를 호출하면서 루트노드에서 리프노드까지 방문할 수 있고, dfs 호출이 종료되고 다시 돌아오면서 리프노드에서부터 루트노드까지 이동할 수 있음
import sys
sys.setrecursionlimit(10**8)
def solution(a, edges):
def dfs(node):
nonlocal answer
visited[node] = True
for u in graph[node]:
if visited[u] == False and a[u] != 0:
dfs(u)
a[node] += a[u]
answer += abs(a[u])
graph = [[] for _ in range(len(a))]
visited = [False] * len(a)
answer = 0
# 가중치의 총합이 0이 아니면 만들 수 없으므로 return -1
if sum(a) != 0:
return -1
for u,v in edges:
graph[u].append(v)
graph[v].append(u)
dfs(0)
return answer
4. Learned
- 트리에서 DFS 알고리즘을 이용하면 루트노드에서 리프노드까지 방문할 수 있음. 이를 역으로 생각한다면 리프노드에서 루트노드까지 방문하는 원리 또한 생각해낼 수 있음
