[programmers] 프로그래머스 Level1 체육복 (파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level1 체육복

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

 

1) 문제

---

프로그래머스 체육복 파이썬

코딩테스트 연습 - 체육복

 

 

 

 

 

2) 코드

---

 

1) 그리디 풀이

def solution(n, lost, reserve):
    answer = n - len(lost)
 
    remove_list = []
 
    for lost_student in lost :
        for reserve_student in reserve :
            if (lost_student == reserve_student) :
                remove_list.append(lost_student)
 
    for remove_student in remove_list :
        answer += 1
        lost.remove(remove_student)
        reserve.remove(remove_student)
 
    for i in range(1, n + 1) :
        if i in lost :
 
            # front
            front = i - 1
            if (front in reserve) :
                answer += 1
                reserve.remove(front)
                continue
 
            # rear
            rear = i + 1
            if (rear in reserve) :
                answer += 1
                reserve.remove(rear)
 
    return answer

 

 

시간복잡도 : O(30)

 

 

 

1-1) 완전탐색(dfs) - 파이썬 스타일 풀이(set 자료구조 이용 및 파이썬 표준 함수 max() 사용)

def dfs(cur_idx, n, lost, reserve) :
    
    if (cur_idx > n) :
        return 0
    
    if (cur_idx in lost) :
        # borrow front
        front_idx = cur_idx - 1
        if (front_idx in reserve) :
            reserve.remove(front_idx) # 중복 제거
            front_answer = dfs(cur_idx + 1, n, lost, reserve) + 1
            reserve.append(front_idx) 
      
        
        else :
            front_answer = -1
            
        # borrow rear
        rear_idx = cur_idx + 1
        if (rear_idx in reserve) :
            reserve.remove(rear_idx)
            rear_answer = dfs(cur_idx + 1, n, lost, reserve) + 1
            reserve.append(rear_idx)
        # not borrow rear
        
        else :
            rear_answer = -1
            
    else :
        front_answer = -1 # Not happened
        rear_answer = -1  # Not happened
    
    # 지금 현재 상태에서 빌리지 않았을 때 최대한의 경우
    no_borrow_answer = dfs(cur_idx + 1, n, lost, reserve)
    
    best_answer = max(front_answer, rear_answer, no_borrow_answer)
    
    return best_answer
 
def solution(n, lost, reserve):
    
    set_lost = sorted(set(lost)-set(reserve))
    set_reserve = sorted(set(reserve)-set(lost))
    
    answer = n-len(set_lost)
        
    best_borrow_case = dfs(1, n, set_lost, set_reserve)
    
    return answer + best_borrow_case

 

 

 

 

2. Low한 풀이

def dfs(cur_idx, n, lost, reserve) : #cur_idx 학생(잃어 버린) n번째 위치에 있을 때 앞에서 빌려 올 수도 있고, 뒤에서 빌릴 수 있다.
     if (cur_idx > n) :
        return 0
    
    if (cur_idx in lost) :
        # borrow front
        front_idx = cur_idx - 1
        if (front_idx in reserve) :
            reserve.remove(front_idx) # 중복 제거
            front_answer = dfs(cur_idx + 1, n, lost, reserve) + 1 
            reserve.append(front_idx) 
 
        # not borrow front
        else :
            front_answer = -1
            
        # borrow rear
        rear_idx = cur_idx + 1
        if (rear_idx in reserve) :
            reserve.remove(rear_idx)
            rear_answer = dfs(cur_idx + 1, n, lost, reserve) + 1
            reserve.append(rear_idx)
 
        # not borrow rear        
        else :
            rear_answer = -1
            
    else :
        front_answer = -1 # Not happened
        rear_answer = -1  # Not happened
    
    # 지금 현재 상태에서 빌리지 않았을 때 최대한의 경우
    no_borrow_answer = dfs(cur_idx + 1, n, lost, reserve)
    
    if (front_answer >= rear_answer) and (front_answer >= no_borrow_answer) :
        best_answer = front_answer
    elif (rear_answer >= front_answer) and (rear_answer >= no_borrow_answer) :
        best_answer = rear_answer
    else :
        best_answer = no_borrow_answer
    
    return best_answer
 
def solution(n, lost, reserve):
    
    answer = n - len(lost)
    
    #내가 있는데, 내가 도난당한 경우를 리스트로 선언한 것.
    remove_list = [] 
    
    # 내가 여벌이 있는데, 내가 도난당한 경우
    for reserve_student in reserve :
        for lost_student in lost :
            if (lost_student == reserve_student) :
                remove_list.append(lost_student)
    
    # 내가 여벌이 있는데, 내가 도난을 당했으면 나 부터 써야지. 그럼 나는 잃어버린것도 아니고, 여분이 있는것도 아님. 그래서 뺀거임.
    for remove_student in remove_list :
        answer += 1
        lost.remove(remove_student)
        reserve.remove(remove_student)
    
    best_borrow_case = dfs(1, n, lost, reserve)
    
    return answer + best_borrow_case

 

 

 

 

 

 

 

3) 풀이 과정

---

핵심 : 체육복을 최대한 많이 빌려야 한다.(최대한 많이 체육 수업을 듣기 위해서)

 

How?

1) 체육복을 도난당한 사람

2) 체육복을 여벌로 가지고 온 사람

3) 2)의 사람이 1)사람과 겹치면, 먼저 처리한다.

 

 

 

 

 

 

 

< < 사고 과정 > >

---

1. 최대한 많은 학생들이 체육 수업을 듣기 위해서는 최대한 많은 체육복이 필요하다.

2. 단순 직관적인 그리디로 생각

 

 

 

 

 

 

 

 

4) 정리 노트

---

X