[프로그래머스 인공지능 스쿨]Day03:파이썬을 무기로, 코딩테스트 광탈을 면하자! (1)

Step 1-1 : 해시(Hash)대표 문제 풀이 : 완주하지 못한 선수

문제의 주어진 조건을 지문으로부터 명확히 알아내는 첫 단계가 매우 중요하다.

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. -> participant 배열의 길이는 1이상 100,000이하
• completion의 길이는 participant의 길이보다 1 작습니다.-> 한명만 완주하지 못함
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다. -> 이게 좀 문제가 될 수 있겠다!

이름이 주어지면 몇번이나 배열에 등장했는지 데이터를 저장하는 구조가 필요하다.
이것이 해시와 밀접한 관련이 있다.

자료구조(와 알고리즘)의 선택

만약 이름 대신 번호가 주어졌다면?
-> 선형 배열(linear array)

• 가능한 모든 이름의 조합의 수를 배열로 나타내려고 하면 영문 26글자에 20자리까지 이름을 만들 수 있으므로 26^20인데, 너무 크다. 배열을 쓸 수 없다!
• 번호 말고 다른 것(예: 문자열)로 접근할 수 있는 좋은 자료구조는 없나요?

해시(Hash)

• 키(key) : 이름을 key라고 하자.
• 해시 테이블(hash table) : 키의 값이 저장되는 공간(매핑되는 공간) 키가 해시 테이블의 몇번째 칸에 위치할지 결정하는 데 hash function이 이용된다.
  해시 테이블의 각각의 칸을 해시 버킷(hash bucket)이라고 한다.
  만약 키의 값들이 같은 해시 버킷에 있는 경우 충돌(collision)이 발생한다.
  
• 같은 버킷 칸에 옆으로 또 다른 버킷 칸을 늘어놓아서 충돌을 해결할 수 있다.

문제의 풀이 - 예제

participant	completion	return
[“mislav”, “stanko”, “mislav”, “ana”]	[“stanko”, “ana”, “mislav”]	“mislav”

participant 배열에서 이름이 나타는 횟수를 센다.
해시 테이블에 다음과 같이 기록한다.

• “mislav” : 2
• “stanko” : 1
• “ana” : 1

completion 배열에서 이름이 나타날 때마다 해시 테이블에서 지운다.

• “mislav” : 1
• “stanko” : 0
• “ana” : 0

따라서 정답은 “mislav”가 된다.

Step 1-2 : Python 풀이 예제 보기

Python 사전(dictionary)

d = {"leo":30, "kiki":62, "eden":5} #사전 정의
x = d["leo"] #"leo"라는 키에 대한 값 접근
d["leo"]=58 #"leo"라는 키에 새로운 값 삽입

파이썬에서는 사전을 구현할 때 내부적으로 해시테이블을 이용하기 때문에, 사전의 원소들을 해시를 이용해 O(1) 시간에 접근 가능

def solution(participant, completion):
    d = {} # 빈 사전 만들기
    for x in participant:
        d[x] = d.get(x, 0)+1 
        # 사전에서 주어진 키 x가 존재하면 그 키에 해당하는 값을, 만약 존재하지 않다면 0을 리턴하는 메소드 get
        # participant에 있는 이름 x가 처음 등장하면 1로 만들고, 처음 등장하는 이름이 아니면 원래 있는 개수 +1해서 사전에 집어넣는다.
        # 이 순환문의 시간복잡도는 participant 배열 길이에 비례한다. 파이썬에서 사전을 해시테이블로 만들기 때문에 상수 시간이 되기 때문!

    for x in completion:
        d[x] -= 1
        # completion에 있는 이름을 사전에서 하나씩 제거해준다.
        # 이 순환문의 시간복잡도는 completion 배열 길이에 비례한다.
    
    dnf = [k for k, v in d.items() if v > 0]
    # 완주하지 못한 사람 리스트에 저장.
    # d라는 사전에 들어있는 모든 원소를 나열하고, 각각에 대해서 if의 조건이 만족하는 경우에 원소들을 골라서 리스트로 만들어내는 연산이다.
    # 사전의 크기에 비례하는 복잡도를 가진다. 즉 participant 배열 길이에 비례한다.
    
    answer = dnf[0]
    # 1명이 완주하지 못했으므로 첫번째의 원소를 꺼낸다.
    return answer

