[ 프로그래머스 ] 구명보트

/  제출 1  /

 

def solution(people, limit):
    answer = 0
    boat_weight = 0
    people.sort()
    for person in people:
        if boat_weight + person <= limit:
            boat_weight += person
        else:
            answer += 1
            boat_weight = 0
            boat_weight += person
        print(boat_weight)
    if boat_weight != 0:
        answer += 1
    return answer

 

채점 결과

정확성: 20.0

효율성: 10.0

합계: 30.0 / 100.0

 

풀이 시간 15분 소요

와.. 진짜 처참한 성적.. 이틀정도 문제 풀이량 줄었다고 바로 흔들리는 실력이라니..

다시 풀어보겠습니다.

 

---

 

 

보통 위의 풀이 정도로 망한 케이스에는 아예 요구 조건을 지나쳐버린 경우가 다여서 문제를 다시 읽어봤습니다.

세상에.. 제한 사항도 아니고 문제 요구조건을 놓쳤네요. 보트에 2명밖에 탈 수 없다는 걸 고려하지 않았습니다.

 

 

/  제출 2  /

 

def solution(people, limit):
    answer = 0
    boat_weight = 0
    people.sort()
    first = 0
    last = -1
    # 2명만 탈 수 있었다..
    while people:
        if people[first] + people[last] <= limit:
            people.pop()
            people = people[1:]
            answer += 1
        else:
            people.pop()
            answer += 1
    return answer

 

채점 결과

정확성: 75.0

효율성: 15.0

합계: 90.0 / 100.0

 

수정 시간 10분 소요

 

꼭 한 번 오류가 나면 그 뒤로는 시간이 없어지니까 급급해져서 마지막 검토를 빼먹고 내는 듯 합니다. 정신 똑바로 차리고 꼼꼼하게 제출하는 걸 연습 때도 계속 길러야겠습니다.

 

그래도 정확성은 만점을 받았습니다.

문제 해결 아이디어 자체는 빨리 잡을 수 있었습니다. 

다만, 구현 방식에서 살짝 감이 안 잡혔는데 이건 파이썬 문법을 다시 공부하다가 이렇게 하는 것보다는 저렇게 하는게 좋다고 새 방식을 배워서 그걸 응용하려 하다보니 살짝 꼬였습니다. 문제 풀이 시작 전 30분 시간 제한을 스스로 정했기에 빨리 포기하고 평소같이 작성하였습니다.

 

문제 풀이 끝나고 시간복잡도 구성이나 전체 코드 복기를 안 했는데 그랬더니 2가지 테스트 케이스에서 시간 초과가 났습니다. 

이제 개선점을 찾아보겠습니다.

 

---

 

/  제출 3  /

 

def solution(people, limit):
    answer = 0
    boat_weight = 0
    people.sort()
    first = 0
    last = len(people) -1
    # 2명만 탈 수 있었다..
    while first <= last:
        if people[first] + people[last] <= limit:
            first += 1
            last -= 1
            answer += 1
        else:
            last -= 1
            answer += 1
    return answer

 

채점 결과

정확성: 75.0

효율성: 25.0

합계: 100.0 / 100.0

 

예상한 부분이 맞았습니다.

 

리스트를 재할당하고 pop하는 등 리스트에 대한 시간이 오래 걸렸습니다.

 

따라서

 

1. 리스트 수정이 없게 만들었습니다.

 

2. 이 동작이 필요했던 기능은 접근하는 인덱스를 수정하는 식으로 변경했습니다. 

 

3. while 문 멈춤 조건은 앞에서부터 증가하는 인덱스와 뒤에서부터 감소하는 인덱스가 역전되는 순간으로 설정했습니다.

 

 

---

 

/  다른 분들 풀이  / 

 

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

 

알고리즘 자체는 동일한데 

제 풀이와다른 부분이 있어서 참고하고자 가져왔습니다.

 

이 분은 전체 인원 중 보트에 두 명이 다 차는 경우를 answer에 저장하셨습니다. 남은 인원은 혼자 타고 간다는 의미이기 때문입니다. 

따라서 while문 종료 조건도 a < b로 둘이 만나는 경우는 비교하지 않았습니다.

그리고 특히 마지막에 전체 인원에서 두 명이 같은 보트에 타는 경우를 뺀 값을 리턴했습니다.

 

 

---

 

 

문제를 꼼꼼하게 읽고 

 

최대한 데이터 조작을 줄이면서 효율성을 가져가는 것에 대해 반성하는 문제였습니다.

 

그래도 풀이 시간이 3일 전보다 단축된 것 같아 다행이라고 생각합니다.

 

2일간 미친 듯이 풀고 미친 듯이 정리해서 실력 확 올리자.!