디너코딩

솔루션

from collections import defaultdict

def solution(n, results):
    answer = 0
    win,lose =defaultdict(set),defaultdict(set)
	# win:key[승리자] values[패배자] / lose:key[패배자] values[승리자]
    for winner,loser in results:
        win[winner].add(loser)
        lose[loser].add(winner)
    
    for i in range(1,n+1):
        # i에게 진 사람은 i를 이긴 사람에게 진다.
        # i에게 이긴 사람은 i에게 진 사람을 이긴다.
        for loser in win[i]:
            lose[loser].update(lose[i])
        for winner in lose[i]:
            win[winner].update(win[i])
    
    # 승패 결과가 본인을 제외한 모든 이와의 경기에서 확정날 경우 순위가 결정
    for i in range(1,n+1):
        if len(win[i])+len(lose[i]) == n-1:
            answer+=1
    
    return answer

너비우선탐색(BFS) 기법을 사용하여 1번 노드에서 각 노드까지의 최단 경로를 계산하여 visited에 딕셔너리 형태로 저장합니다. 그 후 가장 먼 노드의 경로와 같은 값을 갖고 있는 노드를 세서 반환합니다.

솔루션

from collections import defaultdict,deque

def solution(n, edge):
    answer = 0
    graph = defaultdict(list)
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)

    visited= defaultdict(int)
    queue = deque([[1,0]])
    
    # BFS
    while queue:
        current_node,num = queue.popleft()   
        if current_node not in visited:
            visited[current_node] =num
            for adj_node in graph[current_node]: 
                if adj_node not in visited:
                    queue.append([adj_node,num+1])
    # 가장 먼 노드                
    distance = sorted(visited.values(), reverse=True)
    longest = distance[0]
    
    return distance.count(longest)

이 문제의 핵심은 현재 상황에서 가장 무거운 사람과 가장 가벼운 사람의 무게를 합친 무게가 주어진 무게 제한보다 작거나 같도록 짝꿍을 짓는 것입니다. 몸무게를 정렬해준 후 왼쪽 끝에서부터와 오른쪽 끝에서부터의 무게를 비교하여 최대한 많이 짝꿍을 지어줍니다. 

솔루션

def solution(people, limit):
    people=sorted(people)
    count,left,right=0,0,len(people)-1
    
    while left <= right:
        queue=[]
        if people[right]+people[left] <= limit:
            left+=1
        right-=1
        count+=1
    return count

이번 문제에서는 스택을 사용하여 문제를 풀어보았습니다. number의 자리수가 1,000,000자리이기 때문에 시간초과를 유의해야 합니다. 앞에서부터 차례대로 숫자를 stack에 저장하다가, 뒤에 나온 숫자가 저장된 숫자보다 클 시 pop해주고 뒤에 나온 숫자를 저장합니다. k개의 수를 제거할 수 있으므로 pop을 해줄 때마다 count를 해줍니다. 그 후, 만일 k가 양수라면 뒤에부터 k개만큼 제거하여 반환합니다.

솔루션

def solution(number, k):
    answer = ''
    idx=0
    a=['-1']
    num = len(number)
    length=num-k
    for i in range(len(number)):
        while a and a[-1] < number[i] and k>0:
            a.pop()
            k-=1
        a.append(number[i])
        
    return ''.join(a[:-k])

이분탐색은 원하는 값이 중간값보다 크다면 오른쪽을 탐색하고 중간값보다 작다면 왼쪽을 탐색하며 원하는 값을 탐색하는 기법입니다.

예를 들어, 1~10까지 상대가 생각한 수를 이분탐색 기법을 사용하여 찾아보겠습니다. 상대가 생각하는 수를 7이라고 생각해봅니다.

중간값 < 원하는 값 up

중간값 > 원하는 값 down

1. 1~10의 중간 값 = 5 -> up

2. 6~10의 중간 값 = 8 -> down

3. 6~8 의 중간 값 = 7 -> 답

입국심사 문제는 입국 심사하는데 걸리는 시간을 최소화하도록 입국 심사 하는 사람들을 심사대에 잘 배분하는 것입니다. 심사하는데 걸리는 시간을 각 심사대가 처리하는 시간으로 나눈 몫을 더하면 입국 심사 하는 사람들의 수가 나옵니다. 이 점을 활용하여 이분 탐색을 실시합니다. 

솔루션

