23.04.04 TIL
오늘 한 것
1. 삼총사
문제 이해
이 문제는 조합(combination)을 이용해서 풀어야 하는 문제이다. 모든 경우의 조합을 만든 뒤 조건에 맞는(갯수 3, 총합이 0) 조합의 갯수를 반환하면 된다.
시도 1. 모듈 사용
from itertools import combinations
def solution(number):
cnt = 0
for i in combinations(number,3):
if sum(i) == 0:
cnt += 1
return cntitertools 모듈의 combination을 이용하여 쉽게 해결 할 수 있다. 그러나 이런 풀이는 모듈을 사용할 수 없을 경우에는 소용이 없다고 생각했다.
시도 2. for문 사용
조합은 순서에 상관없이 주어진 리스트에서 정해진 갯수만큼 요소를 뽑는 것을 말하므로 반복문을 통해 O(n^r)(r: 뽑아야하는 갯수)안에 문제를 해결할 수 있다.
def solution(number):
cnt=0
for i,x in enumerate(number[:-2]): # i 뽑기
for j,y in enumerate(number[i+1:],i+1): # j 뽑기
for k,z in enumerate(number[j+1:],j+1): # k 뽑기
print(i,j,k)
if x+y+z == 0:
cnt +=1
return cnt시도 3. 트리 탐색(DFS)
number의 각 요소 마다 선택 하느냐 마느냐의 2가지 선택지가 있고, 순서에 상관없이 3개만 뽑으면 되므로 트리 형태의 그래프로 나타내어 재귀적으로 탐색할 수 있다.
def solution(number: list) -> int:
def dfs(number, state, answer): # 재귀 함수
print(state)
if (not sum(state)) and len(state) == 3: # 뽑은개 3개이고, 총합이 0일때
answer.append(1) # +1
return
if len(state) == 3: # 뽑은게 3개 되면 돌아가기
return
if not number: # 더이상 뽑을게 없으면 돌아가기
return
num = number.pop()
dfs(number[:], state[:]+[num], answer) # 뽑았음을 선택
if len(number) < 3-len(state): # 너무 적게 뽑았으면 안뽑는건 안하기
return
dfs(number[:], state[:], answer) # 안 뽑았음을 선택
answer = []
a = []
dfs(number, a, answer)
count = len(answer)
return count해결: 어느것이 더 나은가?
트리 탐색이 O(2^n)이고, 반복문은 O(n^r)의 시간복잡도를 가진다. 따라서 n이 10보다 크면 반복문을 사용하는 것이 낫다. 제한사항은 입력크기가 50까지 있으므로 n^3이 더 빠르다.
2. 키패드누르기(링크)
문제 이해
입력된 숫자 리스트를 보고 어느 쪽 엄지손가락을 움직여야 할지 정해야한다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용
- 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용
이 문제는 이전에 한번 풀었던 적이 있는 문제였다. 예전 코드와 예전 코드를 버리고 바닥부터 다시 짠 코드를 비교해보기로 했다.
풀이 1(old)
def solution(numbers, hand):
answer = ''
num_pos=[((X-1)%3,3-((X-1)//3)) for X in range(0,10)] # 각 숫자의 위치를 2차원 좌표로 리스트에 저장
num_pos[0]=(1,0)
l_ptr=(0,0)
r_ptr=(2,0)
for num in numbers:
if num in [1,4,7]:
answer=answer+'L'
l_ptr=num_pos[num]
if num in [3,6,9]:
answer=answer+'R'
r_ptr=num_pos[num]
if num in [2,5,8,0]: # 가운데 부분을 누를 때
comp=abs(l_ptr[0]-num_pos[num][0])+abs(l_ptr[1]-num_pos[num][1]) - abs(r_ptr[0]-num_pos[num][0])-abs(r_ptr[1]-num_pos[num][1]) # 미리 정해둔 pos좌표에 따라 거리 계산후 비교
if comp >0 or (comp==0 and hand=='right'):
answer=answer+'R'
r_ptr=num_pos[num]
else:
answer=answer+'L'
l_ptr=num_pos[num]
return answer예전 방식은 각 숫자가 키패드에서 위치한 지점을 2차원 공간좌표 형태로 리스트에 저장하여서 사용하였다. 이것보다 더 깔끔하게 표현할 수 있는 방법을 고민해보았다.
풀이2(new):
def dist(x,y): # 두 키패드 위 숫자간 거리 계산
return abs(x%3-y%3)+abs(x//3-y//3)
def solution(numbers, hand):
# 1-> 0,2->1,3->2...,9->8,0 -> 10
new_numbers=[(i-1)%11 for i in numbers] # 계산을 용이하게 하기 위한 숫자변환
h={'left':(-0.5,0),'right':(0,-0.5)}
l_pos=9
r_pos=11
answer=''
for num in new_numbers:
if num%3==0:
l_pos=num
answer +='L'
continue
if num%3==2:
r_pos=num
answer +='R'
continue
if dist(l_pos,num)+h[hand][0] > dist(r_pos,num)+h[hand][1]:
r_pos=num
answer +='R'
else:
l_pos=num
answer +='L'
return answer키패드를 관찰한 결과, 각 키패드의 숫자가 1 씩 감소하고 0은 10, *과 #은 각각 9, 11을 의미하도록 하면 2차원 배열로 나태내어 맨하탄거리를 계산하기 편해짐을 파악하였다. 따라서 n%11을 통해 numbers의 숫자들을 모두 이에맞게 변환하였다.
이하 진행방식은 오른손잡이/왼손잡이로 인한 선택변화를 딕셔너리와 실수값을 이용해 구현한 것 빼고 거의 동일하다.
3. 성격유형(링크)
문제 이해
survey와 choices를 받는다. survey에는 각 문항이 mbti의 어떤 항목에 대한 것인지 정하고, choices는 문항에 대한 설문자의 실제 선택을 저장하고 있다. 선택된 점수는 0~7점이 있고 높을 수록 문항의 뒷쪽 속성의 점수가 높은것이다.
시도 1. 딕셔너리 이용 1
def solution(survey, choices):
mbti_d={'R':0,'C':0,'J':0,'A':0,'T':0,'F':0,'M':0,'N':0,}
choices_=[i-4 for i in choices] # 기준점 옮기기 4->0
answer = ''각 성향 별로 키-카운트 쌍을 딕셔너리로 저장한다.
for i,s in enumerate(survey):
if choices_[i]<0: # choice가 음수면
mbti_d[s[0]] -=choices_[i] #앞쪽 성향 가산
else: # 양수거나 0 이면
mbti_d[s[1]] +=abs(choices_[i]) # 뒷쪽 성향 가산
key_list=list(mbti_d.keys())
for i in range(4): # 점수 총합으로 성향 결정
if mbti_d[key_list[i]] >= mbti_d[key_list[i+4]]: # 같으면('==') 앞쪽 우선
answer +=key_list[i]
else:
answer +=key_list[i+4]
return answer문제는 해결 했지만, 딕셔너리의 키를 4개로 줄여서 더 일반화된 풀이를 적용 할 수 있을 것 같았다.
해결. 딕셔녀리 이용 2
def solution(survey, choices):
my_dict = {"RT":0,"CF":0,"JM":0,"AN":0} # 각 반대 성향별로 묶어 점수를 집계
for i,s in enumerate(survey):
if s not in my_dict.keys(): # 반대방향
s = s[::-1] # 뒤집기
my_dict[s] -= choices[i]-4
# 양수면 R,C,J,M 성향 증가
else:
my_dict[s] += choices[i]-4
# 양수면 T,F,M,N 성향 증가
result = ""
for key_ in my_dict.keys():
if my_dict[key_] > 0:
result += key_[1]
else:
result += key_[0]
return result반대 되는 성향 끼리 묶어 점수의 총합을 음수/양수로 나뉘게 하였다. 0 인 경우엔 사전순으로 앞쪽에 오는 앞쪽 성향을 선택한다.
dictionary methods
페어프로그래밍을 하던 중 팀원으로부터 .setdefault(key,value)메소드를 알게되었다. dictionary에 알지 못했던 유용한 메소드들이 있음을 파악하고 몇가지 찾아보았다.
1. clear()
clear는 말 그대로 딕셔너리 안의 모든 키-밸류 쌍을 없애버린다. 딕셔너리 자체는 빈 딕셔너리로 남는다.
a={1:1}
a.clear()
# a == None
a[0]=1
# a=={0:1}2. copy()
딕셔너리 안의 요소들을 deep copy해 반환한다.
a={1:1}
b=a
c=a.copy()
a[1]=0
# a,b =={1:0}
# c=={1:1}3. fromkeys(iterable한 변수)
list나 tuple 등에 저장된 것들을 key로서 사용하여 새로운 딕셔너리를 생성한다.
a={1:1}
b=a.fromkeys([0,2,3])
c=dict.fromkeys([0,2,3])
# a=={1:1}
# b=={0:None, 2:None, 3:None}
# c=={0:None, 2:None, 3:None}4. get(key,기본값)
딕셔너리에 해당 키가 있으면 쌍을 이루는 밸류를 반환하고 없으면 기본값(기본 None)을 반환한다.
5. pop(key,기본값)
딕셔너리에 해당 키가 있으면 해당 키-밸류 쌍을 딕셔너리에서 제거하고, 벨류를 반환한다.
기본값을 지정하지 않을 경우 키가 없으면 오류를 발생시킨다. 기본값을 지정하면 오류없이 기본값을 반환한다.
6. popitem()
딕셔너리에 가장 마지막에 추가된 키-밸류 쌍을 딕셔너리에서 제거하고(LIFO), 키-밸류 쌍(튜플)을 반환한다.
7. setdefault(key,기본값)
딕셔너리에 key에 해당하는 키가 없으면 키-기본값 쌍을 추가하고 기본값을 반환한다(기본 None).
이미 있는 키 이면 딕셔너리에는 변화를 주지 않고 해당 키의 쌍이 되는 밸류값을 반환한다.
def solution(array):
count={}
for num in array:
if num in count:
count[num] +=1
else:
count[num]=1위와깉이 if문을 써야하는 코드를 다음과 같이 바꿀 수 있다.
def solution(array):
count={}
for num in array:
count.setdefault(num,0)
count[num]+=18. update(다른 딕셔너리/키-밸류쌍 형태의 요소를 가진 튜플이나 리스트 등)
다른 딕셔너리나 리스트 등을 이용해 딕셔너리 자신의 데이터를 갱신한다. 즉 중복된 키값이 있으면 값을 갱신하고 없으면 새로 키를 만들어 밸류를 지정한다.
a = {1: 1, 2: 2, 0: 0, 8: 8}
print(a.update([[8, 20], [30, 30]]), a) # {1: 1, 2: 2, 0: 0, 8: 20, 30: 30}
a = {1: 1, 2: 2, 0: 0, 8: 8}
print(a.update( ((8, 20), (30, 30)) ), a) # {1: 1, 2: 2, 0: 0, 8: 20, 30: 30}
a = {1: 1, 2: 2, 0: 0, 8: 8}
print(a.update({8:20,30:30}), a) # {1: 1, 2: 2, 0: 0, 8: 20, 30: 30}배운점
- 조합 문제를 트리 탐색(깊이 우선 탐색)로 접근할 수 있다.
- 조합문제는 모듈을 쓰지 않으면 주어진 조건(뽑는 개수와 입력크기 범위)에 따라 적절한 알고리즘을 선택해야한다.
- 같은 알고리즘도 표현방법을 달리함에 따라 더 깔끔하거나 효율적으로 작성할 수 있다.
- 딕셔너리의 다양한 메서드들을 활용할 수 있다.
레퍼런스
python docs
[파이썬] dict.fromkeys() 딕셔너리 생성 메소드 정리
Python Dictionary update()
[파이썬] 사전의 기본값 처리 (dict.setdefault / collections.defaultdict)