Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] 정수 내림차순으로 배치하기

[정수 내림차순으로 배치하기]

Solution. $O(n \lg n)$

def solution(n):    
    return int(''.join(sorted(str(n), reverse=True)))

---

[Middler] 카드 뭉치

[카드 뭉치]

Solution. Two Pointer $O(n)$

def solution(cards1, cards2, goal):
    i = j = 0
    
    for g in goal:
        if i<len(cards1) and cards1[i] == g: i += 1
        elif j<len(cards2) and cards2[j] == g: j += 1        
        else: return "No"

    return "Yes"

• 문제의 설명을 읽고 든 생각은 다음과 같다.
  • 순서대로 한 장씩 사용, 다시 사용할 수 없음 → 💡 단방향으로 순회하면 될 것 같다!
  • 카드를 사용하지 않고 다음 카드로 넘어갈 수 없음, 카드 뭉치의 단어 순서는 바꿀 수 없음 → 💡 단방향으로 순회하면서 두 카드 뭉치에서 사용할 수 있는 카드의 인덱스를 관리하면 되겠다!
• 위 생각 그대로 구현했다. 사용할 수 있는 두 카드에 모두 원하는 단어가 적혀 있지 않은 경우는 만들 수 없는 경우이므로 "No"를 return하고, 반복문을 마칠 때까지 그러한 경우가 없었다는 것은 만들 수 있다는 의미이므로 "Yes"를 return해 준다.
  • 엣지케이스를 생각해 보자. 만약 두 카드에 같은 단어가 적혀있다면, 어떤 뭉치에서 선택했을 땐 불가능한데, 다른 뭉치에서 선택했을 땐 가능한 경우가 존재하지 않을까?
    • 제한사항에 따르면, 두 뭉치에는 서로 다른 단어만 존재하므로 배제해도 된다.
• queue를 이용하여 구현할 수도 있다. 하지만 이는 queue로 바꾸는 데에 $O(n)+O(n)$, 순회하는 데 추가로 $O(n)$이 소요되므로 이 방법보다 시간복잡도상으로 비효율적이다.

---

[Challenger] 가장 큰 수

[가장 큰 수]

• 사실 내 접근을 어떻게 설명해야 좋을지 잘 모르겠어서, 정말 많이 고민했다. 그래서 아예 그냥 의식의 흐름을 작성해보려고 한다.

의식의 흐름

• $n$의 자릿수가 모두 다르기 때문에, 단순히 내림차순으로 정렬하여 풀 수 없다. TC #1) [6, 10, 2]를 내림차순으로 정렬하면 [10, 6, 2]가 되고, 이대로 이어붙이면(재배치하면) 1062가 된다.
  
• 정렬을 했을 때에도 낮은 자릿수를 가진 원소의 가치(잠재력)이 유지되었으면 좋겠다.
  • $6$은 $10$보다 작지만, $6$을 $10$보다 앞에 배치하는 것이 가장 크게 재배치하는 방법이다.
  • 그렇다면 뒤에 $0$을 붙여서 자릿수를 맞추면 해결될까?
    • [3, 31, 35] 에 $0$을 붙여서 자릿수를 맞추고 내림차순으로 정렬하면 [35, 31, 30]이 되고, 이대로 원본을 이어붙이면 35313 이 된다. (35331이 더 크게 재배치하는 방법이므로 틀렸다.)
  • 3이 31보다 더 높은 가치를 가져야 하므로, 원본의 맨 뒷자리 수를 이어붙여서 자릿수를 맞춰주면 될 것 같다.
    • [97, 978] 을 이러한 방법으로 자릿수를 맞추고 내림차순으로 정렬하면 [978, 977]이 되고, 이대로 원본을 이어붙이면 97897 이 된다. (97978이 더 크게 재배치하는 방법이므로 틀렸다.)
  • 97이 978보다 더 높은 가치를 가져야 하므로, 단순히 $9$를 붙여주면 될까?
    • 그건 아닐 것 같다.
      • 81, 818를 생각해 보면, 이러한 방법으로 자릿수를 맞추고 내림차순으로 정렬하면 [819, 818] 이 되고, 이대로 원본을 이어붙이면 81818 이 된다. (81881이 더 크게 재배치하는 방법이므로 틀렸다.)
  • 같은 수를 반복해준다면 가치를 정확히 부여할 수 있다. 원소가 $0$ 이상 $1000$ 이하이므로,
    • 한 자릿수의 숫자는 같은 수를 반복해서 네 자릿수로,
    • 두 자릿수의 숫자는 같은 수를 반복해서 네 자릿수로,
    • 세 자릿수의 숫자는 맨 앞자리 숫자만 붙여서 네 자릿수로,
    • 네 자릿수인 $1000$은 그대로!

Solution 1. $O(n \lg n)$

def solution(numbers):
    new_nums = []
    for n in numbers:
        new_n = str(n)
        while len(new_n) < 4:
            new_n += new_n[:4-len(new_n)]
        new_nums.append((new_n, n))
    
    answer = ''.join(str(n) for _, n in sorted(new_nums, reverse=True))
    return "0" if answer[0] == "0" else answer

• 그대로 구현한 풀이이다.
  • 여기서 주의할 점은, numbers 에 $0$만 존재할 땐 “00” 이 아닌 "0"을 반환해야 한다.
  • 이를 위해 str(int(answer))를 이용해 보았으나, numbers의 길이(개수)가 $1$ 이상 $100000$ 이하이고, 각각의 원소가 $0$ 이상 $1000$ 이하이므로 최악의 경우 int로 바꾸는 데에 40만 번의 연산, 다시 str로 바꾸는 데에 40만 번의 연산을 하게 된다.
    $O(n \cdot \sum_{k=0}^{n-1} (\lfloor \log \max(A_k, 1) \rfloor+1))$
  • leading zeros를 지우기 위해 위 시간의 연산이 소모된다. 따라서 단순히 answer의 맨 앞이 0이라면 "0"을 return하고, 그렇지 않다면 $0$으로 시작되지 않는다는 것이 보장되므로 answer를 그대로 return한다.

Solution 2. $O(n \lg n)$

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

• [다른 사람의 풀이]를 참고해서 개선했다. Solution 1.에서처럼 단순히 한 자리씩 이어붙여서 네 자릿수를 만드는 것이 아닌, 문자열을 세 번 반복해서 정렬한다.
  • 엇 이렇게 하면 $1000$인 경우도 괜찮나? 싶었는데, $1000$의 우선순위는 $0$을 제외하고는 가장 낮기 때문에 괜찮다!

---