문제
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.
문제를 보고 든 생각
음... 이게 보면 볼수록 설명이 되게 거창하다라는 생각이 들었다.
아무리 봐도 그냥 경우의 수를 계산해서 푸는 문제인 것 같은데 제한 사항에서는 이름도 신경쓰고 있고 같은 이름을 가진 의상은 존재하지 않는다는 것도 알려주고 있다.
뭐 물론 내가 제한 사항을 제대로 이해하지 못하고 문제에 적용하지 못했기 때문에 이런 말을 하는 걸 거다.
뭔가 아무튼 경우의 수를 구해주기 위해서 옷의 수끼리 곱해주면 풀릴 것 같았다.
결과
table = {}
cases = 1
for c in clothes:
table[c[1]] = table.get(c[1], 0) + 1
for num in table.values():
cases *= num
if len(table) == 1:
answer = cases
else:
answer = cases + len(clothes)
print(answer)
코드를 적으면서 상당히 불안했고, 테스트 케이스로 2케이스가 있었는데 모두 맞아서 그게 나의 불안감을 더 증폭시켰다.
보통 분명 이 코드가 아닌 것 같다는 생각이 맴도는 와중에 테스트 케이스를 모두 맞는다면, 제출을 하는 순간 오답 처리로 도배가 된다.
그리고 역시 예감은 들어맞았다.
100점 중 28점 정도 맞았다.
위의 코드가 경우의 수를 내뱉는 과정을 단순하게 설명하겠다.
1. len(table)이 1일 때
선택할 수 있는 의상의 종류가 1개이며 그 종류 안에 있는 가짓수가 곧 경우의 수가 된다.
2. len(table)이 1이 아닐 때, 즉 의상의 종류가 2종 이상일 때
의상 종류별 가짓수끼리 곱해주는 것이다.
즉, 선글라스 카테고리에서 선글라스의 가짓수가 2개 있고 모자 카테고리에서 모자의 가짓수가 1개 있다고 해보자.
그럼 cases에는 2 * 1의 결과로 2가 들어가고 len(clothes)는 3이 나오기에 answer에는 5가 저장된다.
이런 식으로 테스트 케이스에서는 정답 처리를 받을 수 있었지만 완전히 정확한 코드는 아니었나 보다.
검색을 통해 알게 된 내용
그래서 결국 검색을 해봤다.
내가 적은 코드는 너무나도 단순하기에 아무래도 복잡한 코드가 나오지 않을까 싶었다.
그런데 검색을 통해 알게 된 건 그냥 내가 경우의 수 계산을 잘못했다는 거였다.
내가 생각했던 방법이 맞았다는 것에 조금 기분이 좋았지만
또 한편으로는 간단한 경우의 수 계산을 틀렸다는 것에 기분이 좋지 않았다.
검색을 통해 알게 된 풀이
table = {}
cases = 1
for c in clothes:
table[c[1]] = table.get(c[1], 0) + 1
for num in table.values():
cases *= num + 1
cases -= 1
print(cases)정답 처리를 받을 수 있는 코드는 내가 작성한 코드보다 더 간단했다.
내가 코드를 쓸 때, 경우의 수를 계산할 때 놓쳤던 부분이 있었다.
그것은 바로 의상의 종류가 있다면 그 의상의 종류를 선택할지 말지도 경우의 수에 포함이 되어야 하는데 그걸 고려하지 않았다.
내가 계산한 경우의 수는 무조건 그 의상의 종류를 선택한다고 가정하고 나서의 경우의 수였던 것이다.
그래서 각 case마다 의상의 가짓수에 1을 더해주어야 한다.
그리고 for문이 다 돌고난 후에 cases에 -1을 해주어야 한다는 걸 보고는 이해가 가지 않았다.
그런데 계속 보다보니 이해가 점차 되기는 했다.
도대체 어떤 경우의 수를 빼주어야 하는지 몰랐는데, 그것은 바로 그 어떤 종류도 선택하지 않을 경우를 빼는 것이었다.
이걸 해주어야 하는 이유는 우리가 for문에서 각 의상의 종류를 선택할지 말지의 경우의 수 +1을 해주었기 때문에
그 어떤 것도 선택하지 않는 경우의 수 1개가 포함이 되게 되는 것이다.
그래서 마지막에 -1을 해주어야 한다.
느낀점
경우의 수를 조금만 더 생각하고 풀었다면 이 문제를 혼자서 해결해낼 수 있었을까?
다음에는 나에 대한 확신을 조금만 가져보는 걸로 하자.
그리고 사실 이 글을 작성하기 전까지도 제대로 이 문제에 대해 이해가 되지 않았었다.
왜 각 의상의 종류를 선택하는 경우의 수에서 1을 더해줘야 하는지, 왜 마지막에 전체 경우에서 1을 빼주어야 하는지 이해가 안 됐다.
그런데 신기하게도 이 글을 작성하는 과정에서 완전히 이해가 됐다.
이것이 블로그를 작성하는 이유 중 하나인가 보다.