체육복

문제 정보: https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3

[Python/문제풀이]

내 솔루션:

def solution(n, lost, reserve):
    
    entire = [1 for i in range(n + 2)]
    
    for r in reserve:
        entire[r] += 1        
    for l in lost:
        entire[l] -= 1
    
    for i in range(1, len(entire)):
        if entire[i] > 1 and entire[i - 1] == 0:
            entire[i - 1] += 1
            entire[i] -= 1
        elif entire[i] > 1 and entire[i + 1] == 0:
            entire[i + 1] += 1
            entire[i] -= 1
    count = n
    for e in entire:
        if e == 0:
            count -= 1                    
    return count

선생님 솔루션 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 + 1] == 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으로 푼다. 이 자료가 있는지 없는지만 w/o 키-값

Runtime - O(klogk)
문제에서 n이 너무 크고 lost, reserve는작을때는
이방법이 좋다.

def solutoin(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)