[DEV] 2주차. 자료구조/알고리즘(4)

1. Hash 대표 문제 - 완주하지 못한 선수

해시 문제

이름과 그에 따른 횟수를 기록하는 경우

문제 설명

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

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

제한 사항

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

입출력 예

스크린샷 2023-10-19 오후 3 53 36

문제의 풀이

participant 의 이름과 이름이 등장한 횟수를 hash table에 저장
completion 에서 나온 이름들은 있는 개수만큼 뺄셈
마지막에 hash table에 개수가 남아있는 이름 반환
python dictionary 사용!!
사전의 원소들을 해시를 이용해 $O(1)$ 시간에 접근 가능

코드

def solution(participant, completion):
    d = {}

    for x in participant:
        d[x] = d.get(x, 0) + 1   # 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

알고리즘 복잡도

3-4행, 5-6행 for문 2개
- participant, completion 배열의 길이에 비례
7행 for문
- 사전 d의 크기에 비례
- 사전의 크기는 participant 크기에 비례함
함수 전체의 시간 복잡도
- participant 배열의 길이에 비례하는 linear time 알고리즘
- hash table을 key를 기준으로 상수 시간으로 읽고 쓸 수 있었기 때문!

다른 풀이

정렬 을 이용!
- 알파벳 순 정렬
- participant에는 있고, completion에는 없는 원소 찾기
- 앞에서부터 하나씩 비교
- 정렬의 최소 시간이 $O(nlogn)$ 이기 때문에 위의 풀이가 더 나음!

2. Greedy 대표 문제 - 체육복

Greedy Algorithm

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

현재의 선택이 마지막 해답의 최적성을 해치지 않을 경우 Greedy Algorithm으로 최적해를 찾을 수 있음

문제 설명

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

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

제한 사항

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

입출력 예

스크린샷 2023-10-19 오후 11 31 59

문제 풀이

빌려줄 학생들을 정해진 순서로 살펴야 하고, 이 정해진 순서에 따라 우선하여 빌려줄 방향을 정해야 함

방법 1

착안점) 학생의 수는 기껏해야 30!
학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수 기록
번호 순서대로 스캔하면서 빌려줄 관계를 정함

알고리즘 복잡도

여벌을 가져온 학생 처리 : reverse의 길이에 비례
체육복을 잃어버린 학생 처리 : lost의 길이에 비례
체육복 빌려주기 처리 : 전체 학생 수 (n)에 비례
전체 : $O(n)$ (linear time)

방법 2

만약 전체 학생 수가 매우 크다면?
문제의 성질 상 $O(n)$ 보다 낮은 복잡도 알고리즘은 어려울 듯
그러나, 여벌의 체육복을 가져온 학생은 매우 적다면?
여벌의 체육복을 가져온 학생들의 번호 reverse를 정렬하고,
이것을 하나하나 순서대로 살펴보면서 빌려줄 수 있는 다른 학생을 찾아서 처리

알고리즘 복잡도

reverse 정렬 : $O(klogk)$
빌려줄 수 있는 다른 학생 처리 : 해시를 적용해서 상수 시간에 처리 $O(k) x O(1) = O(k)$
전체 : $O(klogk)$
reverse와 lost 배열 길이의 차이가 매우 클 경우에 유용

방법 1 코드

def solution(n, lost, reverse):
    u = [1] * (n + 2)  # 1번 보다 앞, n번보다 뒤

    for i in reverse:
        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])

방법 2 코드

def solution(n, lost, reverse):
    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)
    # l에 남아있는 학생들: 빌려야 하는데 빌리지 못한 학생들
    return n - len(l)

3. 정렬 대표 문제 - 가장 큰 수

문제 설명

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

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

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

제한 사항

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

입출력 예

스크린샷 2023-10-20 오전 12 46 33

방법 1

빈 문자열로 수 초기화
가장 크게 만들 수 있는 수 고름
그 수를 현재 수에 이어 붙임
모든 수를 다 사용할 때까지 반복
복잡도 : 목록의 길이의 제곱에 비례 $O(n^2)$

방법 2 (더 나음)

빈 문자열로 수 초기화
수의 목록을 (크게 만드는 것 우선으로) 정렬
목록에서 하나씩 꺼내어 현재 수에 이어 붙임
모든 수를 다 사용할 때까지 반복
복잡도 : 정렬 $O(nlogn)$

알고리즘 설계

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

코드

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

알고리즘 복잡도

2행 : $O(n)$
3행 (정렬) : $O(nlogn)$
4-5행 : $O(1)$
6-7행 : $O(n)$
전체 : $O(nlogn)$

4. Greedy 대표 문제 - 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

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

제한 조건

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

입출력 예

스크린샷 2023-10-20 오후 4 02 13

큰 수 만들기

앞 자리에 큰 수가 오는 것이 전체를 크게 만듦
- 큰 것을 우선해서 골라 담기!
앞 자리에서부터 하나씩 골라 담되, 지금 담으려는 것보다 작은 것들은 도로 뺌
- 뺄 수 있는 개수에 도달할 때까지만 (k)
큰 수가 앞자리에, 작은 수가 뒷자리에 놓이도록
- 제약조건 : 뺄 수 있는 수의 개수

알고리즘 설계

주어진 숫자 number로부터 하나씩 꺼내어 모으되
- 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼냄
  - 오른쪽부터 왼쪽으로 살펴봄
이렇게 모은 숫자들을 자릿수 맞추어 반환
- 아직 뺄 개수(k)를 채우지 못한 경우
  - 자릿수 계산!

알고리즘 복잡도

가장 단순한 방법: 모든 경우의 수를 계산해서 비교
- 매우 복잡
위에서 설계한 알고리즘 복잡도 : $O(n)$

코드

def solution(number, k):
    collected = []
    
    for i, num in enumerate(number):
        while len(collected) > 0 and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
        if k == 0:
            collected += list(number[i:])
            break
        collected.append(num)

    collected = collected[:-k] if k > 0 else collected
    answer = ''.join(collected)
    return answer