[프로그래머스] Lv1 체육복_그리디 python 문제 풀이

출처

https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3

문제

몇몇 학생들이 체육복을 도둑맞았는데, 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려줌.

바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다.
예를들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌릴 수 있음
또한 여벌 체육복을 가져온 학생이 체육복을 도둑맞았을 수도 있다. 이럴 때는 남에게 빌려줄 수 없다.

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

입출력 예시

 

 

문제풀이1

def solution(n, lost, reserve):
    # 받은 배열값 정렬
    lost.sort()
    reserve.sort()
    # remove() 시 배열값이 줄어드는 현상을 방지하기 위한 copy
    sub_reserve = reserve.copy()
    # 여벌 체육복을 가져온 학생이 체육복을 도둑맞았을 경우의 처리
    for r in sub_reserve:
        for l in lost:
            # 자기 자신이 체육복을 도둑맞았을 때의 경우 remove
            if l == r:
                lost.remove(l)
                reserve.remove(l)
                break

    # 체육복 빌려주기 로직 시작
    for r in reserve:
        for l in lost:
            # 체육복 번호 기준 왼쪽 사람에게 우선 빌려주기
            if l == r - 1:
                lost.remove(l)
                break
            elif l == r + 1:
                lost.remove(l)
                break
    # 체육수업 들을 학생 return
    return n - len(lost)

• 다중 for 문 사용으로 시간복잡도가 높다는 문제점이 있다. (학생 수에 제한이 있어서 그리 중요하진 않지만)
• 코드가 길고, 깔끔하지 않다.

 

문제풀이2

def solution(n, lost, reserve):
    # set() 사용 시 교집합이 맞지 않는 현상을 방지하기 위한 copy
    sub_reserve, sub_lost = reserve.copy(), lost.copy()
    # set() 사용으로 여벌 체육복을 가져온 학생이 체육복을 도둑맞았을 경우 처리 + 정렬 (교집합 제거)
    lost, reserve = sorted(list(set(sub_lost) - set(sub_reserve))), sorted(list(set(sub_reserve) - set(sub_lost)))

    # 체육복 빌려주기 로직 시작
    for r in reserve:
        # 체육복 번호 기준 왼쪽 사람에게 우선 빌려주기 (if in 써도됨)
        if lost.count(r - 1):
            lost.remove(r - 1)
            continue
        elif lost.count(r + 1):
            lost.remove(r + 1)
            continue
    # 체육수업 들을 학생 return
    return n - len(lost)

• 위의 코드 기준으로, 코드를 줄여본 풀이
• 다중 for 문을 사용하지 않으려 했지만, 생각해보니 remove 도 n 인거 같았다😥

 

내가 생각한 좋은 문제풀이

# 박준영 , 홍정호
def solution(n, lost, reserve):
    student = [1]*n # [1, 1, 1, 1, 1]

    for i in lost:
        student[i-1] = 0 # [1, 0, 1, 0, 1]

    for i in reserve:
        student[i-1] += 1 # [2, 0, 2, 0, 2]

    first_student = student[0]
    last_student = student[len(student)-1]

    if first_student == 0:
        if student[1] == 2:
            student[0] = 1
            student[1] = 1

    if last_student == 0:
        if student[len(student)-2] == 2:
            student[len(student)-1] = 1
            student[len(student)-2] = 1

    for i in range(1, len(student)-1):
        if student[i] == 0:
            if student[i-1] == 2:
                student[i] = 1
                student[i-1] = 1
            elif student[i+1] == 2:
                student[i] = 1
                student[i+1] = 1
    return student.count(1) + student.count(2)

• 시간 복잡도가 n 이다.(어떻게 생각하셨지)
• 코드가 길지만, 그렇게 막 복잡하지는 않다.