[TIL Day3] 파이썬을 무기로, 코딩테스트 광탈을 면하자! (1)

유형별 코딩 테스트 대표 문제

1. 해시(Hash)

완주하지 못한 선수

문제에서 선수의 이름이 주어졌다 -> 문자열로 접근할 수 있는 좋은 자료구조는 무엇일까?

• 사전 자료형
  - 파이썬의 사전 자료형은 원소들을 해시를 이용해 O(1) 시간에 접근 가능하다.
  

def solution(participant, completion):
    d = {}
    for x in participant:
        # d.get(x, 0) -> d에 키 x가 있으면 그 value를 반환, 없으면 0을 반환
        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]
    return dnf[0]
    
# 시간 복잡도: O(N)

2. 탐욕법(Greedy)

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

1) 체육복

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

• 해결 방법 1
  - 학생의 수가 최대 30명이므로
  • 학생 수만큼 배열을 확보하고 여기에 각자 가지고 있는 체육복의 수를 기록한다.
  • 앞에서부터 번호 순서대로 스캔하면서 빌려줄 관계를 정한다.
  • 시간 복잡도는 O(N)

# 배열을 이용하여 풀자
def solution(n, lost, reserve):
    # 앞, 뒷번호를 검사할 때 편하게 배열의 길이를 n + 2로 하자
    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([i for i in u[1:-1] if i > 0])

• 해결 방법 2
  - 학생 수가 매우 많고, 여벌의 체육복을 가져온 학생은 매우 적다면(k) 위 방법은 굉장히 비효율적
  • 여벌의 체육복을 가져온 학생들의 번호(reserve)를 '정렬'(복잡도는 O(klogk))하고
  • 이것을 하나 하나 순서대로 살펴보면서 빌려줄 수 있는 다른 학생을 찾아서 처리한다. -> 해시를 적용해서 상수 시간에 처리!
  • 시간 복잡도는 O(klogk)

# 정렬+해시를 이용하여 풀자
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)

2) 큰 수 만들기

• 원칙
  - 앞 자리에 큰 수가 오는 것이 전체를 크게 만드므로, 큰 것을 우선해서 골라 담고 싶다.
  - '앞쪽'에 있는 작은 수를 뺀다.

• 해결 방법
  - 주어진 숫자 number의 앞 자리에서부터 하나씩 골라서 담되,
  - 이미 모아둔 것 중 지금 담으려는 것 보다 작은 것들은 도로 뺀다.
  - 단, 뺄 수 있는 수효에 도달할 때까지만!
  - 이렇게 모은 숫자들을 자릿수 맞추어 반환한다.
  - 이미 숫자가 정렬된 상태여서 뺄 개수 (k)를 채우지 못한 경우를 고려하자.
  - 시간 복잡도는 O(N)

def solution(number, k):
    collected = []
    # 남아있는 수를 이어 붙이기 위해 i를 이용하자
    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
    return ''.join(collected)

3. 정렬(Sort)

가장 큰 수

• 해결 방법
  1. 빈 문자열로 수를 초기화한다.
  2. 수의 목록을 '크게 만드는 것 우선으로' 정렬(sort()의 복잡도 NlogN)한다.
  3. 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
  4. 모든 수를 다 사용할 때까지 반복한다.
• '크게 만드는 수'의 기준
  - 앞자리가 같고, 길이가 다른 수 비교
  - 문제에서 각 최대 자릿수가 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':
        return '0'
    else:
        return ''.join(numbers)