• TOC {:toc}

이 글은 백준 온라인 저지의 2309번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.04.12

메모리 시간 코드 길이
28776 KB 68 ms 300 B 
from itertools import combinations

d = []

for _ in range(9):
    # 입력한 수를 리스트로 받아서
    d.append(int(input()))

# 모든 원소의 합과 100의 차를 구한다.
e = sum(d) - 100
# 리스트의 원소 쌍을 순회하면서
for c in combinations(d, 2):
    x, y = map(int, list(c))
    # if x == y:
        # continue
    # 두 원소의 합이 위에서 구한 차와 일치하면
    if x + y == e:
        # 리스트에서 제거한다.
        d.remove(x)
        d.remove(y)
        break

d.sort()
# 리스트를 언 패킹(unpacking) 한 뒤 구분자로 줄 바꿈을 넣어서 출력한다.
print(*d, sep="\n")

아이디어 & 풀이

원소 쌍 순회에는 itertools의 combination을 사용했다.

i, j에 각각 반복문을 돌리면 break가 깔끔하게 되지 않아서 combinations를 사용했다.

  • 아래의 풀이 1처럼 break를 하면 j 반복문에서만 벗어나기 때문에 조건을 만족했을 때 반복을 완전히 끝낼 수 없다.
  • 임시 변수를 사용하는 방법 등이 있었지만 깔끔하지 않아서 combination으로 반복문을 한 번만 돌리는 것을 선택했다.
  • 효율성 면에서는 그냥 끝까지 돌리는 게 나을 수도 있을 것 같다.

피드백

  • 리스트 생성 코드를 간결하게 작성하는 습관을 들여야겠다. (e.g., d = [int(input()) for i in range(9)
  • 같은 x와 y가 같을 경우 문제가 발생할 수 있어 if x == y: continue를 넣어줬었는데 combinations는 동일한 값으로 조합을 만들지 않아 굳이 적지 않아도 된다.

참고 답안 1

# 리스트를 생성할 때 먼저 정렬한다.
# 정렬하지 않으면 아래 반복문을 실행할 때 에러가 발생한다.
l = sorted(int(input()) for i in range(9))
for i in l:
    for j in l:
        # 두 원소의 합이 100에서 벗어난 값과 같으면
        if i + j == sum(l) - 100:
            # 그 두 원소를 제거한다.
            l.remove(i)
            l.remove(j)
            break
for i in l:
    print(i)

아이디어 & 풀이

i과 j를 순회할 때 i와 j가 동일한 수를 가리키면 문제가 발생할 수 있다.

문제 페이지에 제시된 입력을 예시로 들어보자.

  • 주어진 입력에서 입력된 수의 총 합과 100의 차는 40이다.
  • 이는 주어진 입력에서 15와 25를 더한 값이기도 하지만 동시에 20을 두 번 더한 값이기도 하다.
  • 주어진 입력에서는 원소를 정렬하지 않으면 20이 가장 먼저 조건을 만족하게 되고 20을 두 번 제거하려하면서 에러가 발생한다.

풀이 1에서 정렬을 하면 문제를 방지할 수 있는 이유는 다음과 같다.

  • 예를 들어 입력된 수의 총 합과 100의 차이를 e라고 해보자
  • a + b == e, c + c == e인 a, b, c가 있을 때(a < b), 이 세 수는 a < c < b를 만족한다.
  • 즉 정렬하면 a, b가 c보다 먼저 조건을 만족해 제거되고 sum(l) 값이 달라지기 때문에 20이 조건을 만족하지 않는다.

하지만 위에서 언급한 것 처럼 break가 반복문을 완전히 벗어나지 않기 때문에 여전히 문제 여지가 남아있다.

  • 만약 sum(l)과 100 차이를 반복문 진입 전에 계산해 sum(l)의 값을 다시 계산하지 않는 경우 20에서 조건을 만족해 동일한 문제가 발생한다.

    l = sorted(int(input()) for i in range(9))

# 차이를 미리 계산
e = sum(l) - 100

for i in l:
    for j in l:
        print(i, j)
        if i + j == e:
            l.remove(i)
            l.remove(j)
            break
for i in l:
    print(i)

  • 남은 원소 중 두 수를 더하거나 자기 자신을 두 번 더했을 때 새로운 sum(l) - 100과 값이 같아지는 원소가 존재할 수 있다.

위와 같은 이유로 애초에 if i == j: continue처럼 두 수가 같은 경우를 필터링 하는 과정이 포함되는 것이 좋을 것 같다.

참고 답안 2

from itertools import combinations

a = [int(input()) for i in range(9)]
# 생성한 리스트의 원소에서 7개의 값을 선택한 조합들의 리스트를 생성한다.
p = list(combinations(a, 7))

# 리스트의 각 원소(7개의 값을 갖는 튜플)에 대해서
for i in p:
    # 일곱 값의 합이 100이면
    if sum(i) == 100:
        # 정렬한 뒤 출력한다.
        print(*sorted(i), sep="\n")
        break