[Programmers] 구명보트 - Python

 

1. 문제 설명

 

2. 제한 조건 & 입출력 예

 

 

3. 시행착오

뭔가 정렬을 하면 안 될 것 같았다. 살짝 뻔하다고 생각해서.

 

 

3.1. 첫 번째 접근. Stack에 Limits 뺀 값을 저장하고 대조

for 문을 돌려서 Stack의 수보다 작으면 빼는 식으로 Stack의 요소 수를 늘렸다.

하지만 이 방법은 보트에 2명을 태운다는 조건을 지키지 못했으므로 정답이 아니었다.

# Method 1.
def solution(people, limit):
    stack = [100]
    for one in people:
        n = 0
        for i in range(0, len(stack)):
            if one <= stack[i] :
                stack[i] -= one
                n = 1
                break
        if n == 0 :
            stack.append(100 - one)   
    return len(stack)

 

 

3.2. 두번째 접근. 첫 번째 방식과 동일하지만 2명만 태우도록

이 방법의 실패 이유는 보트에 최적의 2명을 태워야 한다는 조건을 지키지 않았기 때문이다. 똑같이 보트에 넣을 수 있으면 넣었는데, 이 경우 ([70, 24, 75, 26, 50], 100)라는 반례가 생긴다.

# Method 2.
# 최대 2명만 태워야지
def solution(people, limit):
    stack = [[100,2]]
    for one in people:
        n = 0
        for i in range(0, len(stack)):
            if one <= stack[i][0] and stack[i][1] > 0 :
                stack[i][0] -= one
                stack[i][1] -= 1
                n = 1
                break
        if n == 0 :
            stack.append([100 - one, 1])   
    return len(stack)

 

 

 

4. 접근 방식과 코드 : List에 정보를 저장하자

위의 방식들은 people을 for문 돌리면서 하나하나 비교해 줬다. 그러다 보니 시간이 매우 많이 걸리게 됐다.

(1) list에 0을 limit만큼 집어넣고, people의 몸무게에 해당하는 위치에 1을 더한다.
(2) list의 n 위치는 몸무게 n을 가진 사람의 수를 의미한다.
(3) (limit - n) 은 n의 몸무게를 가지 사람이 탄 후, 보트에 들어갈 수 있는 최대한의 무게를 의미한다.
(4) 이것을 뒤에서부터 비교해서, 조건이 맞으면 1을 빼는 식으로 while 문을 돌린다.

 

Done! 

 

def solution(people, limit):
    n_list = [0] * (limit+1)
    count = 0
    for i in people:
        n_list[i] += 1

    for n in range(0, limit+1):
        subs = limit - n
        i = 0
        while n_list[n] > 0:
            if n_list[subs - i] > 0:
                n_list[subs - i] -= 1
                n_list[n] -= 1
                count += 1
            elif subs - i == 0:
                n_list[n] -= 1
                count += 1
            elif n_list[subs - i] == 0:
                i += 1
            
    return count

 

나중에 다른 사람들의 풀이를 보니 다들 정렬을 활용했다. 너무 꼬아서 생각한 감이 없지 않았다. 정렬을 활용했다면 훨씬 수월하게 문제를 풀었을 것이다. 하지만 정확성/효율성 테스트에서 거의 비슷한 결과를 보였다.

나름 최적의 또다른 해결책을 발견해서 풀었다고 생각하겠다!

 

 

 

 

아직 코딩테스트가 익숙하지 않다. 그래도 점점 적응해가고 있는 듯하다.