알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 11. 그리디 - Q5. 볼링공 고르기

  • 0
  • 0
0
0

1. 볼링공 고르기

  • 난이도
  • 풀이 시간
    • 30분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128 MB
  • 출처
    • 2019 SW 마에스트로 입학 테스트

A. 문제

A, B 두 사람이 볼링을 치고 있다.
두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.
볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.
볼링공의 무게는 1~M까지의 자연수 형태로 존재한다.

a. 예를 들면.

N = 5, M = 3이며 무게가 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1, 2, 3, 4, 5번으로 부여된다. 이때 두 사람이 고를 수 있는 볼링공의 조합을 구하면, 아래와 같다.

(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)

두 사람이 공을 고를 수 있는 경우의 수는 8가지이다.

b. 입력 조건
  • 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어진다
    • 1 <= N <= 1,000
    • 1 <= M <= 10
  • 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.
    • 1 <= K <= M
c. 출력 조건
  • 첫번째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력하라.
d. 테스트 케이스
  • 입력 예시

    
    5 3
    1 3 2 3 2
    
    
    
    8 5
    1 5 4 3 2 4 5 2
    
    
  • 출력 예시

    
    8
    
    
    
    25
    
    

B. 내 답안

a. 1차 시도 (내가 생각해본 반례에서 틀림)

from itertools import combinations  
  
n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
count_sort = [0] * (m+1)  
result = 0  
  
for i in array:  
    count_sort[i] += 1  
  
for i in range(1, len(count_sort)):  
    if count_sort[i] > 0:  
        count_sort[i] -= 1  
print(count_sort)  
for i in count_sort:  
    if i < 2:  
        result += i  
    else:  
        result *= i  
print(result)  
result = len(list(combinations(array, 2))) - result  
  
print(result)

b. 2차 시도 (통과)

from itertools import combinations  
  
n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
result = 0

combi = list(combinations(array, 2))  
# print(combi)  
  
answer = len(combi)  
  
for i in combi:  
   A, B = i  
   if A == B:  
       answer -= 1  
  
print(answer)

c. 반례

# 반례  

# 5 3  
# 1 1 1 2 3 

# 10 8  
# 1 1 2 3 3 8 4 8 8 2

a. 회고

풀이

  • 조합이라는 단어가 있길래, Combination이 떠올랐다.
  • 하지만, 기존 Combination에서 조건이 하나 더 추가된다.
    • 두 사람이 고른 볼링공의 무게가 같으면 안된다.
  • 즉, N개의 볼링공의 조합을 구한다. -> 구한 조합에서 볼링공의 무게가 같은 경우를 제외한다.
    • list의 pop() 메소드를 사용하려다가, 쓸데없이 시간 복잡도가 증가할 것으로 생각하여, 간단하게 len()을 사용하였다.
      • list메소드의 시간복잡도는 len()은 O(1), pop(i)는 O(N)이다.

반성

  • 단순히 문제에서 예시로 나온 테스트 케이스에 맞추는데 집중했다. 그래서 반례에는 통과하지 못했다.

결론

  • 조금만 더 생각해보자. 이번 문제에서는 추가 조건을 어떻게 해석하느냐에 따라 정답과 오답이 갈리는 문제였다.

C. 문제 해설

제 풀이랑 조금 다른 방식입니다.

무게마다 볼링공이 몇 개 있는지를 계산해야 한다.

  • 무게가 1인 볼링공 : 1개
  • 무게가 2인 볼링공 : 2개
  • 무게가 3인 볼링공 : 2개

A가 특정한 무게의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산하면 문제를 해결할 수 있다.

  1. A가 무게가 1인 공을 선택할 때의 경우의 수
    • 1 (무개가 1인 공의 개수) * 4 (B가 선택하는 경우의 수) = 4가지
  2. A가 무게가 2인 공을 선택할 때의 경우의 수
    • 2 (무개가 2인 공의 개수) * 2 (B가 선택하는 경우의 수) = 4가지
  3. A가 무게가 3인 공을 선택할 때의 경우의 수
    • 2 (무개가 3인 공의 개수) * 0 (B가 선택하는 경우의 수) = 0가지

단계가 진행됨에 따라, 이미 계산했던 경우(조합)는 제외하기 때문에 B가 선택할 수 있는 경우의 수는 줄어든다.
또한 볼링공의 무게가 1부터 10까지만 존재할 수 있기 때문에, 하나의 리스트를 선언하여 각 무게별로 볼링공이 몇 개가 존재하는지 기록할 수 있다.

a. 책 답안

python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.