선택하는 데이터 구조에 따라 적용 가능한 알고리즘이 달라집니다.
1. 완주할 수 없었던 선수(Hash)
Hash의 특징을 살펴 보겠습니다.
- 이름 대신 번호가 주어지면? → 선형 배열(인덱스에서 일부 요소에 액세스할 수 있습니다.
) - 배열의 인덱스가 아닌 문자열로 액세스 할 수있는 좋은 데이터 구조는 무엇입니까? → Hash!
!
! - 캐릭터 라인을 key 로 보고 hash table 에 mapping 시킬 수가 있는 데이터 구조.
- 각 키 값은 hash function에서 mapping 가능.
- 해시 버킷이 많을수록 다른 버킷에 대해 생각할 가능성이 높아집니다.
- 같은 버킷에 들어가면 충돌이 일어난다.
파이썬 사전를 생각해 볼 수 있다.
사전을 구현할 때 내부적으로 해시 테이블을 사용하기 때문에 사전의 요소는 해시를 사용하여 O(1)에 액세스할 수 있습니다.
temp 사전을 만들고 → get()으로 모든 요소를 넣습니다.
→완주한 선수는 -1 적용
인기글
내 잔디
# 참가자 / 완주자
# 완주하지 못한 선수들의 이름을 return
def solution(participant, completion):
answer = ()
for i in range(len(participant)):
if participant(i) not in completion:
answer.append(participant(i))
else:
completion.remove(participant(i))
return ''.join(answer)왜 잘못되었는가
– 같은 이름이이다 고려하지 않았다.
이후 동명가임을 고려해 해방해 보았지만 시간의 복잡성도 고려하지 않았다.
어떤 데이터 구조로 액세스할 수 있는지 우선적으로 생각하자.
강사 수영장
def solution(participant, completion):
d = {}
# 아래의 for문 시간 복잡도는 participant 길이에 비례
for x in participant:
d(x) = d.get(x, 0) + 1 # 처음 등장하면 1
# 아래의 for문 시간 복잡도는 completion 길이에 비례
for x in completion:
d(x) -= 1
# list comprehension -> 사전의 크기에 비례하는 시간 복잡도
dnf = (k for k, v in d.items() if v > 0) # value가 0보다 큰 key값 담음.
answer = dnf(0)
return answer
# 결과적으로 시간 복잡도는 n에 비례하는 linear time 복잡도.
2. 체조복
Greedy 문제
- 알고리즘의 각 단계에서 순간이 최적이라고 생각하는 것을 선택합니다.
- 탐욕법으로 최적해를 찾을 수 있는 문제는 현재의 선택이 마지막 대답의 최적성을 해치지 않는 경우가 해당된다.
(=지금 좋은 것이 끝에도 좋다.
) - 탐욕법의 적용 가능성을 어떻게 확인합니까? → 빌리는 학생 정해진 순서로 봐야 합니다.
정해진 순서에 따라 우선적으로 빌려주는 방향을 결정해야 한다.
그 문제에서 가장 분명한 방법을 살펴 보겠습니다.
착안점 : 학생수는 기껏해야 30명.
학생수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복수를 기록한다.
→ 번호순으로 스캔하면서 빌려주는 관계를 결정한다.
내 잔디
def solution(n, lost, reserve):
answer = n - len(lost)
for i in range(len(lost)):
if lost(i) in reserve:
lost.remove(lost(i))
reserve.remove(lost(i))
elif lost(i)+1 in reserve:
answer += 1
reserve.remove(lost(i)+1)
elif lost(i)-1 in reserve:
answer += 1
reserve.remove(lost(i)-1)
return answer왜 잘못 되었습니까?
시간의 복잡성도 고려하지 않는다.
Greedy에 접근해야합니다!
생각하면 그에 따라 새로운 배열을 하나 만들어야 한다.
해결은 바로 아래 코드처럼 보입니다.
내가 접근한 방법이라면 추가 수영장에서 풀 수 있습니다.
set를 잘 활용해야 한다.
n이 상대적으로 큰 경우 추가 풀과 같은 방법으로 액세스하는 것이 좋습니다.
강사 수영장
def solution(n, lost, reserve):
u = (1) * (n+2) # 모든 원소를 1로 초기화. 2개는 맨 앞, 뒤에 추가
for i in reserve: # 여벌 있는 인원 +1 -> O(n)
u(i) += 1
for i in lost: # 도난 -> O(n)
u(i) -= 1
for i in range(1, n+1): # 정확히 n회 반복 -> O(n)
if u(i-1) == 0 and u(i) == 2:
u(i-1:i+1)=(1,1)
elif u(i) == 2 and u(i+1) == 0:
u(i:i+2)=(1,1)
return len((x for x in u(1:-1) if x>0)) # O(n)여벌을 가져온 학생 처리: reserve의 길이에 비례
체조복의 잃어버린 학생 처리 : lost의 길이에 비례
스포츠웨어 대출 처리: 학생의 총 수(n)에 비례
→ O(n) Linear time Algorithm
추가 수영장
set의 복잡도도 굳이 보면 O(n)이다.
sort 의 복잡도 : set(r) 의 요소수 = k -> klogk 를 복잡도로 가진다.
def solution(n, lost, reserve):
s = set(lost) & set(reserve) # 교집합
l = set(lost) - s
r = set(reserve) - s
for x in sorted(r): # x = 체육복을 빌려줄 수 있는 학생 번호
if x-1 in l:
l.remove(x-1)
elif x+1 in l:
l.remove(x+1)
return n - len(l)