프로그래머스 - '체육복' [코딩테스트 연습]

#체육복  #42862 # lv1

 

문제

---

 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

---

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

결과 예시

---

+) 테스트 케이스 몇 가지를 추가했다.

 

처음 문제를 보자마자 든 생각은 lost에 들어있는 번호의 학생 앞 뒤로 다 여벌을 갖고 있으면 어떡하지? 였다. 만약 count += 1 을 쓰면서 개수를 더하다보면 중복되는 경우가 생길 것 같아 바로 중복 숫자를 지워줘야겠다 생각하며 문제 로직을 생각해봤다.

# 문제 설명

# 학생들의 번호: 체격 순(바로 앞 or 뒤 인덱스에만 가능) 
# ex) reserve = [4], lost = [3] : [4] 한테는 두 벌이 있고 [3]은 없으므로, [4]가 [3]에게 한 벌을 줌.
# 전체 학생 수 : n , 도난 당한 학생 번호 : lost list, 여벌 학생 : reserve
# reserve[i] - 1 == lost[j] or reserve[i] + 1 == lost[j]
# count += 1
    
# count = n - len(lost)
# lost 요소 번호 +- 1이 reserve에 있는가? 
# 있다면, count += 1 하고 lost 요소/reserve 요소 삭제. lost 길이가 0이 되면 break
# lost 의 길이를 먼저 ?
# 잃어버렸지만 여벌이 있는 상태도 감안 -> 중복 요소 제거 후 다시 리스트 반복

근데 remove 함수를 쓰면서 중복된 요소의 개수를 셀 걱정을 할 필요가 없음을 깨닫고, 앞 뒤로 -1, +1 한 요소가 reserve에 있으면 reserve에서 해당 학생(번호)를 지워주면 됨을 알게 되었다. 그리고 count는 그대로 +1!

# 풀이

---

 

# 1 번째 풀이

def solution(n, lost, reserve):
    new_lost = []
    # lost.sort()
    # reserve.sort()
    for i in lost:
        if i in reserve: # lost = [3, 4, 5], reserve = [3, 4, 6] 인 케이스 (3, 4는 여벌이 있으므로 제외) 
            reserve.remove(i)
        else:
            new_lost.append(i) # 만약 i가 reserve에 없으면 new_lost에 할당. 
    lost = new_lost # 굳이 안해줘도 되긴 했지만, 메모리 효율상 lost에 재할당해주는 것이 나을 듯했다.

    count = n - len(lost)
    
    for i in lost:
        if i-1 in reserve: # reserve에 i-1이 있으면, 
            count += 1     # 개수 += 1
            reserve.remove(i-1) # 개수를 더해준 뒤, 중복을 없애고자 remove 함수 실행
        elif i+1 in reserve:  # 밑 조건도 마찬가지
            count += 1
            reserve.remove(i+1)
        else:
            pass
    return count  # 최종 count의 개수를 return

> 로직에 문제가 있는 거 같진 않은데... 고민 끝에 코테 연습 힌트 모음집을 참고했는데, 13, 14 테스트에서는 정렬(sorting)을 꼭 해줘야 한다고 언급하고 있었다. (프로그래머스는 많은 문제들이 sort하지 않으면 안되는 형태인 것 같다... 내 시간 ㅠㅜㅜㅠ)

 

# 2 번째 풀이

def solution(n, lost, reserve):
    new_lost = []
    for i in lost:
        if i in reserve:
            reserve.remove(i)
        else:
            new_lost.append(i) 
    lost = new_lost

    for i in reserve:
        if i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
        else:
            pass
    return n - len(lost)

> 혹시나 로직에 문제가 있나 싶어 아예 lost 에서 요소들을 제거하는 방법도 써봤는데 첫 번째 풀이와 마찬가지로 sort() 함수를 사용해 lost 리스트와 reserve 리스트를 정렬해주고 다시 돌려보니 바로 풀렸다...

 

결론

두 풀이 모두 로직에서는 문제가 없었다!!