[프로그래머스] 고득점Kit (6) - 그리디(1) (파이썬)

1. 체육복 (Lv. 1)

# 체육복
def solution(n, lost, reserve):
    lost = set(lost)
    reserve = set(reserve)
    answer = 0
    for x in (lost-reserve):
        if x-1 in (reserve-lost):
            reserve.remove(x-1)
            continue
        elif x+1 in (reserve-lost):
            reserve.remove(x+1)
            continue
        answer += 1
    return n - answer

 

집합의 성질을 이용했다. (차집합 이용)

체육복을 잃어버린 인원 중, 여벌 체육복이 없는 인원들(lost - reserve)을 for문으로 돌면서

앞이나 뒤의 사람이 여벌 체육복을 가지고 왔으면서 체육복을 잃어버리지 않은 집합(reserve - lost)에 속해 있다면

reserve에서 remove해주고 continue (앞사람 먼저 : 그리디)

둘 다 없다면 answer += 1 (체육복을 구하지 못한 인원)

n - answer 리턴

---

2. 조이스틱 (Lv. 2)

# 조이스틱
def solution(name):
    answer = 0
    move = len(name) - 1
    for i in range(len(name)-1, -1, -1):
        if name[i] == 'A':
            move -= 1
        else:
            break
    for i, alpha in enumerate(name):
        answer += min(ord(alpha) - ord('A'), ord('Z') - ord(alpha) + 1)
        ni = i + 1
        while ni < len(name) and name[ni] == 'A':
            ni += 1
        move = min(move, 2*i + len(name) - ni)
        move = min(move, (len(name) - ni)*2 + i)
    answer += move
    if answer < 0:
        return 0
    return answer

 

오른쪽으로만 이동할 때의 최소 값을 구해준다. (len(name)-1에서 맨 뒤에 'A'가 연달아 있을 경우 빼주면 된다.)

이제 name을 전부 돌면서

    - 알파벳을 바꾸기 위해 조이스틱을 누르는 값의 최솟값을 answer에 더해준다.

    - 다음 알파벳이 'A'이면 다음 인덱스 값(ni)를 증가시켜서 'A'가 아닌 다음 인덱스 값을 구한다.

    - move의 원래 값과 오른쪽으로 가다가 왼쪽으로 가는 값과 왼쪽으로 가다가 오른쪽으로 가는 값의 최솟값을 구한다.

answer += move

 

왜 Lv.2인지 모르겠다. 생각해야할 것이 한 두 개가 아니다.

---

3. 큰 수 만들기 (Lv. 2)

# 큰 수 만들기
def solution(number, k):
    answer = []
    for x in number:
        if k == 0:
            answer.append(x)
        elif not answer:
            answer.append(x)
        else:
            while answer and int(answer[-1]) < int(x) and k > 0:
                answer.pop()
                k -= 1
            answer.append(x)
    answer = answer[:len(answer)-k]
    return ''.join(answer)

 

k번 전부를 pop하더라도 가장 앞에 있는 수가 가장 커야 하므로

answer[-1]이  x(append할 숫자)보다 작으면 pop, k -= 1 (k : pop할 수 있는 수), 이후 append를 해준다

k가 0보다 클 경우 뒤에서부터 슬라이싱을 해줘야한다. (answer[:len(answer)-k])