100일 동안 매일 알고리즘을 하면? - 13일차

100일 동안 매일 알고리즘을 하면? - 13일차

 

 

https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

 

큰수 만들기문제는 오름차순및 내림차순을 활용한 문제였다.

이 문제에서 12번 테스트케이스 "999",2 를 통과하지 못했었다. 테스트를 통과하지 못했던 이유는 오름차순, 내림차순에만 신경쓰다보니 같은 숫자가 나왔을때 k 값을 어떻게 처리해야 하는지에 대해서는 고려하지 않았던게 패인이였다.

 

오름차순, 내림차순으로 값을 처리할때는 계속 같은 값이 나오는 상황을 반례로 만들어놓고 풀자.

def ans(deleted, number):
    answer = "";
    for idx,v in enumerate(deleted):
        if (not v):
            answer += number[idx];
    return answer;

def solution(number, k):
    deleted = [0] * (len(number));
    for i in range(len(number) - 1):
        if (number[i] >= number[i + 1]):
            continue;
        else:
            target = number[i+1];
            for j in range(i, -1, -1):
                if (deleted[j]):
                    continue;
                if number[j] < target:
                    k -= 1;
                    deleted[j] = 1;
                    if (k == 0):
                        return(ans(deleted, number));       
                else:
                    break;
    if (k > 0):
        ret = ans(deleted, number);
        return ret[0:len(ret) - k];

https://programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

def solution(people, limit):
    people.sort(reverse=True);
    k = 0;
    m = len(people) - 1;
    answer = 0;
    while (k < m):
        if people[k] + people[m] > limit:
            k += 1;
        elif people[k] + people[m] <= limit:
            k += 1;
            m -= 1;
        answer += 1;
    if (k == m): answer += 1;
    
    return answer