[프로그래머스]Lv1. 예산

 

방법1

1. for loop를 통해서 하나씩 새로운 배열하나에다가 값을 넣는다.

2. 넣고 나서 배열의 총합이 budget보다 작은지 확인하고 cnt를 올린다.

3. 크다면 continue로 다음 인자를 비교한다. 

4. 새로운 배열(=budget보다 값이 작은 합들의 모임) 의 갯수를 리턴한다. 

 

계속 에러가났다. 50%밖에 통과가 안되었음. 

아차 싶었다. 너무쉽게 문제를 여겼다. 

sorting이 안되어있기때문에, for문을 두개 돌려서 i, j를 바꿔가면서 ..... (직감적으로 복잡도가 o^2 로 올라간다) 

 

방법2.

1.sort를 하고 나서 하나씩 값을 넣어서 합을 따지자. 

2. 합을 따지기 보다는 반대로 생각하자. 

3. 합을 넘어가는 요소를 빼서 남아있는 리스트의 갯수를 파악하자. 

 

 

코드

잘못된예

def solution(d,budget):
  tmp = []
  # sum=0;
  cnt=0
  for i in range(len(d)):
    if(sum(d)>budget):
      d.pop()

  print(len(d))

solution([1,3,2,5,1],9)

적용

def solution(d, budget):
    d.sort()
    while budget < sum(d):
        d.pop()
    return len(d)

느낀점

• 문제의 제한조건을 그대로 이용해서 코드로 옮기는 것도 풀이방법중 하나이지만, 그 조건의 반대입장에서 생각하는 것도 문제풀이에 도움이 됨이 은근많다. 
• 반대로 생각하라 
• "00조건에 맞는 리스트 총갯수의 합" = "00조건에 벗어나는 갯수의 합" 
• 알고리즘 문제는 난이도보다도 고민이다.