구명보트

 

프로그래머스

💡 생각

combinations의 경우 시간 초과, 메모리 초과 실패가 난다 어떻게 접근해야할까... 탐욕 알고리즘 쓰라고 떡하니 써있는데 뭔지 몰라 쓰질 못하는 멍청한 인간 ㅎㅎ
질문하기 흘끔 보고 deque로 풀 수 있는 걸 봤음

❌
우선 제일 무거운 애부터 뺄 거기 때문에 people 배열을 큰 순서대로 정렬하고 이를 데크 dq로 만든다.
몇 번 왔다갔다 해야하는지 표시할 answer 정수 플래그를 만든다.
dq가 존재하는 동안,
제일 무거운 애와 제일 가벼운 애의 합이 limit 보다 큰 경우 제일 무거운 애 혼자 보내고 dq에서 빼버린다.
제일 무거운 애와 제일 가벼운 애의 합이 limit 보다 작거나 같은 경우 누구든 같이 보낼 수 있으므로 누구랑 같이 보낼지 탐색해본다.

• 일단 제일 무거운 애는 갈거니까 popleft 하는 동시에 max 값으로 저장해놓는다.
• max 값과 같이 갈 수 있는 애를 가장 큰 수부터 찾는다.
• 갈 수 있는 애를 찾으면 걔도 popleft로 보내버린다.
• 갈 수 있는 애가 아닌 경우 popleft로 뽑았다가 append로 다시 뒤로 보내버린다.
• 이 과정에서 뒤죽박죽된 dq를 다시 정렬해줘야 된다.

from collections import deque

def solution(people, limit):
    # 큰 것부터 정렬
    people = sorted(people, reverse=True) # [80, 70, 50, 50]
    # 데크로 만들기
    dq = deque(people)

    answer = 0

    while len(dq) > 1:
        # 젤 무거운 애 혼자 가야댐
        dq = deque(sorted(dq, reverse=True))
        if dq[0] + dq[-1] > limit:
            answer += 1   
            dq.popleft()
            # print("혼자 갑니다~", dq)
        # 같이 갈 수 있는 경우
        else:
            answer += 1   
            max = dq.popleft()
            while True:
                # 갈 수 있는 애 찾기
                if dq[0] <= limit - max:
                    # 갈 수 있음
                    dq.popleft()
                    # print("같이 갈 수 잇숴", dq)
                    break
                # 못감, 다른 애로 넘어가야함
                else:
                    nope = dq.popleft()
                    dq.append(nope)
                    # print('못가 넘어가', dq)
    if dq:
        answer += 1

    return answer

 

정확성 만점 효율성 빵점 흑흑 효율성이 문제구만
넣었다 빼는 부분이 문제인건가 다시.. deque에서 쓸 수 있는 메서드를 확인하기 위해 print(dir(dq)) ..

❌ 눈에 띄는 rotate 요걸로 순회돌리면 괜찮으려나!? rotate(1)하면 맨 뒤에 있는 애가 맨 앞으로 오므로 rotate(-1)로 맨 앞에 있는 애가 맨 뒤로 가는 방향으로 돌렸다.

from collections import deque

def solution(people, limit):
    # 큰 것부터 정렬
    people = sorted(people, reverse=True) # [80, 70, 50, 50]
    # 데크로 만들기
    dq = deque(people)

    answer = 0

    while len(dq) > 1:
        # 젤 무거운 애 혼자 가야댐
        dq = deque(sorted(dq, reverse=True))
        if dq[0] + dq[-1] > limit:
            answer += 1   
            dq.popleft()
            # print("혼자 갑니다~", dq)
        # 같이 갈 수 있는 경우
        else:
            answer += 1   
            max = dq.popleft()
            while True:
                # 갈 수 있는 애 찾기
                if dq[0] <= limit - max:
                    # 갈 수 있음
                    dq.popleft()
                    # print("같이 갈 수 잇숴", dq)
                    break
                # 못감, 다른 애로 넘어가야함
                else:
                    dq.rotate(-1)
                    # print('못가 넘어가', dq)
    if dq:
        answer += 1

    return answer

 

어림도 없지 시간 초과! 순회도 어차피 똑같은거니께..
진촤 모르겠어서 질문하기를 봤는데 순회를 돌리는게 아닌 맨 앞 원소와 맨 뒤 원소를 빼는 거였다. 그니까 굳이 젤 큰 애랑 같이 데려갈 애를 탐색할 필요 없이 젤 작은 애를 데려가면 된다는 것... [10, 20, 30, 70, 80, 90, 100] 구로넹... 왜 이 생각을 못했을까

 

📖 내 코드

from collections import deque

def solution(people, limit):
    # 큰 것부터 정렬
    people = sorted(people, reverse=True) # [80, 70, 50, 50]
    # 데크로 만들기
    dq = deque(people)

    answer = 0

    while len(dq) > 1:
        # 젤 무거운 애 혼자 가야댐
        if dq[0] + dq[-1] > limit:
            answer += 1   
            dq.popleft()
            # print("혼자 갑니다~", dq)
        # 같이 갈 수 있는 경우
        else:
            answer += 1   
            dq.pop()
            dq.popleft()
    if dq:
        answer += 1

    return answer

 

📑 다른 사람의 풀이

def solution(people, limit) :
    answer = 0
    people.sort() # [50, 50, 70, 80]

    a = 0
    b = len(people) - 1 # 3
    while a < b :
        # 맨 처음 사람과 맨 뒷 사람의 몸무게 합이 limit보다 작거나 같을 때 (같이 갈 수 있음)
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    # 같이 갈 수 있으면 사람 2명을 1명으로 치는 것과 같으므로...
    return len(people) - answer

 

오마이갓 떼엠 ,,,~ 와 포인터인가? 저렇게 a, b로 가리키면서 넘어갈 수 있구나.. 무릎갈린다 진짜 똑똑하다 우와..