-
(프로그래머스) 코딩테스트 연습 > 그리디 > 저울코딩연습 2020. 3. 25. 00:12
추의 무게가 배열로 주어지고, 추가 측정할 수 없는 무게의 최소 값을 구하는 문제이다. 예를 들어 1, 2, 3 짜리 추가 주어졌다면, 1, 2, 3은 각각의 추로 무게를 달면 되고 4(1+3), 5(2+3), 6(1+2+3) 이런 식으로 측정이 가능하다. 그렇다면 정답은 7이 된다. 만약에 2,3,4가 주어졌다고 생각하면? 1이 정답이 된다.
def solution(weight): weight.sort() if weight[0] > 1: return 1 for answer in range(1, sum(weight)+2, 1): temp = answer if temp in weight: continue else: for i in range(len(weight)-1, -1, -1): if temp < weight[i]: continue else: temp -= weight[i] if temp != 0: return answer
결국 주어진 추의 최소 값이 1보다 커지면 답은 1이 되는 것이다. 일단 정답의 범위부터 생각을 해보았다. 1에서 주어진 추의 합 + 1 까지가 정답이 될 수 있을 것이다. 이에 따라 for loop 범위를 지정하고 정답이 주어진 무게 추 리스트에 존재하면 답이 될 수 없으니 넘기고, 그렇지 않다면 추의 조합으로 무게를 달 수 있는지 확인하였다.
채점 결과 정확성은 통과했는데 효율성은 실패하였다. 어떻게 효율을 내야하는거야아아아~~~.
https://gurumee92.tistory.com/185
이곳의 풀이를 보니 너무나 허탈하였다.
def solution(weights): weights.sort() answer = 1 for weight in weights: if answer >= weight: answer += weight return answer
추의 무게를 오름차순으로 정렬하고, 측정 불가능한 최소 무게는 추 + 1이 후보군이 될 수 있다는 사실을 이용하였다. 추 + 1이 정렬된 추들과 비교하여 무게가 작다면 최소 무게가 될 것이고 만일 무게가 크다면 모든 추들의 합 + 1이 될 것이다. 이로써 프로그래머스에서 제공하는 그리디 문제는 모두 풀어보았다. 아직 로직을 정돈하여 코드로 옮기는 능력이 부족한 것 같다.
'코딩연습' 카테고리의 다른 글
같은 숫자는 싫어 (0) 2020.08.02 두 정수 사이의 합 (0) 2020.07.30 (프로그래머스) 코딩테스트 연습 > 해시 > 위장 (0) 2020.03.25 (프로그래머스) 코딩테스트 연습 > 그리디 > 체육복 (0) 2020.03.19 (프로그래머스) 코딩테스트 연습 > 해시 > 전화번호 목록 (0) 2020.03.19