participant 배열 길이가 n일 때, O(n)의 시간복잡도를 가진다! (선형 시간 복잡도를 가진다.)

정렬을 이용한다면?

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

sort의 복잡도는 O(NlogN)이다. 정렬을 이용해서 풀면 선형 시간 복잡도를 가지지만, 정렬을 이용하면 테스트는 통과하지만 복잡도는 더 크다.

Step 1-3 : 풀어서 내걸로 만들자! “완주하지 못한 선수”

def solution(participant, completion):
    answer = ''
    d = {}
    for i in participant: # participant의 이름을 키값으로 갖는 사전생성
        d[i] = 0
    for name in participant: # participant에 있는 이름의 개수를 사전에 값으로 넣기
        d[name] += 1
    for comp in completion: # completion에 있는 이름은 사전에서 개수를 빼준다.
        d[comp] -= 1
    for dnf in d: # 사전에 있는 키의 값이 1인 것을 answer에 담아 출력
        if d[dnf] == 1:
            answer = dnf
    return answer

Step 2-1 : 탐욕법(Greedy) 대표 문제 풀이 : 체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

문제의 해결 - 예제

n = 5
reserve = [1, 3, 5], 빌려줄 학생들 : 1 3 5
lost = [2, 4], 빌릴 학생들 : 2 4
answer = 5 (모든 학생들이 다 빌릴 수 있음!)
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

탐욕법(Greedy Algorithm)

알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
탐욕법으로 최적해를 찾을 수 있는 문제 : 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때.

탐욕법 적용 가능성 확인

이 문제에서 탐욕법을 적용하려면
빌려줄 학생들을 “정해진 순서”로 살펴야 하고, 이 “정해진 순서”에 따라 우선하여 빌려줄 방향을 정해야 함.

문제의 해결 - 방법(1)

(착안점) 학생의 수는 기껏해야 30!
학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
-> 번호 순서대로 “스캔”하면서 빌려줄 관계를 정한다
n = 10, lost = [1,5,8,3,7], reverse = [7,5,2,9,6]

    1   2   3   4   5   6   7   8   9   10
1   1   1   1   1   1   1   1   1   1   1   1 
-> 무조건 1로 초기화해주기. 매 단계에서 내 앞의 번호, 뒤의 번호를 살펴봐야 하므로 앞뒤에 허깨비 1을 붙여준다.(고려하지 않는 것으로 치기 위해)
1   1   2   1   1   2   2   2   1   2   1   1 
-> 체육복 가져온 사람 1씩 늘려주기(앞과 뒤의 1은 허깨비)
1   0   2   0   1   1   2   1   0   2   1   1 
-> 도난당한 체육복 1씩 감소
1   1   1   0   1   1   2   1   1   1   1   1 
-> 번호가 작은 쪽부터 살펴나가서, 여분이 있는 사람은 번호가 작은 사람에게 한벌을 빌려주게 한다.
-> 2번이 1번에게 빌려주고, 2번이 8번에게 빌려준다.

따라서 정답은 9!

알고리즘의 복잡도

• 여벌을 가져온 학생 처리 : reserve의 길이에 비례
• 체육복을 잃어버린 학생 처리 : lost의 길이에 비례
• 체육복을 빌려주기 처리 : 전체 학생 수 (n)에 비례 -> O(n)
  선형 시간 복잡도를 가진다! 아주 훌륭한데, 조금 걸리는 부분이 있다…
  

