누런강냉이

해시

완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

해시란? 해시 테이블이라고 불리우는 저장공간에다 키들이 어느 위치에 있을지 정해 해시 테이블에 값을 저장하는 것.

값들의 위치를 결정하는데에는 hash function이 이용된다. 해시 테이블의 각각의 저장공간을 hash bucket이라고 한다.

코드 구현

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x,0) +1 #get(x,0) x가 존재하면 키에 해당하는 값을, 존재하지 않으면 0을 return 
    for x in completion:
        d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0]
    answer = dnf[0]
    return answer

시간복잡도 : O(n)

탐욕법

체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

탐욕법이란? 알고리즘의 각 단계에서 그 순간 최적이라고 생각되는 것을 선택

현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법 활용 가능

코드 구현

def solution(n, lost, reserve):
    u = [1]*(n+2)
    for i in reserve:
        u[i]+=1
    for i in lost:
        u[i]-=1
        
    for i in range(1, n+1):
        if u[i-1]==0 and u[i]==2:
            u[i-1:i+1]=[1,1]
        elif u[i] == 2 and u[i+1] == 0:
            u[i:i+2]=[1,1]
            
            
    return len([x for x in u[1:-1] if x > 0])

시간복잡도 : O(n)

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
            
    return n-len(l)

시간복잡도 : O(klogk)

정렬

가장 큰 수 

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

문제 해결 방법

1. 빈 문자열로 수 초기화
2. 수 목록을 (크게 만드는 것 우선) 정렬
3. 목록에서 하나씩 꺼내 현재 수에 이어 붙인다.
4. 모든 수를 다 사용할 때까지 반복

알고리즘 설계

• 대소 관계 비교를 위한 기준 마련
• 기준을 이용해 주어진 배열 정렬
• 정렬된 배열을 이용해 문자열 표현 완성

코드 구현

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x : (x*4)[:4], reverse=True)
    if numbers[0]=='0':
        answer='0'
    else:
        answer = ''.join(numbers)
    return answer

시간복잡도 : O(nlogn) (정렬하면서..)

탐욕법

큰 수 만들기

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

문제 해결 방법

• 큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록 한다.

알고리즘 설계

• 주어진 숫자로부터 하나씩 꺼내 모은다.
  • 이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다.
• 모은 숫자들을 자릿수 맞춰 반환한다.
  • 아직 뺄 개수를 채우지 못한 경우를 고려한다.

코드 구현

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
        while len(collected)>0 and collected[-1]<num and k>0: 
            #아직까지 빼낼 게 남아있고 (k>0) 
            #마지막 글자가 현재 글자보다 작고 (collected[-1]<num) 
            #collected의 길이가 0보다 클 때동안 (len(collected)>0)
            collected.pop()
            k-=1
        if k==0:
            collected += list(number[i:])
            break
        collected.append(num)
        
    collected = collected[:-k] if k>0 else collected 
    #만약 k가 0보다 크면 즉, 잘라야 할 문자가 남았다면 맨 뒤부터 남은 문자 갯수만큼 잘라준다.
    return ''.join(collected)

시간복잡도 : O(n)