자료구조/알고리즘 (4)

해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수

자료구조와 알고리즘의 선택

만약 이름 대신 번호가 주어졌다면? -> 선형 배열
번호 말고 다른 것 (예: 문자열)로 접근할 수 있는 좋은 자료구조는 없나요? 해시(Hash)

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

정렬을 이용한다면?

복잡도 : O(nlogn)

탐욕법 (Greedy) 대표 문제 풀이 : 체육복

탐욕법 (Greedy Algorithm)

알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
탐욕법으로 최적해를 찾을 수 있는 문제 : 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때

탐욕법 적용 가능성 확인

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

문제의 해결 - 방법(1)

학생의 수만큼 배열을 확보하고 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
-> 번호 순서대로 "스캔"하면서 빌려줄 관계를 정한다.

알고리즘의 복잡도

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

문제의 해결 - 방법(2)

만약 전체 학생 수가 매우 크다면?
하지만 문제의 성질상 O(n)보다 낮은 복잡도 알고리즘은 어려울 듯

그런데 여벌의 체육복을 가져온 학생은 매우 적다면?

여벌의 체육복을 가져온 학생들의 번호를 정렬하고 이것을 순서대로 살펴보면서
빌려줄 수 있는 다른 학생을 찾아서 처리한다 -> 해시를 적용해서 상수 시간에 처리

알고리즘의 복잡도

여벌의 체육복을 가져온 학생들의 번호를 정렬 -> O(klogk)
체육복을 빌려줄 수 있는 학생을 찾아 처리 -> O(k) * O(1)
전체 알고리즘의 시간 복잡도 -> O(klogk)

#방법 1
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])

#방법 2 set이용
def solution(n, lost, reserve):
	# &은 교집합 
	s = set(lost) & set(reserved)
	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)

정렬 (Sort) 대표 문제 풀이 : 가장 큰 수

문제의 해결 방법

(1) 빈 문자열로 수를 초기화한다.
(2) 가장 크게 만들 수 있는 수를 고른다.
(3) 그 수를 현재 수에 이어 붙인다.
(4) 모든 수를 다 사용할 때까지 반복한다.

(조금 나은) 문제의 해결 방법

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

구현

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

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x : (x * 4)[:4], reverse=True)
    # 0000 같은 경우 0으로 표시
    if numbers[0]=='0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer

-> O(nlogn)

탐욕법 (Greedy) 대표 문제 풀이 : 큰 수 만들기

원칙

• 앞 자리에 큰 수가 오는 것이 전체를 크게 만든다.
  -> 따라서, 큰 것을 우선해서 골라 담고 싶다.

방법

• 앞 자리에서부터 하나씩 골라서 담되, 지금 담으려는 것보다 작은 것들은 도로 뺀다
  단, 뺄 수 있는 수효에 도달할 때까지만
• 큰 수가 앞자리에, 작은 수가 뒷 자리에 놓이도록
  (제약조건) 뺄 수 있는 수의 개수

구현

• 주어진 숫자 (number) 로부터 하나씩 꺼내여 모으되
  • 이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다.
  • 이것은 어디서 어떻게 살펴보아야?
• 이렇게 모든 숫자들을 자릿수 맞추어 반환한다.
  • 아직 뺄 개수 (k)를 채우지 못한 경우
  • 자릿수는 어떻게 계산하는가?

복잡도

• 가장 단순한 방법은 어떤 것일까?
• 우리가 설계한 알고리즘의 복잡도는?
  - O(n)

탐욕법 (Greedy Approach)

• 앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality)에 영향을 주지 않음

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