[Python][프로그래머스] 가장 큰 수 / 정렬 (Lv2)

🖇️ 링크 

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

---

🗒️ 파이썬 코드 풀이

def solution(people, limit):
    people.sort()
    answer = 0
    
    S = 0
    E = len(people) - 1 
    
    print(people)
    while S <= E :
        
        if limit >= people[S] + people[E] :
            S += 1 
            E -= 1 
            answer += 1
            
        else : 
            E -= 1 
            answer += 1 
            
    return answer

시간 복잡도 O( N·Log N)

 

1. people 리스트를 정렬 해준다 .

→ 해당 문제를 정렬 없이 하려면 완전 탐색 밖에 없는 것 같다. 

 

2. S와 E의 값이 역전 될 때까지 while 문을 돌린다.

 

3. 투포인터 방식으로 알고리즘을 풀어가면 된다. 

• Start, End의 인덱스의 합이 limit 보다 작거나 같은 경우 
  • Start, End를 구명 보트 태워 보냄
  • Start 옆에 있는 사람이 조건에 맞으면 Start 대신 태워도 되는데, 굳이 옆애 있는 애를 건드릴 필요는 없어보인다.
• Start, End의 인덱스의 합이 limit 보다 큰 경우 
  • End만 구명 보트 태워 보냄
  • Start (가장 무게 적게 나가는)와도 안되니 그 어떤 사람과도 탈 수 없음

 

---

📌  문제 코멘트 

이 문제를 포스팅 하는 이유는 다음과 같다

1. 탐욕법 적용 + 투포인터 사용
2. 문제의 조건 "최대 2명" 까지 탑승 가능한거를 못보고 삽질

 

아이디어만 생각하면 구현 자체는 어렵지 않은 문제 ! 

---

📚  문제