def solution(n, times):
    left = 1
    right = n * min(times)
    mid=0
    while left < right:
        mid = (left+right) // 2
        m = 0
        for time in times:
            m += mid//time

        if m >= n:
            right = mid
        else:
            left = mid+1

    return left

left를 반환하는 이유는 입국 심사하는데 걸리는 최소한의 시간을 반환해야 하기 때문입니다.

pandas의 cut과 qcut은 간단히 설명하면 절대평가와 상대평가의 의미와 비슷합니다.  절대평가는 특정 점수 이상일 경우에 성적을 부여하는 것이고 상대평가는 인원수에 따라 상위 몇 %인지에 따라 성적이 부여됩니다.

cut의 경우 특정 점수가 부여되고 그 점수를 경계로 성적이 부여되고, qcut의 경우 상위 퍼센트가 부여되고 그 퍼센트를 경계로 성적이 부여됩니다. 

예시를 통해 알아보겠습니다.

CUT

import pandas as pd
import numpy as np

df=pd.read_csv('StudentsPerformance.csv')
df.head()

df.columns

df = df.drop(columns=['race/ethnicity', 'parental level of education', 'lunch', 'test preparation course'])
df.head()

pd.cut(df['math score'],bins=4)

pd.cut(df['math score'],bins=4).value_counts()

grades = ['C','B-', 'B', 'A-', 'A']
cut_bins = [0, 40, 55, 65, 85, 100]

df['grades'] = pd.cut(df['math score'], bins = cut_bins, labels = grades)
df.head()

qcut

pd.qcut(df['math score'],q=4)

pd.qcut(df['math score'], q=4).value_counts

df['math score'].describe()

[참조]

https://www.youtube.com/watch?v=cgpiFkpBLyY

레벨 2

그리디 알고리즘

그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 알고리즘입니다. 각 단계에서 했던 최선이 선택이 전체적으로 가장 최선의 선택이라고 생각하는 것입니다.

조이스틱 문제는 ①커서를 바꾸는 횟수, ②알파벳을 바꾸는 횟수를 합하여 조이스틱을 최소로 조작하는 것입니다. 알파벳을 바꾸는 횟수는 그렇게 어렵지 않습니다. O-ZA-N순으로 알파벳을 정렬하여 아스키 코드 값을 빼줍니다. 문제는 커서를 바꾸는 횟수입니다. 커서를 오른쪽으로 혹은, 왼쪽으로 갈것인지 선택해야 합니다. 또한 한방향으로 쭉 가는 것이 아니라, 오른쪽으로 갔다가 왼쪽으로 갈 수도 있습니다. 예를 들면 'JBAAN'과 같은 경우 B 위치로 커서를 옮긴 후 오른쪽으로 3칸 이동하는 것보다 왼쪽으로 2칸 이동하는 것이 더 이득입니다.

따라서 그리디 알고리즘을 적용하여 커서를 이동하도록 작성해봅니다. 현재 커서 위치에서 바꾸어야 할 알파벳이 있는 곳까지 오른쪽과 왼쪽의 인덱스를 셉니다. 둘 중 인덱스가 더 적은 쪽으로 이동을 합니다. 현재의 위치에서 최선의 선택을 하는 것이 그리디 알고리즘이라는 것을 생각해보면 이해가 갈 것입니다. 

솔루션

def solution(name):
    answer = 0
    asci=[]
    # name의 각 단어를 아스키 코드로 변환
    for i in name:
        a=ord(i)
        if a>=79:
            asci.append(a-26)
        else:
            asci.append(a)
            
    print(asci)
    first=[ord('A')]*len(name)
    current=0
    
    # 똑같아 질 때까지 반복
    while asci != first:
        left_idx=0
        right_idx=0
        
        # 왼쪽 인덱스 개수 세기
        while asci[current+left_idx] == first[current+left_idx]:
            left_idx-=1
            
        # 오른쪽 인덱스 개수 세기
        while asci[current+right_idx] == first[current+right_idx]:
            right_idx+=1
            
        # 비교 후 현재 인덱스 변경, 커서 개수 세기
        if abs(left_idx)<right_idx:
            current+=left_idx
            answer += abs(left_idx)
        else:
            current+=right_idx
            answer += right_idx
        
        # 변환하기
        answer+= abs(asci[current] - first[current])
        asci[current] = first[current]
        print(left_idx, right_idx, current, answer)
    
    return answer

