파이썬을 무기로, 코딩테스트 광탈을 면하자! 정리 (1)

프로그래머스의 파이썬을 무기로, 코딩테스트 광탈을 면하자! 강의 1-4강을 정리한 글입니다.

---

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

문제: 완주하지 못한 선수

• 동명이인이 나올 수 있다 → 이름이 몇 번 나왔는지 알 수 있는 자료구조가 필요
• 문자열로 접근할 수 있는 자료구조: 해시!
• 파이썬에서 해시는 딕셔너리로 구현됨

풀이1: 해시

• 해시로 이름과 등장 횟수를 세고, 다 돌은 후 value가 0이 아닌 key를 리턴한다.
• 복잡도: O(n)

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x,0) + 1 #dictionary에 x가 있으면 그 값을 리턴하고, 없으면 0 리턴하고 1 더함
    for x in completion:
        d[x] -= 1

    dnf = [k for k, v in d.items() if v > 0]

    return dnf[0]

dictionary.get(keyname,value)

• keyname이 있으면 그 Value를 리턴하고, 없으면 value 리턴

dictionary.items()

• (key, value) 쌍을 리스트로 리턴

풀이2: 배열

• 배열을 sort한 후 participant와 completion을 비교하여 다른 값이 나올 때 return
• 복잡도: 정렬로 인하여 O(nlogn)

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            return participant[i]
    return participant[-1]

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

문제: 체육복

• 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 → 그리디
• 체육복을 다 줄 수 있었는데 못 받는 경우를 떠올려 보았을 때, 체육복을 나눠주는 방향에 영향을 받는 것을 알 수 있다.
  • 앞에서부터 주면 작은 숫자에 우선적으로,
  • 뒤에서부터 주면 큰 숫자에 우선적으로 주어야 한다.

풀이1

• 복잡도: O(n)

def solution(n, lost, reserve):
    u = [1] * (n + 2)

    # 학생 별 체육복 수 저장하는 list
    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 + 1] == 0 and u[i] == 2:
            u[i:i + 2] = [1, 1]

    return len([x for x in u[1:-1] if x > 0])

풀이2: 여벌의 체육복을 가져온 학생이 전체 학생 수에 비해 매우 적다면?

• 모든 학생을 다 스캔하는 것은 비효율적일 수 있기 때문에
  • 여벌의 체육복을 가져온 학생들의 번호를 정렬하고, 하나씩 살펴보며 빌려줄 수 있는 학생들이 있는지만 확인한다.
  • 빌려야 하는 학생은 해시로 처리한다.
• 복잡도: O(nlogn)

def solution(n, lost, reserve):
  s = set(lost) & set(reserve) # 전체 학생
  l = set(lost) - s # 빌려야 하는 학생 (0)
  r = set(reserve) - s # 빌려줄 수 있는 학생 (2)
  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)

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

문제: 가장 큰 수

• 단순히 문자열 정렬만으로는 '30'과 '3'을 올바르게 정렬할 수 없다
• numbers 원소가 1000 이하라고 했으니 숫자 하나를 반복한 뒤 네번째 자리까지 비교하면 된다.
  • ex) '3030 | 30' vs '3333| 3'
• 복잡도: 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': # 0만 들어온 경우
      return '0'
    answer = "".join(numbers)
    return answer

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

문제: 큰 수 만들기

• 앞 자리부터 하나씩 스택에 숫자를 넣다가 지금 담으려는 수보다 작은 것들은 도로 뺀다.
  • 단, 뺄 수 있는 수효에 도달할 때까지만
• 복잡도: 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# 아직 k가 남아있다면 마지막 빼기
    answer =  "".join(collected)
    return answer