📖 학습주제
자료구조/알고리즘 풀기(4)
해시(Hash)
키에 해시함수를 적용해 그 결과값을 해시테이블에 저장한다.
문제풀이
완주하지 못한 선수
1) 문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
2) 제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
3) 입출력 예
4) 풀이
동명이인이 있어서 같은 이름이 여러 번 나오는 경우도 생각해 봐야 한다. 완주하지 못한 사람은 딱 한명이므로 participant의 이름들이 몇 번 나왔는지 기록한 후 compeltion에서 해당 이름이 나올 때마다 1씩 빼다 보면 마지막에 값이 0이 되지 않은 선수가 완주하지 못한 선수임을 알 수 있다. 이를 위해 이름을 key값으로, 몇 번 나왔는지를 value 값으로 하는 딕셔너리를 만들어 풀이를 진행한다.
코드
def solution(participant, completion):
d = {} # 빈 딕셔너리 생성
for x in participant:
d[x] = d.get(x,0) + 1 # 딕셔너리에 없던 이름이면 value로 1을, 기존에 있던 이름이면 +1을 한다.
for x in completion:
d[x] -= 1 # 완주한 선수들이면 해당 딕셔너리 값에서 1씩 뺸다.
dnf = [k for k,v in d.items() if v > 0]
answer = dnf[0] # 완주하지 못한 선수만이 0보다 큰 값(1)을 가지므로 dnf의 가장 첫번쨰 값을 가져온다.
return answer결과
그리디(Greedy)
알고리즘의 각 단계에서 최적이라고 생각되는 것을 선택하는 알고리즘
문제풀이
체육복
1) 문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
2) 제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
3) 입출력 예
4) 풀이
여분을 가져온 학생들 중 도난당한 학생들은 여분이 없는 학생들과 같다. 따라서 reserve에서 이들을 빼고 나머지 학생들 중에서 앞번 학생과 뒷번 학생을 살펴보고 lost에 있다면 lost에서 그 학생을 제거한다. 모든 과정이 끝난 후 n에서 lost의 원소 수를 빼면 체육복을 가지고 있는 학생 수를 알 수 있다.
코드
def solution(n, lost, reserve):
s = set(lost) & set(reserve) # 여분을 가져왔지만 도난당한 학생
l = set(lost) - s # 도난당한 학생
r = set(reserve) - s # 여분을 가지고 있는 학생
for x in sorted(r): # 앞번과 뒷번을 보고 빌려줘야 한다면 빌려줘서 도난당한 학생 목록에서 없앤다(앞번 우선)
if x-1 in l:
l.remove(x-1)
elif x+1 in l:
l.remove(x+1)
return n - len(l)결과
큰 수 만들기
체육복
1) 문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
2) 제한사항
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
3) 입출력 예
4) 풀이
앞에 오는 숫자가 클수록 더 큰 숫자임은 자명하다. 따라서 리스트에 각 자리 숫자를 저장해가다가 더 큰 숫자가 나오면 제거하는 방식으로 앞에 큰 숫자가 올 수 있도록 한다.
코드
def solution(number, k):
collected = [] # 각 자리 숫자를 저장할 리스트
for i, num in enumerate(number):
# collected에 원소가 존재하고 제거한 숫자가 k보다 적으며 현재 숫자가 최근 저장한 숫자보다 적을 경우 제거
while len(collected) > 0 and collected[-1] < num and k > 0:
collected.pop()
k -= 1
if k == 0: # 주어진 횟수만큼 숫자를 제거했다면 나머지 숫자는 이엉붙인다.
collected += list(number[i:])
break
collected.append(num)
# 만약 아직 횟수가 남아있다면 숫자가 내림차순으로 정렬되어있는 것과 같으므로 뒤에서 숫자를 제거한다.
collected = collected[:-k] if k > 0 else collected
answer = ''.join(collected)
return answer결과
정렬(Sort)
문제풀이
가장 큰 수
1) 문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
2) 제한사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
3) 입출력 예
4) 풀이
리스트가 이미 크기순으로 정렬되어있다고 가정하고 원소를 뽑아보자.
3과 34를 뽑았을 때 각각이 만들어질 숫자의 가장 앞에 온다고 했을 때 이 리스트는 이미 정렬되어 있으므로 3을 뽑았을 때 만들 수 있는 숫자는 33333..을 넘지 못한다. 마찬가지로 34를 뽑았을 때 34343434...를 넘지 못한다. 3보다는 34를 뽑았을 때 더 큰 수를 만들 수 있다. 제한사항아ㅔ서 numbers의 원소는 1000이하이므로 반복된 수를 4자리로 제한하여 비교해 정렬한다.
코드
def solution(numbers):
numbers = [str(x) for x in numbers]
# 1000이하이므로 각 숫자를 4번 반복하고(1의 자리더라도 4자리로 맞춰진다.) 앞에서 4자리를 잘라 비교한다.
# 큰 순으로 정렬해야 하므로 reverse = True
numbers.sort(key = lambda x : (x*4)[:4], reverse = True)
# 크기순으로 정렬한 리스트의 첫번째가 0인 것은 숫자를 조합했을 때 0이 나온다는 것과 같다.
if numbers[0] == '0':
answer = '0'
else:
answer = ''.join(numbers)
return answer결과
