[알고리즘] Programmers Level 1 - 체육복(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

7 / 50(NEW!)

 

탐색

 8 / 50

 

기초 동적 프로그래밍

6 / 50

---

투포인터

1 / 10

 

이분탐색

0 / 10

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42862#

프로그래머스

→ 프로그래머스 Level 1

→ 코딩테스트 연습 > 탐욕법(Greedy)

---

문제 해결 아이디어

앞 번호를 먼저 주고, 뒷 번호를 그 다음 순서로 두자.

→ 문제에서 "여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있습니다."라는 조건이 있으므로 처음에 여벌 체육복을 가져온 학생 중 도난당한 학생은 제거

---

구현

내 풀이

# 수정 전
import copy

def solution(n, _lost, _reserve):
    lost = copy.deepcopy(_lost)
    reserve = copy.deepcopy(_reserve)
                            
    for reserve_student in _reserve:
        if reserve_student in _lost:
            lost.remove(reserve_student)
            reserve.remove(reserve_student)
    
    lost.sort()
    reserve.sort()
    for reserve_student in reserve:
        for lost_student in lost:
            if reserve_student - 1 == lost_student:
                lost.remove(reserve_student - 1)
                break
            elif reserve_student + 1 == lost_student:
                lost.remove(reserve_student + 1)
                break
    
    return n - len(lost)

처음에 무지성으로 일단 될 때까지 풀고 그 다음 다른 사람 풀이를 보면서 수정..

# 수정 후
import copy

def solution(n, lost, reserve):
    lost = [l for l in lost if l not in reserve]
    reserve = [r for r in reserve if r not in lost]
  
    for reserve_student in reserve:
        if reserve_student - 1 in lost:
            lost.remove(reserve_student - 1)
        elif reserve_student + 1 in lost:
            lost.remove(reserve_student + 1)
    
    return n - len(lost)

---

메모

• 걸린 시간: 25분
• 수정 전과 후가 딱 다른 것: sort와 동시 for문 여부
  • 첫번째 경우에 정렬을 하지 않으면 뒷 번호가 먼저 될 수도 있기 때문에 그런 것..

---

마치며

오랜만에 프로그래머스로 했는데

프로그래머스는 역시 다른 사람 풀이를 쉽게 보고 스타일을 배울 수 있어서 좋은 듯.. 굿굿