문제의 해결 - 방법(2)

만약 전체 학생 수가 매우 크다면? 방법 1보다 더 효율적인 방식을 찾아야 한다!

• 하지만 문제의 성질상 O(n)보다 낮은 복잡도 알고리즘은 어려울 듯?

그런데 여벌의 체육복을 가져온 학생은 매우 적다면?

• 여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬하고, -> 정렬을 하므로 O(klogk)
• 이것을 하나 하나 순서대로 살펴보면서
• 빌려줄 수 있는 다른 학생을 찾아서 처리한다! -> 해시를 적용해서 상수 시간에 처리!

n = 10, lost = [1,5,8,3,7], reserve = [7,5,2,9,6]
n = 10, lost = [1,5,8,3,7], reserve = [2,5,6,7,9]

reserve : 2   5   6   7   9
lost : 1   5   8   3   7
-> 5번과 7번이 lost와 reserve에 모두 들어있으므로 빼준다.
reserve : 2   6   9
lost : 1   8   3
-> 2번은 바로 앞의 1을 빌려줄 수 있으므로 lost에서 1을 뺀다.
reserve : 2   6   9
lost : 8   3
-> 6번은 5번에게 빌려줄 수 있는데 lost에 없다.
-> 7번도 lost에 없다
-> 9번은 8번에게 빌려줄 수 있는데 lost에 있으므로 lost에서 8을 빼준다.
reserve : 2   6   9
lost : 3
---
answer = 10-1(3번) = 9

방법 1과 완전히 동일한 동작을 한다.

알고리즘의 복잡도

여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬
-> O(klogk)
체육복을 빌려줄 수 있는 학생을 찾아 처리
-> O(k)*O(1)
전체 알고리즘의 시간 복잡도
-> O(klogk)

Step 2-2 : Python 풀이 예제 보기

방법 1 구현

def solution(n, lost, reserve):
    u = [1]*(n+2)#바운더리 체크하는 번거로움을 줄이기 위해 앞뒤로 한칸 더 만든다. 
    for i in reserve: # 여벌로 가져온걸 +1
        u[i] += 1
        # 이 순환문은 reserve의 길이에 비례하는 복잡도 O(n)
    for i in lost: # 도난당한걸 -1
        u[i] -= 1
        # 이 순환문은 O(n)
    for i in range[1, n + 1]:
        if u[i - 1]==0 and u[i]==2:#앞의학생이 체육복이 없고 뒤에있는 학생이 체육복이 있으면
            u[i-1:i+1] = [1, 1] # i-1번 원소와 i+1을 모두 1로 만든다
        elif u[i]==2 and u[i+1] == 0:#내가 체육복을 가지고 있고 뒤의 학생이 체육복이 없으면
            u[i:i+2] = [1, 1]
        #이 순환문은 O(n)
    return len([x for x in u[1:-1] if x>0])
    # u에 들어있는, 1부터 맨 마지막 하나 전까지의 원소를 꺼내는데, 단 그 원소의 값이 0보다 큰것들의 길이만 반환
    # 리턴문의 복잡도도 O(n), n에 비례한다.

전체 알고리즘의 복잡도는 O(n)인 선형 복잡도를 가진다.
만약 학생수가 1억명 이렇게 많은데 체육복 가져온 사람은 20명이라면, 위의 코드에서 7~11행의 루프를 학생수만큼 돌리는데 굉장히 낭비스럽다.
이를 위한 방법 2를 구현하면..

방법 2 구현

