[PROGRAMMERS] 탐욕법 뽀개기 | 파이썬 | 프로그래머스 탐욕법(Greedy) 문제풀이

PROGRAMMERS 프로그래머스 코딩테스트 연습 > 고득점 kit >  탐욕법 https://programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

 

Lv1. 체육복

체육복을 도난당한 학생들의 번호가 담긴 배열 lost와 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 주어진다.

여벌을 가져온 학생들은 도난당한 학생들 중 자신의 바로 앞이나 뒤 번호의 학생에게 체육복을 빌려줄 수 있으며 여벌을 챙겨온 학생이 도난을 당한 경우도 있다.

체육복이 있어 체육수업을 들을 수 있는 학생들의 최댓값을 구하여라

 

첫 번째 시도) 정확성 75

def solution(n, lost, reserve):
    answer = n
    reserve.sort(reverse=True)
    for r in reserve:
        if (r-1 in lost) or (r in lost) or (r+1 in lost):
            lost.pop()
    return n - len(lost)

여벌을 가져온 학생들 기준으로 해당 학생 앞, 뒤 학생 혹은 본인이 체육복을 도난당했다면 빌려주고 lost 배열에서 제거한다.

여벌을 챙겨온 학생이 도난 당한 경우 다른 학생들에게 빌려주지 못함으로 이를 먼저 생각했어야하는데 순서가 꼬여서 실패,,

 

두 번째 시도) 정확성 70

def solution(n, lost, reserve):
    answer = n
    reserve.sort()
    lost_ = list(set(lost) - set(reserve))
    reserve = list(set(reserve) - set(lost))
    for r in reserve:
        if (r-1 in lost_) or (r+1 in lost_):
            lost_.pop()
    return n - len(lost_)

이전 방법에서의 문제를 해결하고자 두 배열 사이 겹치는 학생, 즉 여벌을 가져왔지만 도난당한 학생들을 집합 연산으로 배제하고 시작했다.

여벌있는 학생을 제외하고 도난당한 학생들 번호를 새로 저장한 배열 lost_에서 어차피 한명씩 지워지면 된다고 생각해서 pop()을 한것이였는데 이러면 이후 비교가 꼬인다는 점을 발견

 

최종 답안 코드) 

def solution(n, lost, reserve):
    answer = n
    reserve.sort()
    lost_ = list(set(lost) - set(reserve))
    reserve = list(set(reserve) - set(lost))
    for r in reserve:
        if (r-1 in lost_) or (r+1 in lost_):
            lost_ = lost_[1:] # 앞의 학생부터 비교하고 있음으로 앞을 삭제해야함
    return n - len(lost_)

reserve 배열을 오름차순 정렬 후 비교하기 때문에 pop()연산이 아니라 리스트 맨 앞을 제거하여 문제 해결

나는 배열을 슬라이스하여 맨 앞 요소를 날렸는데 deque로 생성해서 popleft() 연산을 하는게 더 성능상으로 좋지 않을까.. 하는 생각..

 

 

Lv2. 조이스틱

조이스틱으로 알파벳 이름을 완성하기까지 필요한 조이스틱 조작 횟수의 최솟값을 구하는 문제

 

잘 생각해야할 점은 꼭 오른쪽 왼쪽으로 모두 이동 가능하기 때문에 문자열의 양 끝에서 반대편으로 한번 조작을 통해 이동 가능하다는 것

1회차 풀이할때도 머리 꽤나 아팠던 문제.. 프로그래머스 2단계는 익숙해질듯 익숙해지지 않는다.

 

첫 번째 풀이) 정확성 48.1

def solution(name):
    answer = 0
    
    max_dist, dist = 0, 0
    max_i, max_j = 0, 0
    last = 0
    for i, n in enumerate(name):
        if n != 'A':
            answer += min(abs(ord(n) - ord('A')), abs(ord('Z')-ord(n)+1))
            last = i
        else:
            dist += 1
            if max_dist < dist:
                max_dist = dist
                max_i, max_j = i-max_dist+1, i   

    if max_dist == len(name):
        answer = 0
    elif max_dist != 0:
        answer += min(last, ((max_i-1)*2 + (len(name)-max_j-2) + 1))
    elif max_dist == 0:
        answer += (last)
    
    return answer

먼저 A가 아닌 알파벳의 경우 필요한 조작 횟수 먼저 계산, 이때 위로 움직여서 조작하는 방법과 아래로 움직여서 조작하는 방법 중 최솟값을 선택해야 함

이전 풀이때 배웠지만 이 문제에서 중요한 것은 가장 길게 연속된 A 구간을 찾는 것

그 구간을 기준으로 A를 다 지나쳐서 다음 조작이 필요한 알파벳으로 갈지 아니면 지나치지않고 역순으로 돌아 도달할지 정해아함

첫 번째 if는 모두 A로 이뤄졌을 때, 조작 횟수는 총 0이다.

