programmers : 베스트 앨범, 3진법 뒤집기, 최소 직사각형, 2016년 (요일구하기), 시저암호, 모두 0으로 만들기

베스트 앨범

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 알고리즘을 이용하면 루트노드에서 리프노드까지 방문할 수 있음. 이를 역으로 생각한다면 리프노드에서 루트노드까지 방문하는 원리 또한 생각해낼 수 있음