-
큰 수 만들기 (프로그래머스, 레벨2)개발자의 길/Algorithm 2021. 3. 12. 16:22
https://programmers.co.kr/learn/courses/30/lessons/42883
첫 번째 아이디어는 조합(combinations)을 이용하는 것이다.
예시는 다 통과했는데 실제 테스트에서 시간 초과가 나온다. 모든 조합의 경우의 수를 리스트에 만들어서 최댓값을 뽑아오기 때문에 시간이 오래 걸리는 것 같다. 시간문제만 아니면 간단한 코드로 해결할 수 있다.
시간을 줄이거나 다른 방법을 생각해보자. 확실히 레벨2 부턴 쉽지 않다.
두 번째 아이디어는 슬라이싱을 이용해보았다.
1234567891011121314151617181920212223def solution(number, k):temp = []ind = 0while k > 0:num = number[ind : ind + k + 1]m = max(num)a = num.index(m) + indtemp.append(a)k -= (a - ind)ind = a + 1if k == 1 and ind == len(number) - 1 : breakanswer = ''for i in temp:answer += number[i]if k != 1:answer += number[temp[-1] + 1 : ]return answercs
그러나 '테스트 10'에서 시간 초과가 뜬다. 다른 방법을 찾아야겠다..세 번째 아이디어는 큰 수를 순차적으로 찾고, 그 수의 앞에 있는 수의 개수가 k개 보다 작을 때 제거하기.
def solution(number, k): answer = '' j = 0 h, t = 0, len(number) # head, tail. 밑에 for문의 시작, 끝 while k > 0: if t - h == k: # for문의 범위에서 시작부터 끝까지 원소 개수가 k개랑 같으면 종료. break mx = 0 # 최댓값 for i in range(h, t): # 최댓값 찾기, j는 최댓값의 인덱스 if number[i] == '9': j = i break i_num = int(number[i]) if i_num > mx: mx = i_num j = i if j - h > k: # 최댓값 앞의 수의 개수가 k개 보다 크면 tail을 최댓값 인덱스로 바꾼다. t = j else: # 최댓값 앞의 수의 개수가 k개 이하면 answer += number[j] # 최댓값만 따로 저장 k -= (j - h) # 제거한 수의 개수만큼 k의 수를 조정 h = j + 1 # 새로운 head는 최댓값 다음 인덱스로 조정. answer += number[h + k: ] return answer
결과는 위에서 시간초과 뜬 '테스트 10번'이 통과됐는데 위에서 아슬하게 통과한 '테스트 8번'이 시간 초과다...
아마도 원인은 다음이 아닐까 추측된다. 아래와 같은 테스트는 잘 작동하지만,
아래와 같이 같은 숫자가 많이 반복되면,
연산 횟수가 많이 늘어난다.
줄여 보려고 생각을 많이 해봤는데 잘 안된다.
아예 생각을 바꿔서 큰 원소를 찾아 앞에서부터 순서대로 집어넣는 방식으로 다시 code를 작성해봐야겠다.
'개발자의 길 > Algorithm' 카테고리의 다른 글
소수 만들기 (프로그래머스, 레벨1) (0) 2021.03.27 약수의 합 (프로그래머스, 레벨1), 양의 약수의 합 공식 (0) 2021.03.17 무엇이 추구해야 할 방향인가? (0) 2021.03.10 '하나씩 세는 것이 강력한 방법이다' (0) 2021.03.04 카톡 스터디 시작(알고리즘 매일 한 문제 풀기) (0) 2021.03.01