완주하지 못한 선수
1. Problem
2. My Solution
- 입력값이 100,000 이기 때문에 선수가 완주했는지 판단하기 위해서 completion 리스트를 탐색하는 것은 시간초과가 발생, 또한 set 자료구조를 이용하는 것도 참가자중에는 동명이인이 있기 때문에 안됨
- Dict 자료구조를 이용하여 문제 해결
- 이름을 key 로하고 value 는 0부터 1씩 더함 (동명이인 가능성)
- completion 에 등장하는 사람의 value 값을 -1
- 마지막에 value 값이 1인 사람이 완주하지 못한 사람임
def solution(participant, completion):
partDict = dict()
answer = ""
for i in participant:
partDict[i] = partDict.get(i,0) + 1
for i in completion:
partDict[i] -= 1
for i in participant:
if partDict[i] == 1:
answer = i
break
return answer
3. Others' Solutions
- 첫 번째 방법 (collections.Counter 함수 이용)
- counter 함수를 이용하여 각 요소의 개수를 구한뒤에 뺄셈 수행
- 뺄셈 후에도 남아있는 나머지 한개의 요소가 완주하지 못한 사람
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]
// 실제 동작 원리
// Counter({'mislav': 2, 'stanko': 1, 'ana': 1}) - Counter({'stanko': 1, 'ana': 1, 'mislav': 1})- 두 번째 방법 (hash 함수 이용)
- 참가자 목록을 모두 해쉬화해서 누적합 한 뒤에, 완주자 목록 또한 모두 해쉬화해서 뺄셈하면 나머지 하나의 해쉬값만 남게되고 이를 다시 저장해논 dict 에서 찾음
def solution(participant, completion):
answer = ''
temp = 0
dic = {}
for part in participant:
dic[hash(part)] = part
temp += int(hash(part))
for com in completion:
temp -= hash(com)
answer = dic[temp]
return answer
4. Learned
partDict['key']를 사용하여 value 값에 접근할 때, 해당 key 가 존재하지 않을 때 에러를 발생시킴partDict.get('key')를 이용하여 접근한다면 key 가 존재하지 않을 때 None 객체를 반환partDict.get('key',value)을 이용한다면, key 가 없을 때는 value 로 초기화하여 가져옴
- Counter 함수 - dict 자료구조를 이용해서 파라미터의 구성 요소들의 개수를 count하는 함수
print(collections.Counter(["mislav", "stanko", "mislav", "ana"]))
-> 출력 Counter({'mislav': 2, 'stanko': 1, 'ana': 1})- Counter 객체를 이용하여 여러 다양한 작업을 수행할 수 있음
- hash 함수 - 값을 입력받아 정수의 해쉬값을 반환하는 함수
print(hash("test"))
-> 출력 -7926904895098085402- 값이 같은 요소는 해쉬값이 같지만, 해쉬값이 같다고해서 원래의 값이 같은 건 아님 (해쉬충돌 가능성)
N으로 표현
1. Problem
2. My Solution
- dp[i][j] 에서 i = N의 개수, j = N을 i 개 사용하여 만들 수 있는 수
- 뺄셈과 나눗셈은 피연산자의 순서에 따라 결과가 달라지므로 각각 바꿔서 계산
- 문제 해결 방법
1. 5 를 이용해서 만들 수 있는 수
5
2. 5 5 를 이용해서 만들 수 있는 수
5+5 = 10
5-5 = 0
5*5 = 25
5/5 = 1
55
3. 5 5 5 를 이용해서 만들 수 있는 수
(5+5)+5 (5+5)-5 (5+5)*5 (5+5)/5
5+(5+5) 5+(5-5) 5+(5*5) 5+(5/5)
...
...
4. 5 5 5 5 를 이용해서 만들 수 있는 수
1과 3의 조합, 2와 2의 조합
- 이렇게하면 N을 i번 사용해서 만들 수 있는 수는 이전의 수들의 조합으로 만들 수 있음
def cal(n,i,j,dp):
for a in dp[i]:
for b in dp[j]:
try:
dp[n].append(a+b)
dp[n].append(a-b)
dp[n].append(b-a)
dp[n].append(a//b)
dp[n].append(a*b)
dp[n].append(b//a)
except:
pass
def solution(N, number):
dp = [[] for i in range(9)]
dp[1].append(N) # N 1개로 만들 수 있는 수는 N
dp[2].append(N+N)
dp[2].append(N-N)
dp[2].append(N//N)
dp[2].append(N*N)
dp[2].append(int(str(N)*2))
for i in range(1,3): # number를 N 1개, 또는 2개로 만들 수 있다면 -> 1 또는 2
if number in dp[i]:
return i
for i in range(3,9):
dp[i].append(int(str(N)*i)) # N을 i개 붙인 수
for j in range(1, (i//2)+1):
cal(i,j,i-j,dp)
if number in dp[i]: # N i개로 number를 만들 수 있다면 -> i
return i
return -1 # 모든 경우를 돌려도 만들 수 없다면 -> -1
3. Learned
- DP 에서 바로 이전 결과를 사용할 수도 있고, 더 이전의 결과를 사용할 수 도 있고, 이전 결과들을 사용할 수 도 있음
예산
1. Problem
2. My Solution
- 최대한 많은 부서에 물품을 지원하기 위해서는 부서별 신청 금액이 가장 낮은 부서부터 할당해야함 (그리디 알고리즘)
- 일단 해당 부서에게 신청 금액만큼 지원을 했다고 가정했을 때, 가지고 있는 예산을 초과하면 다시 회수
def solution(d, budget):
spend = 0
department = 0
d.sort()
for i in d:
spend += i
department += 1
if spend > budget:
spend -= i
department -= 1
elif spend == budget:
break
return department
3. Others' Solution
- 일단은 모든 부서의 신청금액을 누적합을 구한뒤에 신청금액이 큰 부서부터 제외하면서 가지고 있는 예산보다 작거나 같아지는 순간 종료
def solution(d, budget):
d.sort()
while budget < sum(d):
d.pop()
return len(d)