구현은 방법 1보다 간단하다.
집합연산을 이용하는게 특징이다.
방법 1과 달리 n명의 학생을 전부 살펴보는게 아니라, 여벌의 체육복을 가져온 학생들만 고려하기 때문에 전체 학생 수에 비해 여벌의 체육복을 가져온 학생수가 아주 적을 경우 유용하다.

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    # set, 집합을 &으로 연결하면 이 두 집합의 교집합을 뜻한다. 교집합을 s에 담는다. s는 여분의 체육복이 있는데 도난당한 학생.
    # set의 복잡도는 배열 길이에 비례한다.
    l = set(lost) - s # lost는 체육복을 도난당한 학생-reserve에도 있는 학생(빌릴 필요 없는 학생) 이렇게 차집합 연산! l은 체육복이 0개인 학생.
    r = set(reserve) - s # 여분이 있는 학생 - 여분의 체육복이 있는데 도난당한 학생. r은 체육복을 빌려줄 수 있는 학생.
    # set의 복잡도는 배열 길이에 비례한다.
    for x in sorted(r): # O(klogk)
        # 조건 중요하다!! 오름차순으로 먼저 살펴보고, 그다음 내림차순으로 살펴봐야 한다.
        if x - 1 in l:#나보다 번호 작은 학생이 체육복을 도난당한 학생이면
            l.remove(x-1)
        elif x+1 in l:#나보다 번호 큰 학생이 체육복을 도난당한 학생이면
            l.remove(x+1)
    return n-len(l) #전체 학생에서 체육복 0인 학생들 빼준걸 리턴!

알고리즘의 복잡도는 O(klogk)이다.

Step 2-3 : 풀어서 내걸로 만들자! “체육복”

나는 방법 1이 직관적으로 이해하기 쉬워서, 나한테 편한 방식으로 풀어보았다.

def solution(n, lost, reserve):
    answer = 0
    u = [1]*(n+2) # 학생의 유니폼 소지 여부 모두 1으로 초기화
    for r in reserve: # 여벌 갖고 있는사람 +1
        u[r]+=1
    for l in lost: # 도난당한 사람 -1
        u[l]-=1
    for i in range(len(u)): #  여분이 있는 사람은 자기보다 번호가 작은 사람에게 한벌을 빌려줌
        if u[i]==0 and u[i+1]==2:
            u[i]+=1
            u[i+1]-=1
    for i in range(len(u)):#  여분이 있는 사람은 자기보다 번호가 큰 사람에게 한벌을 빌려줌
        if u[i]==2 and u[i+1]==0:
            u[i]-=1
            u[i+1]+=1
    # print(u)
    for j in range(len(u)):
        if u[j]!=0:
            answer +=1
    return answer-2

Step 3-1. 정렬(Sort) 대표 문제 풀이 : 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

문제의 해결 방법

1. 빈 문자열로 수를 초기화한다
2. 가장 크게 만들 수 있는 수를 고른다.
3. 그 수를 현재 수에 이어 붙인다.
4. 모든 수를 다 사용할 때까지 반복한다.

예제에 적용

[3, 30, 34, 5, 9] "" <- 빈 문자열 초기화
[3, 30, 34, 5] "9" <- 앞의 숫자가 제일 큰 9를 선택
[3, 30, 34, 5] "95"
[3, 30] "9534"
[30] "95343"
[] "954330"

각 단계에서 목록 안에 있는 것중에 수를 가장 크게 만드는 것을 찾아내는 작업이 목록의 길이에 비례한다. 그리고 그 단계를 목록 안에 들어있는 수의 개수만큼 수행해야 하므로 O(n^2)의 복잡도를 가지게 한다.
따라서 이보다 더 나은 방법을 찾아야 하는데, 바로 sort이다!

(조금 나은) 문제의 해결 방법

1. 빈 문자열로 수를 초기화한다.
2. 수의 목록을(크게 만드는 것 우선으로) 정렬한다.
3. 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
4. 모든 수를 다 사용할 때까지 반복한다. -> O(nlogn)의 복잡도를 가진다.
   

“크게 만드는 수”의 기준

