-
99클럽 코테 스터디 1일차 : 그리디, 구명보트(프로그래머스)Today_I_Learned/Algorithm 2024. 6. 6. 10:57
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
참고한 그리디 설명 영상
학습 페이지
www.inflearn.com
통과 여부
Fail
문제를 통과하지 못한 이유는 효율성 Test 로, 시간 기준을 충족하지 못한 것으로 보인다. 이 점으로 보아 내가 아직 시간 복잡도를 계산하는 부분이 취약하다는 것을 확인할 수 있었으며, 시간 복잡도 개념을 다시 공부해야겠다는 생각을 하게 되었다. 더불어 이제까지는 Test case 를 통과하는 데에만 초점을 맞추어 알고리즘을 작성했다면 앞으로는 시간 복잡도를 함께 고려하여 문제를 풀어보리라.
나의 접근법
- limit 을 2로 나눈 값을 기준으로 작은 무게와 큰 무게로 나눈 배열 구하기
- 작은 무게는 오름차순, 큰 무게는 내림차순으로 정렬
- 어느 한 배열이 끝날 때까지 반복
- 요소가 남은 배열이 작은 배열이면 2로 나누기
- 큰 배열이 남으면 남은 요소 개수만큼 더하기
오답률이 가장 낮았던 Code - Test Case 는 다 통과했지만 시간 만족도를 맞추지 못함.
def solution(people, limit): crit = limit/2 s_w = [] h_w = [] for w in people: if w <= crit: s_w.append(w) else: h_w.append(w) s_w.sort() h_w.sort(reverse=True) boat = 0 si=0 hi=0 while s_w and h_w and hi < len(h_w): sw = s_w[si] hw = h_w[hi] if sw + hw <= limit: boat += 1 s_w.pop(si) h_w.pop(hi) else: hi += 1 if s_w: if len(s_w) % 2 ==0: boat += int(len(s_w)/2) else: boat += (int(len(s_w)/2) + 1) if h_w: boat += len(h_w) return boat
'Today_I_Learned > Algorithm' 카테고리의 다른 글
99클럽 코테 스터디 5일차 TIL: 배열, Leetcode 1476. Subrectangle Queries (0) 2024.06.15 99클럽 코테 스터디 4일차 TIL : Graph, 프로그래머스, 순위 (0) 2024.06.13 99클럽 코테 스터디 3일차 TIL: Graph, Dijkstra, 프로그래머스, 가장 먼 노드 (0) 2024.06.12 MST 탐색(프림 Prim / 크루스칼 Kruskal) (0) 2023.04.16 탐욕 Greedy Algorithm (0) 2023.04.16