코딩테스트 연습문제

---

해시(Hash)문제-완주하지 못한 선수

해시 테이블은 키(key)와 값(value)으로 구성된 자료 구조다.

프로그래머스 코딩테스트 연습에 있는 문제입니다.
https://school.programmers.co.kr/learn/courses/30/lessons/42576

완주하지 못한 선수

def solution(participant, completion):
    d ={}
    for x in participant:#참가자를 딕셔너리형태로 저장
        d[x] = d.get(x,0) + 1 #x가 있으면 원래 value 없으면 0을 반환
    for x in completion:#완주자를 참가자에서 뺌
        d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0] #value가 0 보다 큰 키값(완주 못한 사람)반환
    answer = dnf[0]
    return answer

그리디(Greedy)문제 - 체육복

---

그리디알고리즘은 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하는 것이다.

https://programmers.co.kr/learn/courses/30/lessons/42862#
체육복 문제는 위 링크 참고하세요!

체육복

def solution(n, lost, reserve):
    all = [1]*(n+2)#앞뒤 번호를 파악할 때 맨 앞,뒷사람때문에 하나씩 더 추가한다.
    for i in reserve:#여벌옷이 있는사람 +1
        all[i]+=1
    for j in lost:#옷을 잃어버린 사람 -1
        all[j]-=1
    for i in range(1,n+1):#앞사람을 먼저 나눠주는 방식
        if all[i-1]==0 and all[i] == 2:#자기 앞사람 옷이 없고 자기가 여벌옷이 있으면 나눠줌
            all[i-1:i+1]=[1,1]
        elif all[i+1]==0 and all[i] == 2:#뒷사람이 없으면 나눠줌
            all[i:i+2]=[1,1]
        else:
            pass
    answer = n-all.count(0)
    return answer#len([x for x in all[1:-1] if x>0])

정렬(Sort) - 가장 큰 수

---

문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42746
자세한 내용은 위 링크 참고!

def solution(numbers):
    numbers = list(map(str,numbers))#문자열로 변경
    numbers.sort(key=lambda x :(x*4)[:4],reverse = True) #각 숫자는 1000이하이므로 :4까지
    if numbers[0] == '0':#0이하의 원소도 들어가므로 0만 있는 리스트일 때 처리
        answer ='0'
    else:
        answer = ''.join(numbers)
    return answer

그리디(Greedy) - 큰 수 만들기

---

문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42883
자세한 내용은 위 링크 참고

def solution(number, k):
    collected =[]
    for i, num in enumerate(number):
        while len(collected)>0 and collected[-1]< num and k>0: #collected에 맨 마지막에 들어간 문자와만 비교하면 된다
            collected.pop()
            k-=1
        if k == 0:#k가 0일때 나머지 다 이어 붙인다.
            collected += list(number[i:])
            break
        collected.append(num)
    
    collected = collected[:-k] if k>0 else collected#빼낼 숫자가 남았을 경우
    answer = ''.join(collected)#리스트에 저장된 숫자를 이어붙임
    return answer

---