34의 경우 결과의 수를 가장 크게 만드는 것 우선으로 정렬이 다 되어있디고 가정하면, 34보다 뒤에 올 수 있는 것은 커 봐야 34를 넘지 못한다. -> 34343434…
343의 경우, 343343343343…이 가장 크게 만들 수 있는 패턴이다.
문제에서 numbers의 원소는 1000 이하이므로(각 숫자는 4자리를 넘지 않음!) 각각 3434, 3433이고, 따라서 34 vs 343이면 34가 결과를 더 크게 만든다.

알고리즘 설계 -> 구현

• 대소 관계 비교를 위한 기준을 마련
• 이것을 이용하여 주어진 배열을 정렬
• 정렬된 배열을 이용하여 문자열 표현을 완성

Step 3-2. Python 풀이 예제 보기

def solution(numbers):
    numbers = [str(x) for x in numbers] # 문자열로 변환. O(n)복잡도를 가진다.
    numbers.sort(key=lambda x : (x*4)[:4], reverse = True) # x라는 원소가 주어지면 4번 반복하고 앞에서 4개까지를 슬라이스해서 딱 4개에 맞게 떨어지도록 만든다. 그리고 내림차순으로 정렬한다. O(nlogn)복잡도를 가진다.
    if numbers[0] == '0':
        answer = '0'
        # 만약 0만 두개 이상 들어있는 배열이 주어진다면, 00, 0000 이런게 나오게 될텐데, 그럴때는 0 한글자로 이루어진 문자열을 리턴하게 해야한다.
    else:
        answer = ''.join(numbers)
    # if에 의한 수행은 O(n)
    return answer

-> 정렬에 따라 O(nlogn)의 복잡도를 가진다!

Step 3-3. 풀어서 내걸로 만들자! “가장 큰 수”

풀이 강의를 듣지 않고 풀었을때는 이렇게 했는데, 정확성 테스트를 다 통과하지 못했다.

def solution(numbers):
    answer = ''
    d = {} # 원래의 숫자가 키, 변형된 숫자가 값으로 들어갈 사전
    origin = list(map(str, numbers)) # 원래의 수를 담아둘 오리진 배열
    numbers = list(map(str, numbers)) # numbers의 숫자를 문자열로 바꿈
    for i in range(len(numbers)):
        numbers[i]=numbers[i]*3
        numbers[i]=numbers[i][:4]
        d[origin[i]] = numbers[i]
    print(numbers)

    d = sorted(d.items(), reverse=True, key=lambda item:item[1]) # 딕셔너리의 값을 기준으로 내림차순 정렬
    print(d)
    for i in range(len(d)):
        answer += d[i][0]

    return answer

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x : (x*4)[:4], reverse = True)
    if numbers[0] == '0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer

lambda 함수 쓰는 법에 좀더 익숙해져야겠다. 정말 간편하게 기능 압축을 할 수 있다.

람다(lambda)

함수를 딱 한 줄로 만들게 해주는 아주 편리한 람다 형식!

lambda 인자 : 표현식

두 수를 더하는 함수가 다음과 같을때,

def plus(x,y):
    return x+y

람다 형식으로 쓰면 다음과 같다.

(lambda x,y: x+y)(10,20)

이번 코드에서

numbers.sort(key=lambda x : (x*4)[:4], reverse = True)

의 경우, key를 lambda x : (x4)[:4]로 해서, 즉 key를 문자열을 4번 반복한 후 4번째 자리까지 자른 것으로 해서 그 기준으로 numbers를 정렬하게 한다. numbers내부의 숫자를 (x4)[:4]로 바꾸지 않고 정렬해줘서 간편하다.

Step 4-1: 탐욕법(Greedy)대표 문제 풀이 : 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

큰 수 만들기 - 원칙

• 앞 자리에 큰 수가 오는 것이 전체를 크게 만든다.
  • 따라서, 큰 것을 우선해서 골라 담고 싶다.

예제 살펴보기 (1)

number = “1924”, k = 2 -> 94가 제일 큰 수

