Lv.1 체육복

코딩테스트 연습 - 체육복 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

이번 문제는 Greedy Algorithm 문제이다.

문자 그대로, 큰 그림보다는 순간 순간에 최선의 값을 만들 수 있게끔 결과를 내야 한다.

 

사실 크나큰 어려움은 없을 것이라고 생각했는데

아래 오류 코드를 확인하고 당황했다.

#오류 코드

def solution(n, lost, reserve):
    lost.sort() # 배열 정렬 후
    reserve.sort()
    
    for i in lost: # 여벌 옷이 있는 학생이 도난당한 경우
        if i in reserve:
            lost.remove(i)
            reserve.remove(i)
    for a in lost: # 여벌 옷이 없는 학생이 도난당한 경우
        if a-1 in reserve: # 바로 앞 번호부터 확인
            lost.remove(a)
            reserve.remove(a-1)
        elif a+1 in reserve: # 없을 시 뒷 번호 확인
            lost.remove(a)
            reserve.remove(a+1)

    return n - len(lost)

왜 그런가? 싶어서 팀원에게 물어봤는데,

for 문에 그대로 이어져 있는 lost와 reserve 배열의 한 인덱스씩 remove할 시에는

순서대로 진행하는 for 문의 인덱스가 꼬이게 된다.

 

ex) for a in lost에서 lost[4]를 제거할 시, 다음 a는 lost[5]가 되어야 하는데,

lost[4]가 제거되었으므로 제거 전 lost[6]이 한 칸 앞당겨지면서 lost[5]가 된다.

>> lost[4] 다음에 lost[6]을 조사하게 되면서 인덱스를 건너뛰게 된다. 오류 발생!

# 정답 코드

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()
    
    for i in lost[:]:
        if i in reserve:
            lost.remove(i)
            reserve.remove(i)
    for a in lost[:]:
        if a-1 in reserve:
            lost.remove(a)
            reserve.remove(a-1)
        elif a+1 in reserve:
            lost.remove(a)
            reserve.remove(a+1)

    return n - len(lost)

이를 위해 [:]를 사용하면서 리스트를 복사해준다.

원본이 아닌 사본 리스트를 만들어줌으로써 원본에는 영향을 미치지 않는다.

---

# 다른 사람의 코드

def solution(n, lost, reserve):

    reserve = set(reserve)

    for size in [0, 1, -2]:
        lost = set(map(lambda x : x+size, lost))
        # map 함수를 사용하여 lost 리스트의 각 항목을 x+size로 변환함.
        # 이렇게 함으로써 lost 리스트의 항목에 size만큼을 더하거나 뺌. 이 과정에서 중복된 값들이 생길 수 있음.
        reserve, lost = reserve - lost, lost - reserve
        # 각 집합에서 겹치는 부분을 제거

    return n - len(lost)

이 코드는 얻어갈 것이 많아서 너무 달았다.

for size in [0, 1, -2]:

# 리스트를 통해 사용한 것으로, 본래 lost 배열을 그대로 둠.  [0]
# lost 배열의 값들을 전부 +1 함 >> lost +1 = reserve     [1]
# lost 배열의 값들을 전부 -2 함 >> lost +1 -2 = reserve  [-2]

lost = set(map(lambda x : x+size, lost))

# 'x+size'에 있는 size 위 for 문에 있기 때문에
# for 문에 있는 리스트 값을 그대로 넣을 수가 있다..
# 리스트도 for 문으로 돌릴 수 있다는 말도 안 되는 응용력..

reserve, lost = reserve - lost, lost - reserve

# +0, +1, -2 하는 과정에서 같은 숫자들을 모조리 제거해버리기
# 완벽한 그리디 형식이다.. 이걸 보니 확실히 그리디 냄새가 나는 걸 느낌