레벨3

풀이방법 1

def solution(jobs):
    answer = 0
    now, start,i = 0,-1,0
    heap = []
    # 모든 작업을 할 때까지 반복
    while i < len(jobs):
        # start 부터 now 시간까지에 들어 있는 모든 작업들을 heap에 heappush
        for job in jobs:
            if start < job[0] <= now :
                heapq.heappush(heap,[job[1], job[0]]) # 작업 시간(job[0])을 비교해야 하므로 0번에 삽입
        # heap 에 있는 작업시간이 낮은 것부터 heappop()
        if len(heap) != 0 :
            dur, s = heapq.heappop(heap)
            start = now
            now = max(s+dur, now+dur) # 요청 시간과 현재 시간의 max 값을 비교
            answer += now - s
            i+=1
            print(now,s)
        # heap에 아무것도 없을 경우 1씩 증가
        elif len(heap) ==0:
            now += 1
    return answer // len(jobs)

풀이방법 1과 유사하지만 jobs에서 데이터 자체를 heappop하는 것도 가능하다. 

풀이방법 2

import heapq
def solution(jobs):
    answer = 0
    num = len(jobs)
    heapq.heapify(jobs)
    start, now,i = 0,0,0
    heap = []

    while i<num:
        while len(jobs)!=0 and jobs[0][0] <= now :
            s,t=heapq.heappop(jobs)
            heapq.heappush(heap,[t,s])
        if len(heap) != 0:
            dur, s = heapq.heappop(heap)
            now = max(s,now)+dur
            answer += (now-s)
            i+=1
        else:
            now+=1
    return answer//num

레벨 2

heapq (우선 순위 큐) 개념

import heapq

list1 = [5,2,6,3,4,1]
heap = []
for i in list1:
	heapq.heappush(heap,i)
print(heap)

[1, 3, 2, 5, 4, 6]

heapq는 우선 순위 큐로 heappush() 함수를 사용하면,  k번째 인덱스에 있는 원소가 2k+1, 2k+2 번째 인덱스에 있는 원소보다 같거나 작습니다. 예를 들어, 3이라는 원소는 인덱스 1이고, 인덱스 2k+1(3), 2k+2(4) 에 해당하는 5와 4보다 작은 값을 갖습니다. 

import heapq

list1 = [5,2,6,3,4,1]
heap = []
for i in list1:
	heapq.heappush(heap,i)

sort = []
while heap:
    sort.append(heapq.heappop(heap))
print(sort)

이 때, heappop() 함수는 heap 리스트를 받아서 원소 값이 가장 작은 값부터 추출을 합니다. 중요한 점은 heap 리스트의 모든 원소가 heappush() 함수로 추가가 되어 있기 때문에 최솟값부터 추출할 수 있다는 것입니다. 만일 heap 리스트가 무작위로 배치되어 있다면 heapify() 함수를 사용합니다. 

import heapq

heap = [5,2,6,3,4,1]
heapq.heapify(heap)

sort = []
while heap:
    sort.append(heapq.heappop(heap))
print(sort)

문제풀이

import heapq

def solution(scovile, K):
    heap=[]
    # 스코빌 지수 리스트 heapq로 배치
    for i in scovile:
        heapq.heappush(heap,i)
    count=0
      
    while True:
        a = heapq.heappop(heap)
        if a >= K :
            return count
        try :
            b = heapq.heappop(heap)
        except:
            return -1               # heap 이 비어있을 경우
        heapq.heappush(heap,a+2*b)
        count+=1

레벨1 K번째 수

def solution(array, commands):
    answer = []
    cut=[]
    for i in range(len(commands)):
        for r in range(commands[i][0]-1,commands[i][1]):
            cut.append(array[r])
        
        cut = sorted(cut)        
        answer.append(cut[commands[i][2]-1])
        cut=[]
    return answer

레벨2 가장 큰 수

def solution(numbers):

    a=[]
    c=''
    for i in numbers:
        a.append([(str(i)*4)[0:4],str(i)])
    a=sorted(a,reverse=True)
    for i in range(len(a)):
        c+=a[i][1]
    if int(c)==0:
        return '0'

    return c

레벨2 H-Index

def solution(citations):
    
    
    while citations:
        a=citations.index(min(citations))
        b=citations.pop(a)
        
        if len(citations)+1 <= b:
            return len(citations)+1
            break
        
    return 0