시행착오 기술 블로그

프로그래머스 체육복

여분 체육복 O :  1   3   5

                    X :     2   4 

1번이 2번에게 빌려주고, 3번이 4번에게 빌려준다.

또는

3번이 2번에게 빌려주고, 5번이 4번에게 빌려준다.

위 과정에서 머릿속으로 그린 그림을 절차적으로 기술하는 것이 곧 알고리즘의 핵심이다.

탐욕법: 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택한다. 탐욕스럽게!

[방법1]

학생의 수는 기껏해야 30명. 학생 수만큼 배열을 확보하고, 각자가 가지고 있는 체육복의 수를 기록한다.

그리고 번호 순서대로 스캔하며 빌려줄 관계를 정한다. 시간복잡도는 O(N)

- 단, n이 커지면 시간초과 문제가 발생한다.

- 또한 n배열로 인해 메모리가 매우 많이 필요하고

- n번을 순차탐색해야해서 비효율적이다.

def solution(n, lost, reserve):
	# 모두 1벌씩
    students = [1] * (n + 1) 
    
    # 잃어버린 경우
    for l in lost:
        students[l] -= 1
    
    # 여분 있는 경우
    for r in reserve:
        students[r] += 1
        
    # 앞뒤 확인하며 빌려줄 수 있는 경우 찾기
    for idx, s in enumerate(students):
        if s == 2: # 2벌
            if students[idx - 1] == 0: # 좌 확인
                students[idx - 1] += 1
                students[idx] -= 1
            elif (idx+1 <= n) and students[idx + 1] == 0: # 우 확인
                students[idx + 1] += 1
                students[idx] -= 1
    return len([i for i in students[1:] if i != 0])

[방법2] 

n이 매우 크다면? reserve 학생(K)은 매우 적다면? reserve 정렬 후, 하나하나 살펴보면서 빌려줄 앞, 뒤 학생을 찾는다.

이때 reserve의 길이를 K라고 하면 여벌의 체육복을 가져온 학생들을 정렬하는 데에 O(K * log K) 이다.

K만큼 O(K) 반복하면서 빌려줄 수 있는 다른 학생을 찾아서 처리한다. 해시 사용하면 O(1)만에 처리가 가능하다.

프로그래머스 완주하지 못한 선수

어떤 자료 구조를 택하느냐에 따라 시간복잡도가 달라진다.

(1) 인덱스로 이중 반복문을 이용해 하나씩 비교하는 방법: O(n^2)이 걸린다. => 

(2) 해시는 key를 기준으로 해시 테이블에 저장하는 방법 : 이름-등장횟수(동명이인의 수)를 key-value로 기록.

[방법1] 해시

파이썬에서 해시테이블은 dict()를 이용한다.

1. participant 배열에 있는 참가자들을 dict[key] += 1 이렇게 count를 한다.

2. completion 배열에 있는 완주자들은 dict[key] -= 1 이렇게 빼준다.

3. 그 결과 해시 테이블에는 완주하지 못한 사람은 숫자가 0이 아닐 것이다.

def solution(participant, completion):
    hash = dict()

    for p in participant:
        if p in hash:
            hash[p] += 1
        else:
            hash[p] = 1

    for c in completion:
        hash[c] -= 1

    for h in hash:
        if hash[h] != 0:
            return h

[방법2] 

약간의 아이디어만 떠올리면 가능한 단순 비교

participant 배열과 completion 배열을 각각 정렬해서 일대일 비교하는 과정

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]