알고리즘(Python)

기린이·2021년 5월 9일
0

가장 큰수

문제링크

원래 접근(0 패딩)

def solution(numbers):
    # 같은 길이로 패딩
    numbers.sort()
    pad_num = []
    nums = list(map(str, numbers))
    m = max(nums, key=lambda x: len(x))
    m = len(m)
    for i in nums:
        if len(i) < m:
            pad_num.append(i + ('0' * (m - len(i))))
        else:
            pad_num.append(i)
    pad_num = list(map(int, pad_num))
    # 크기비교하고 큰 순서대로 결합(자릿수가 적은 것을 우선적으로 오게 맨앞에서 소팅)
    rank = sorted(range(len(pad_num)), key=pad_num.__getitem__, reverse=True)

    r = ''
    for ii in rank:
        r += nums[ii]
    return r

위와 같이 시도해봤으나 반례 존재.

'15', '151' 이 있다면 나는 '15115'로 나올 것이다. 그러나 올바른 답은 '15151'이다.

완전탐색

별다른 풀이방법이 생각나지 않아서 완전탐색을 시도.

import itertools
def solution(numbers):
    npr = itertools.permutations(numbers, len(numbers))
    
    ans = []
    for i in npr:
        ans.append(''.join(map(str, i)))
    ans = list(map(int, ans))
    m = max(ans)
    return(str(m)) 

시간초과

솔루션 참고(원소 그 자체를 패딩)

def solution(numbers):
    pad_num = []
    nums = list(map(str, numbers))
    for i in nums:
        pad_num.append(i + (i *3))
    rank = sorted(range(len(pad_num)), key=pad_num.__getitem__, reverse=True)
    r = ''
    for ii in rank:
        r += nums[ii]
    return str(int(r)) 
  1. 만약에 원소 그 자체를 반복해야한다는 것

  2. 원소를 반복하는 횟수도 원소의 길이에 상관없이 원소는 0 이상 1000이하이므로 동일하게 3으로 해주면 된다는 것

  3. '000'을 int를 사용해서 0으로 만들면 된다는 것

위 세가지를 깨달았다면 작성했을 코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

똑같은 접근 매우 간단함
참고

2시간 20분 정도 소요


H-Index

def solution(citations):
    citations.sort(reverse=True)     
    for i in range(citations[0], -1, -1):
        cnt = 0
        for ii in range(len(citations)):
            if citations[ii] >= i:
                cnt += 1
        if i <= cnt:
            return i

문제만 이해하면 쉬운 문제

  1. h는 꼭 인용수리스트에 포함된 수가 아니어도 된다.

  2. [0,0,0] 인용횟수가 모두 0이라면 답은 0

profile
중요한 것은 속력이 아니라 방향성

0개의 댓글