[프로그래머스] 체육복

기본 아이디어

• for문 여러번 돌리기보다 index로 접근하는 것이 좋겠다.
• 무식하게 해도 될거같은데...?

1. 인덱스 접근

def solution(n, lost, reserve):
    status = [1]*n   # all students
    for a in lost:   # losted students
        status[a-1] -= 1
    for b in reserve:
        status[b-1] += 1

    for i in range(n):
        # 내가 체육복 여벌 있을 때
        if status[i] == 2:
            if i > 0 and status[i-1] == 0:
                status[i] -= 1
                status[i-1] += 1
            elif i < n-1 and status[i+1] == 0:
                status[i] -= 1
                status[i+1] += 1
            else:
                status[i] -= 1

    return sum(status)

• 코드가 드럽지만 확실한건 느릴 이유가 없음
• O(n)

2. 집합 접근

def solution(n, lost, reserve):
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    lost_sorted = sorted(lost_set)
    reserve_sorted = sorted(reserve_set)

    for i in reserve_set:
        if i-1 in lost_set:
            lost_set.remove(i-1)
        elif i+1 in lost_set:
            lost_set.remove(i+1)
    return n - len(lost_set)

• gpt한테 받은 코드
• 처음에 lost_set, reverse_set 으로 양측 중복제거 하고 시작하는거 좋다
• set.remove() 연산은 평균적으로 O(1)임. 내부가 해시테이블로 구현되어있어서 빠름! (dic에서 key접근이 빠른거랑 동일함)
• O(nlogn) 정렬 필요없는 경우는 O(n)