[SWEA] 1486. 장훈이의 높은 선반 (Python3)

문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

---

나의 논리

 

문제를 읽어보면 서론이 구구절절인데, 핵심은 점원 N명의 키를 리스트로 받은 후에 그 키들을 조합해서 높이 B 이상이 되는 경우를 찾으면 되는 문제였다.

 

한 가지 유의할 점은 높이 B 이상인 것이 여러 개일 때는 그 합이 B와 가장 가까운, 즉, 차이가 적은 값을 답으로 한다는 것이다. 예를 들어, 주어진 조건에서 높이 B = 16일 때 점원들의 키를 조합해서 16이 나오면 베스트고, 그 이상이 나오면 B와 가장 가까운 17부터 시작해서 아무튼 가장 가까운 값을 답으로 하면 된다.

 

사진으로 보기

# date: 2020/10/25
# author: psS2mj
# brief: SWEA_1486_장훈이의 높은 선반 (D4)

from itertools import combinations
T = int(input())
for tc in range(1,T+1):
    N, B = map(int,input().split()) # N: 점원의 수, B: 탑의 높이
    height = list(map(int,input().split())) # 점원의 키
    result = list() # 조건을 만족하는 결과값을 저장할 리스트
    # 조합을 이용해 길이가 1 이상인 모든 부분집합 구하기
    for i in range(1,N+1):
        c = list(combinations(height,i))
        # 각 부분집합마다 합을 구해준다.
        for j in c:
            sum = 0
            for k in j:
                sum += k
            # 키의 합이 B 이상일 때만 리스트에 저장
            if sum >= B:
                result.append(sum)
    # 리스트를 정렬한 뒤 첫 번째 원소를 출력한다.
    print("#{} {}".format(tc,sorted(result)[0]-B))

 

나는 문제를 읽고 바로 부분집합이 떠올랐는데, 이왕이면 파이썬에 내장되어 있는 함수를 좀 활용하고 싶어서 조합으로 한 번 풀어봤다. 조합이나 부분집합이나 크게 다르지 않으니까. (아참, 키의 합으로 높이 B를 만들어야 하는 것이기 때문에 0명으로는 불가능하겠지? 그래서 공집합은 포함되지 않는다는 점!!🙄)

 

👩🏻주요 로직은 이런 흐름이다:

1. 가능한 모든 조합을 구해 c라는 리스트에 저장한다. (단, i는 1부터)

2. 각각 조합된 경우마다 합을 구해준다.

3. 만약 그 합이 높이 B 이상이라면 result 리스트에 저장한다. 아닌 애들은 무시하고 넘어가기.

4. 마지막에 result 리스트를 정렬한 후, 첫 번째 원소를 답으로 출력한다. (이때, 해당 값에서 높이 B를 빼주는 로직도 동시에 수행)

 

나름 나쁘지 않은 방법이라고 생각하고 풀었고, 통과는 했다.

통과는 했는데 메모리를 상당히 많이 사용하고, 시간도 좀 더 걸리는 것 같아서 어떤 방법으로 푸는게 좀 더 효율적인걸까,,, 생각을 해봤지만 잘 떠오르지 않는다. 다음 기회에 좀 더 생각해봐야겠다^_^

---

...는 글 쓰자마자 뭔가 떠올라서 고쳐봤는데 바로 메모리와 시간이 절반으로 줄었다.

 

기존 코드에서 딱 하나를 빼봤다.

기존 코드:
c = list(combinations(height,i))

수정 후 코드:
c = combinations(height,i)

기존에는 조합한 결과를 list로 다 받아서 이렇게 저렇게 했었는데, 이걸 꼭 리스트로 다 받은 다음에 해야할까?라는 생각이 들어서 list만 빼봤는데 메모리와 시간 모든 것이 좋아졌다.

결과 비교 (아래: 기존 코드, 위: 수정 후 코드)

근데 문제는 왜 이렇게 큰 차이가 나는지 정확히 이해가 안 된다. 추가로 공부해야겠다.🤔🤨❓

 

지금 이렇게 좋아진 상태에서

print(c)
출력 결과:
<itertools.combinations object at 0x000001F394598180>
<itertools.combinations object at 0x000001F3945984A0>
<itertools.combinations object at 0x000001F394598180>
<itertools.combinations object at 0x000001F3945984A0>
<itertools.combinations object at 0x000001F3945A92C0>

print(type(c))
출력 결과:
<class 'itertools.combinations'>
<class 'itertools.combinations'>
<class 'itertools.combinations'>
<class 'itertools.combinations'>
<class 'itertools.combinations'>

print(list(c))
출력 결과:
[(1,), (3,), (3,), (5,), (6,)]
[(1, 3), (1, 3), (1, 5), (1, 6), (3, 3), (3, 5), (3, 6), (3, 5), (3, 6), (5, 6)]
[(1, 3, 3), (1, 3, 5), (1, 3, 6), (1, 3, 5), (1, 3, 6), (1, 5, 6), (3, 3, 5), (3, 3, 6), (3, 5, 6), (3, 5, 6)]
[(1, 3, 3, 5), (1, 3, 3, 6), (1, 3, 5, 6), (1, 3, 5, 6), (3, 3, 5, 6)]
[(1, 3, 3, 5, 6)]

나중에 공부할 때 도움될 듯해서 각 출력문의 출력 결과를 메모해둔다.