문제를 이해하면서, 파이썬의 딕셔너리 개념을 사용해야 한다고 생각했다.
딕셔너리는 기본적으로 중괄호({}) 를 사용해서 데이터를 묶는 형태를 띄며, 키(key)와 밸류(value)가 하나의 아이템(item)을 구성하게 된다. 즉, 딕셔너리에는 특정한 key값과 value 값이 서로 짝지어서 저장된다고 이해하면 편하다.(해쉬처럼 말이다.)
파이썬을 공부하면서 문제를 풀다 보니, 딕셔너리를 어떻게 사용해야 할지 감이 잘 안 왔다.
처음에 풀었던 코드는 아래와 같았다. (런타임 오류가 났었던 코드)
testcase = int(input())
for test in range(testcase):
n = int(input())
clothes = {} # clothes 라는 빈 딕셔너리 생성
for i in range(n):
name, category = input().split() # 'name'은 옷 이름 , 'category'는 옷 종류
# 'name'이라는 key 값에 'category' 라는 'value' 값 저장
clothes[name] = category
# 우선 clothes 라는 딕셔너리를 value 값 기준으로 정렬
clothes_sorted = sorted(clothes.items(), key=lambda x: x[1])
current_value = clothes_sorted[0][1] # 현재 value 값은 우선 첫 번째 value로 설정
cnt = 0 # 옷 종류를 저장하기 위한 변수를 초기화
count_list = [] # 각기 다른 옷 종류가 몇개씩 있는지 알아보기 위한 리스트 생성
for key, value in clothes_sorted: # 정렬된 clothes 딕셔너리를 반복문을 통해 탐색
if(value == current_value): # 현재 value 값(옷 종류)과 같다면
cnt += 1 # cnt 1 증가
continue
else: # 다른 value 값(옷 종류)을 만났다면
count_list.append(cnt) # 해당 cnt 를 count_list 에 넣고
cnt = 0 # cnt 는 다시 0으로 초기화(새로운 옷 종류 이므로)
current_value = value # 현재 value를 해당 value로 저장하고
cnt += 1 # 다시 cnt 를 1 증가
# for문이 끝나고 나오면 마지막 value 값의 개수를 저장한 cnt를 마저 count_list 에 저장
count_list.append(cnt)
answer = 1
for c in count_list:
answer *= (c+1) # (각 옷의 수+1) 한 것을 곱해줌
# 전체 가능한 조합 수는
# (종류별 옷의 수) + 1을 전부 곱해주고 (해당 종류의 옷을 안 입는 경우의 수를 포함한 것)
# 알몸의 경우의 수인 1만 빼주면 된다.
print(answer-1) # 전체 가능한 패션조합은 전체 조합횟수에서 알몸인 수 1 만 빼면 된다.
여기서 맨 처음에 어차피 옷 종류(category)를 기준으로 옷 이름(name) 이 다른것이니까
key 값과 value 값을 바꿔서 저장하면 안되나 생각해서 아래 코드와 같이
key와 value 값을 뒤바꿔서 저장하는 새로운 딕셔너리를 생성해보았다.
>>> reverse_clothes = dict(map(reversed,clothes.items()))
# key와 value 값을 뒤바꿔서 저장하는 새로운 딕셔너리를 생성하지만, 파이썬 dictionary(딕셔너리)의 특징에 따라 그럴 수 없었다.
( 더보기 를 클릭하면 딕셔너리 특징을 알 수 있다.)
1. 값이 입력한 순서와 상관없이 무작위로 저장된다. 따라서 인덱스 접근이 불가능하다.
2. 데이터에 접근할 땐 key값을 사용하여 접근한다.
3. 저장된 key값은 변경이 불가능하고 같은 이름의 key값을 가질 수 없다.
중복 key값이 들어오면 기존 값이 삭제된다.
4. 저장된 value값은 수정이 가능하고, value값들은 중복된 값이 있더라도 상관없다.
3번 조건에 따라, key와 value를 바꿔버리게 된다면, category(옷 종류)에 따른 name(옷 이름)이 1개씩만 저장될 수 밖에 없었다. 즉, key와 value를 서로 바꿔서 저장하는 방식은 clothes 라는 딕셔너리 자체를 변형시키는 방법이라 옳지 않은 접근 방법이었다.
그럼, value값을 기준으로 key 값이 몇개인지 알면 되는 것 아닌가 싶었다.
get()함수나 in 함수 등등은 결국 key 값을 이용해서 알아내는 방법이고 value 값을 기준으로 개수를 파악하려면
어떻게 해야 할까 고민을 했다.
어차피, 어떤 종류의 옷들이 몇개씩 있는지 알아야 계산이 가능한 문제였다. 즉, 옷 이름은 중요하지 않았다.
for문을 통해 딕셔너리를 탐색하면서 찾는 방법이 있었는데,
(우리는 사용자가 category를 입력하기 전까지는 해당 딕셔너리에 어떠한 category 가 있는지 모르기 때문에)
결국 value가 무엇인지 알아야 가능한 문제였고, 그렇다면 정렬이라는 것이 선수되어야 하고 value 값을 기준으로 정렬을 하되, value(옷 종류)가 바뀔 때마다 리스트에 그에 따른 옷의 개수를 저장하는 방법을 고려해 볼 필요가 있었다.
파이썬 딕셔너리를 정렬하는 것에는 sorted() 가 있는데, 이는 key 값을 기준으로 정렬해 주는 것이고,
value 값을 기준으로 정렬해주려면 lambda(람다)식을 이용해야 했다.
>>> sorted(clothes, key= lambda x : dict[x])
# value값을 기준으로 정렬한 key 리스트를 반환해 준다.
# 내림차순은 reverse = True라는 옵션을 뒤에 붙여주면 된다.
우리는, key 리스트를 반환해주는 것도 아니라 애초에 딕셔너리를 value 값을 기준으로 정렬하고 싶은거니까
items()를 이용한 정렬 방법이 필요했다.
>>> sorted(d.items(), key=lambda x : x[1])
# key 값을 오름차순 하고 싶다면 sorted(d.items(), key=lambda x : x[0])으로 하면 된다.- 딕셔너리에 items() 메서드를 사용해주면 {"key" : value}의 형태를 [(key, value)]의 형태로 만들어 준다. (리스트 안에 튜플)
- 이를 sorted해주면 key값을 기준으로 오름차순으로 정렬해준다. value값으로 정렬하려면 lambda를 사용해주면 된다.
- 정렬된 list값을 dictionary로 바꿔주려면 dict()메서드를 마지막에 써주면 된다.
다시 코드리뷰로 돌아와서,
for문을 돌기 전 일단 current_value 값을 딕셔너리의 첫 key-value 쌍의 value 값을 가리키도록 하고
current_value 값이 해당 value 값과 같다면 cnt를 증가시켜주고
그렇지 않다면(다른 종류의 옷(value)을 만났다면), 여태까지 쌓였던 cnt는 count_list에 추가시켜주고
다시 cnt를 갱신하면서 current_value 값도 업데이트 해준다.
그렇게, 최종으로 만들어진 count_list 는
어떤 종류(category)의 옷이 몇 개씩 있는지 나타내는 리스트를 뜻하게 된다.
예를 들어 count_list = [3,2,1,1,2] 라고 하면
옷 종류는 5개이고, 각 종류에 속하는 각기 다른 옷들이 3벌, 2벌, 1벌, 1벌, 2벌 이렇게 있는것이다.
# 전체 가능한 조합 수는
# (종류별 옷의 수) + 1을 전부 곱해주고 (해당 종류의 옷을 안 입는 경우의 수를 포함한 것)
# 알몸의 경우의 수인 1만 빼주면 된다.
예전 수학을 배웠을 때를 생각하면 공식이 바로 보이는 문제였다. 이 규칙을 여집합 형태로 생각 안하고 주먹구구로 계산하려고 하니 고생을 꽤나 했다,,ㅎ
문제는 잘 풀렸는데, 위의 코드는 런타임오류(IndexError) 가 났다.
(이건, 시간 나는대로 다시 어디가 틀렸는지 살펴볼 문제이다.)
문제가 어디인지 찾았다!!(수정)
문제에
- 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
라고 나와있다.
즉, 의상수가 0일때 인덱스 에러가 나온 것이다! :)
0이 입력되었을때를 처리해줘서 코드를 완성할 수 있었다.
(결국 최종코드는 아래와 같다.-1)
testcase = int(input())
for test in range(testcase):
n = int(input())
clothes = {} # clothes 라는 빈 딕셔너리 생성
if n == 0:
print(0)
else:
for i in range(n):
name, category = input().split() # 'name'은 옷 이름 , 'category'는 옷 종류
# 'name'이라는 key 값에 'category' 라는 'value' 값 저장
clothes[name] = category
# 우선 clothes 라는 딕셔너리를 value 값 기준으로 정렬
clothes_sorted = sorted(clothes.items(), key=lambda x: x[1])
current_value = clothes_sorted[0][1] # 현재 value 값은 우선 첫 번째 value로 설정
cnt = 0 # 옷 종류를 저장하기 위한 변수를 초기화
count_list = [] # 각기 다른 옷 종류가 몇개씩 있는지 알아보기 위한 리스트 생성
for key, value in clothes_sorted: # 정렬된 clothes 딕셔너리를 반복문을 통해 탐색
if(value == current_value): # 현재 value 값(옷 종류)과 같다면
cnt += 1 # cnt 1 증가
continue
else: # 다른 value 값(옷 종류)을 만났다면
count_list.append(cnt) # 해당 cnt 를 count_list 에 넣고
cnt = 0 # cnt 는 다시 0으로 초기화(새로운 옷 종류 이므로)
current_value = value # 현재 value를 해당 value로 저장하고
cnt += 1 # 다시 cnt 를 1 증가
# for문이 끝나고 나오면 마지막 value 값의 개수를 저장한 cnt를 마저 count_list 에 저장
count_list.append(cnt)
answer = 1
for c in count_list:
answer *= (c+1) # (각 옷의 수+1) 한 것을 곱해줌
print(answer-1) # 전체 가능한 패션조합은 전체 조합횟수에서 알몸인 수 1 만 빼면 된다.
(결국 최종코드는 아래와 같다.-2)
애초에 옷이름(name)과 옷 종류(category)를 사용자가 입력할 때, 옷 이름은 중요한게 아니니까,
'name' 이라는 key 값에 'category'라는 value 값을 저장 하는 것이 아니고 (X)
'category' 라는 key 값에 '서로 다른 옷 개수'라는 value 값을 저장하면 된다. (O)
{} 빈 딕셔너리에서
사용자가 입력하고 바로 해당 category가 딕셔너리에 포함되어 있는지,
있다면 해당 category의 value 값을 1 증가
없다면 해당 category의 value 값을 새로 추가
해서 마지막으로 for문을 돌면서 key 값으로 value값을 찾은후 +1 을 한 값을 다 곱해준 것에서
-1 만 해주면 답이 나온다.
testcase = int(input())
for test in range(testcase):
n = int(input())
clothes = {} # clothes 라는 빈 딕셔너리 생성
for i in range(n):
name, category = input().split() # 'name'은 옷 이름 , 'category'는 옷 종류
# 'name'이라는 key 값에 'category' 라는 'value' 값 저장
# clothes[name] = category
if(category in clothes):
clothes[category] += 1
else:
clothes[category] = 1
case = 1
for key in clothes.keys():
case *= (clothes[key]+1)
print(case-1)결국, value 값을 기준으로 개수를 세는 것이 관건이었는데,
간단하게 문제에 필요한 옷의 개수를 key값으로 설정하면 됐었던 문제였다.
(단, 사용자에게 입력받을 때마다 바로바로 조건을 파악해야 하는 것이 주의사항!)
이 문제는 딕셔너리 lambda 함수 혹은 zip함수 등을 다시 살펴볼 수 있는 기회가 있었던 좋은 문제였다.
'컴퓨터 공부 > 📚 Baekjoon(백준)' 카테고리의 다른 글
| [백준/알고리즘/python/java] 2004번 - 조합 0의 개수 (0) | 2021.02.12 |
|---|---|
| [백준/알고리즘/python/java] 1676번 - 팩토리얼 0 의 개수 (0) | 2021.02.11 |
| [백준/알고리즘/python/java] 13305번 - 주유소 (0) | 2021.02.09 |
| [백준/알고리즘/python/java] 11399번 - ATM (0) | 2021.02.02 |
| [백준/알고리즘/python/java] 11047번 - 동전 0 (0) | 2021.02.02 |