DevCourse TIL Day4 Week2

김태준·2023년 4월 13일

Data Enginnering DevCourse

목록 보기

5/93

Day 4 학습 내용 정리
오늘 학습 내용은 코딩테스트 문제 풀이 위주이다.

✅ Hash

🎈 완주하지 못한 선수

마라톤에 참여한 선수들의 이름 배열 participants와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 리턴하는 문제

# Best sol
def solution(participant, completion):
	dic = {}
    for i in participant:
    	# 키 i가 존재하면 1, 아니면 0 이후 + 1처리
    	dic[i] = dic.get(i, 0) + 1
    for i in completion:
    	dic[i] -= 1
    dnf = [k for k, v in dic.items() if v > 0]
    answer = dnf[0]
    return answer

# 나의 풀이
def solution(participant, completion):
    member = {}
    value = 0
    for i in participant:
        member[hash(i)] = i
        value += hash(i)
    for i in completion:
        value -= hash(i)
    return member[value]

< 풀이 과정 >
'key'를 기준으로 매핑되는 해시 자료구조를 이용한 풀이.
member라는 dictionary를 만들어 준 후, hash함수를 이용해 member[hash(i)] = i 로 저장하고 value는 각 이름마다 고유 해시번호가 다르기에 + 해준다.
이후 완주한 선수들에 한해 value에서 각 해시값을 빼준다면 결과적으로 member딕셔너리에서 남은 value를 키에 넣는다면 완주하지 못한 선수만 남게 된다.

✅ Greedy Algorithm

앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해의 최적성에 영향 X
현 상태에서 최선 고르는 기법

🎈 체육복 ( 학습 완료 ✍️)

전체 학생 수 n, 체육복을 도난 당한 학생들 번호가 담긴 lost, 여벌 체육복을 가져온 학생의 번호가 담긴 배열 reseve가 있을 때 체육 수업을 들을 수 있는 학생의 최댓값을 구하는 문제

# Best Sol
def solution(n, lost, reserve):
    # 체육복 있는데 도난 당한 경우
    s = set(lost) & set(reserve)
    # 빌려야 하는 애들
    l = set(lost) - s
    # 빌려줄 수 있는 애들
    r = set(reserve) - s
	# O(klogk)에 비례 하게 됌    
    for i in sorted(r):
        if i-1 in l:
            l.remove(i-1)
        elif i+1 in l:
            l.remove(i+1)
    return n - len(l)

< 풀이 과정 >
시간 복잡도, set형으로 인한 복잡도 감소 등 위 풀이를 보고 감탄을 했다.✍️
문제에서 체육복을 가져왔는데 도난 당할 수도 있다고 했다. 따라서 이를 활용하여 다음과 같이 표현한다.

s : 체육복을 가져왔으면서 도난 당한 학생들 번호 집합
l : 체육복을 빌려야 하는데, 가져오지도 않은 학생들 번호 집합
r : 체육복을 빌려줄 여벌이 있는 학생들 번호

이후 for문으로 학생들 번호가 오름차순 정렬된 r에 대해 순회를 진행하며 i-1, i+1이 빌려야 하는 집합 l에 포함되면 remove해주고 최종적으로 학생 수 - l에 속한 수 를 리턴한다.

🎈 큰 수 만들기

문자열 형식으로 숫자 number가 주어지고 제거할 수의 개수 k가 주어졌을 때 가장 큰 숫자를 문자열 형태로 리턴하는 문제

# Best Sol
def solution(number, k):
	collected = []
    for i, num in enumerate(number):
    	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
    
# 나의 풀이
def solution(number, k):
    answer = []
    # 모든 문자 순회
    for num in number:
    	# answer 리스트가 비어있으면 추가하고 한 문자씩 확인 위해 continue
        if not answer:
            answer.append(num)
            continue
       	# 제거해야할 수가 존재하면
        if k > 0:
        	# answer에 넣은 수와 다음 수 비교해서, 다음 수가 더 큰 경우에 한해 pop, -1 진행
            while answer[-1] < num:
                answer.pop()
                k -= 1
                # answer가 비어있거나, 제거해야할 수가 없다면 중단
                if not answer or k <= 0:
                    break
        # 제거하고 남은 숫자들 추가
        answer.append(num)
    # 제거가 다 안된 경우 ex) 98765와 같은 내림차순 정렬된 리스트, 0 ~ -k번까지만 뽑기
    if k > 0:
        answer = answer[:-k]
    else:
        answer
    # 원소만 합쳐서 리턴
    return ''.join(answer)