예제 살펴보기 (2)

number = “1231234”, k = 3 -> 3234가 제일 큰 수

예제 살펴보기 (3)

number = “4177252841”, k = 4 -> 775841가 제일 큰 수

작은 것을 빼되, 앞에서부터 빼는 것이 유리하다. 앞에서부터 작은 수를 빼는 것이 유리하다.

큰 수 만들기 - 방법

• 앞 자리에서부터 하나씩 골라서 담되,
  • 지금 담으려는 것보다 작은 것들은 도로 뺀다!
  • 단, 뺄 수 있는 수효에 도달할 때까지만 즉,
• 큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록
  • (제약조건)뺄 수 있는 수의 개수

주의할 점

number = “98765”, k = 2
이미 큰 것 -> 작은 것 순서대로 놓여져 있기 때문에 앞자리에서부터 차례로 보면서 뒷자리가 클때 삭제하는 방법을 쓸 수 없다. 이런 경우, 뒷자리에서 두개를 제거해서 987을 만들어야 한다.

알고리즘 설계 -> 구현

• 주어진 숫자(number)로부터 하나씩 꺼내어 모으되
  • 이때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다.
• 이렇게 모은 숫자들을 자릿수 맞추어 반환한다.
  • 아직 뺄 개수(k)를 채우지 못한 경우
  • 위의 주의할 점에 따라, 맨 뒤에서 뺄 개수만큼 제거해준다!

알고리즘의 복잡도

매 수를 다 더할때 지금까지 나와있는 수를 비교하면서 빼고/안빼고를 반복하므로 하나를 뺄 때마다 O(n^2)라고 생각할 수 있지만, 그렇지 않다. 수의 자릿수에 비례하는 선형 알고리즘으로, O(n)이다. 모든 각각 자리의 수는 더해지고 빼지는게 기껏해야 한번씩이므로 O(n)이다.

탐욕법(Greedy Approach)

• 앞 단계에서의 선택(앞 자리에 큰 수!!)이 이후 단계에서의 동작에 의한 솔루션의 최적성에 영향을 주지 않음!
• 앞자리의 수를 결정할때 먼저 나온 작은 것부터 k개를 채울 때까지 탐욕스럽게 빼는 것이다. 현재 상태에서 가장 빼고 싶은 것들만 빼는 것이다. 이후에 어떻게 최적화에 영향을 줄지는 고려하지 않는다! 따라서 탐욕법을 적용해서 풀 수 있다.

Step 4-2 : Python 풀이 예제 보기

def solution(number, k):
    collected = [] # 숫자를 하나씩 모아서 큰 수를 만드는 데 쓸 것이다. 문자열을 사용할 수도 있지만, 파이썬에서는 inmutable(불변)의 특성을 가지고 있기 때문에 리스트가 편하다!

    #enumerate함수는 순서가 있는 자료형의 index번호 와 index값 을 반환한다.
    for i, num in enumerate(number):#이 가장 바깥쪽 순환문이 전체 알고리즘의 복잡도를 결정한다. O(n)
        while len(collected) > 0 and collected[-1] < num and k > 0:#지금 꺼낸 숫자가 전에 쌓아놓은 숫자의 마지막보다 크면 쌓아놓은 마지막 숫자를 뺀다.
            collected.pop()
            k -= 1
        if k == 0: # 빼야하는 숫자를 다 빼면, 나머지 숫자들을 이어붙여준다.
            collected += list(number[i:])
            break
        collected.append(num) #현재 꺼낸 문자인 num을 맨 끝에 이어붙여 준다.
    
    collected = collected[:-k] if k>0 else collected #뒤에서 k개만큼의 글자를 끊어서 버림. 단, k가 0 이상일 때! k가 이미 0이면 그냥 collected를 반환.
    answer = ''.join(collected)
    return answer

Strep 4-3 : 풀어서 내걸로 만들자! “큰 수 만들기”