강의로 돌아가기
혜주

자바 효율성테스트

효율성테스트 통과하신 분들은 어떤 방법으로 알고리즘 작성하셨나요?ㅠㅠ
아무리 풀어봐도 계속 효율성에서 시간초과나네요..ㅠ

1 개의 답변
장용민

n을 빠르게 줄이는 방법을 생각해보면 될 것 같아요.

저는 처음 배열을 내림차순 정렬 후 for문을 돌려서 i이하에 있는 모든 배열의 원소들을 똑같이 감소시키는 개념으로 접근했어요.
예를 들어서
[11, 5, 3, 2, 1], n=15라고 하면
[5, 5, 3, 2, 1], n=9, i=0
[3, 3, 3, 2, 1], n=5, i=1
[2, 2, 2, 2, 1], n=2, i=2
위에서 더이상 한 번에 줄이지 못하므로 다음으로 넘어갑니다.
max인 2가 4개이고, 남은 n이 2이므로 answer = pow(2-1, 2)(2) + pow(2, 2)(4-2) 로 n=0으로 만든 후에 남은 원소 answer += pow(1)을 더해줬어요.

위의 과정에서 answer의 계산은 마지막에 n=0이 되었을 때부터 하고, n이 i가 증가함에 따라 빠르게 감소합니다.

  • 황인태

    c++로 heap을 이용했을 시 매번 최댓값을 갱신하여도 효율성 테스트 1 : 32.50ms, 2 : 22.84ms로 통과했습니다. 프로그래머스가 시간제한이 좀 널널한거 같습니다.

    황인태―2020.02.09 22:05
  • 장용민

    와.. 그렇군용 참고해서 제가 쓴 답변 다시 읽어보니 시간초과에 대한 얘기를 잘 모르고 했던 것 같아요. 수정하였습니다.

    장용민―2020.02.14 19:48
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.