두 번째 if에서 A가 연속되는 구간이 있다면 오른쪽으로 이동하여 A를 지나치는게 더 적은지 왼쪽으로 이동하여 거꾸로(오->왼) 가는게 더 빠른지 계산

세 번째 if는 A가 연속하여 나타나지 않을 때, A가 아닌 마지막 요소의 인덱스(전체 이동 거리)를 더한다.

 

두 번째 시도) 44.4

def solution(name):
    answer = 0
    max_dist, dist = 0, 0
    max_i, max_j = 0, 0
    last = 0
    for i, n in enumerate(name):
        if n != 'A':
            answer += min(abs(ord(n) - ord('A')), abs(ord('Z')-ord(n)+1))
            dist = 0 # A 거리 초기화해줌
            last = i
        else:
            dist += 1
            if max_dist < dist:
                max_dist = dist
                max_i, max_j = i-max_dist+1, i
                
    if max_dist == len(name):
        answer = 0
    elif max_dist != 0:
        print(((max_i)*2 + (len(name)-1-last)+1), ((len(name)-1-last)*2+1+(max_i)))
        tmp = min(((max_i)*2 + (len(name)-1-last)+1), ((len(name)-1-last)*2+1+(max_i-1)))
        answer += min(last, tmp)
    elif max_dist == 0:
        answer += last
    
    return answer

연속된 A 구간의 길이가 아니라 인덱스를 이용한 풀이로 수정했지만,, 여전히 좋지 못한,,

 

결국 다른 사람 풀이 참고)

def solution_other(name):
    answer = 0
    min_left_right = len(name) # 왼쪽에서 오른쪽으로만 이동할 때 좌,우 조작 횟수
    next_idx = 0
    for idx, char in enumerate(name):
        # up/down
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        # left/right
        next_idx = idx + 1
        while next_idx < len(name) and name[next_idx] == 'A':
            next_idx += 1 # 현재 위치 이후 연속된 A 다음의 문자를 가리킴
        
        # 한 방향으로만 이동하는 경우와, 오른쪽으로 이동했다가 왼쪽으로 이동하는 경우를 비교
        min_left_right = min(min_left_right, idx + idx + len(name) - next_idx)
    answer += min_left_right
    return answer

1회차 풀때도 결국 해결하지 못하고 구글링해서 풀었었는데 2회차인 이번에도 못풀었다..😵‍💫

내가 하고싶었던 방법대로 연속된 A구간의 시작과 종료 인덱스를 구하여 한 방향으로만 이동하는 경우와 거꾸로 이동하는 경우를 비교한다.

사실 문제 푼지 몇주 시간이 지나서 이제 다시 보니 이해가 될랑말랑하다,,

 

 

Lv2. 큰 수 만들기

한자리수 이상의 숫자 문자열 number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 구하는 문제

 

 

Lv2. 구명보트

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 한다. 구명보트는 한번에 최대 2명까지 탈 수 있고 무게 제한도 있다.

사람들의 몸무게가 담긴 배열 people과 무게 제한 limit이 주어질 때 모든 사람을 구출하기 위해 필요한 구명보트의 최소 개수를 구하여라

 

첫 번째 시도)

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    total = people.pop()
    while people:
        if total + people[-1] > limit:
            answer += 1
            total = 0
        else:
            total += people[-1]
            people.pop()

    return answer+1

구명보트 최대 인원수가 2명인 것을 확인하지 못하고 푼 방법.. 주어진 문제 조건을 잘 읽을 것..

 

두 번째 시도)

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    
    while people:
        if len(people) < 2:
            answer += 1
            break
            
        if people[-2] + people[-1] <= limit:
            people.pop()
            people.pop()
        else:
            people.pop()
        answer += 1
        
    return answer

몸무게 배열 정렬 후 2명의 무게 합을 무게 제한과 비교함으로써 최대 인원이 2명인 조건은 만족하였지만 최소 횟수 조건은 만족하지 못함

최솟값을 구하기 위해 무게가 작은 사람부터 2명씩 짝지어 보낼려고 내림차순 정렬 후 무게가 작은 사람부터 접근하였는데 잘못된 접근 방식이였다 ㅠ

 

마지막 시도와 통과) 

import collections
def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    people = collections.deque(people)
    
    while people:
        if len(people) < 2:
            answer += 1
            break
        if people[0] + people[-1] <= limit:
            people.pop()
            people.popleft()
        else:
            people.popleft()
        answer += 1
        
    return answer

일단 실행시간을 아끼기 위해 양방향 접근 가능한 deque와 popleft() 사용

최솟값을 구하기 위해서는 최대한 많이 2명씩 짝지어야 한다.

따라서 이전처럼 가장 작은 사람들끼리 짝을 지을 것이 아니라 가장 무거운 사람과 가장 가벼운 사람을 짝지어 보트에 태워야한다.