[programmers - python] 체육복 (greedy)

첫번째 시도

한문제 맞춤…

    def solution(n, lost, reserve):
        lost_new = sorted(set(lost) - set(reserve),reverse = True)
        reserve_new = sorted(set(reserve) - set(lost),reverse=True)
        given = []
        given_flag = False
        while reserve_new:
            while lost_new:
                lo = lost_new[-1]
                temp = reserve_new[-1]
                if temp - 1 == lo or temp + 1 == lo:
                    given.append(reserve_new.pop())
                    lost_new.pop()
                    given_flag = True
                    break
            if not given_flag:
                reserve_new.pop()
            given_flag = False
        return n - len(lost) + len(given)

테스트 케이스 추가해서 디버깅 시도 1

    def solution(n, lost, reserve):
        intersect = set(lost) & set(reserve)
        lost_new = sorted(set(lost) - intersect,reverse = True)
        reserve_new = sorted(set(reserve) - intersect,reverse=True)
        given = list(intersect)
        given_flag = False
        while reserve_new:
            while lost_new and (lost_new[-1]==reserve_new[-1]-1 or lost_new[-1]==reserve_new[-1]+1):
                # lo = lost_new[-1]
                # temp = reserve_new[-1]
                # if temp - 1 == lo or temp + 1 == lo:
                given.append(reserve_new.pop())
                lost_new.pop()
                given_flag = True
                # break
            if not given_flag:
                reserve_new.pop()
            given_flag = False
        return n - len(lost) + len(given)

50점. 문제 반 맞춤

누군가 친절히 알려준 테스트 케이스 추가하고 문제점 발견

    def solution(n, lost, reserve):
        intersect = set(lost) & set(reserve)
        lost_new = sorted(set(lost) - intersect,reverse = True)
        reserve_new = sorted(set(reserve) - intersect,reverse=True)
        given = list(intersect)
        given_flag = False
        while reserve_new:
            while lost_new and reserve_new and (lost_new.count(reserve_new[-1]-1) > 0 or lost_new.count(reserve_new[-1]+1) > 0):
                given.append(reserve_new.pop())
                lost_new.pop()
                given_flag = True
                    # break
            if not given_flag:
                reserve_new.pop()
            given_flag = False
        return n - len(lost) + len(given)

다 맞춤

# n=24;lost=[12, 13, 16, 17, 19, 20, 21, 22];reserve=[1,22, 16, 18, 9, 10]

원래 코드에선 lost_ = [22,21,20,19,17,16,13,12], reserve_ = [22,18,16,10,9,1] 로 정렬 후 각각 매칭 시켜서 연산했다.

1. 1 → 12 안 맞아? 그럼 1버려 → reserve_ [22,18,16,10,9]
2. 9 → 12 안 맞아? 그럼 9 버려 → reserve_ [22,18,16,10]
3. 10 → 12 안 맞아? 그럼 10 버려 → reserve_ [22,18,16]
4. 16 → 12 안 맞아? 그럼 16 버려 → reserve_ [22,18]
5. 18 → 12 안 맞아? 그럼 18 버려 → reserve_ [22]
6. 22 → 12 안 맞아? 그럼 22 버려 → reserve_ []

• 문제점이 보인다. 각 reserve에서 비교하는 숫자들은 lost에 있는 모든 숫자들과 비교해야하나 매번 하나씩만 비교하고 있다. 이를 해결해줄 방법을 고민했다.
• 누군가 list_object.count(a)를 써서 (a와 일치하는 수를 몇개 가졌는지를 산출해주는 함수) 코드를 작성한 걸 봤고 모방했다. reserve 원소의 +1, -1 한 값의 원소개의 개수를 찾았고 그게 0보다 큰 게 있으면 pop하고 넘어가는 방식으로 작동한다.

1시간 반정도 소요 되었다.