[TIL] 자료구조/알고리즘 풀기 (4)

학습 주제

---

1. [Hash] 완주하지 못한 선수

2. [Greedy] 체육복

3. [Sort] 가장 큰 수

4. [Greedy] 큰 수 만들기
   
   

1. [Hash] 완주하지 못한 선수

---

• 풀이

  • N의 크기가 최대 100,000이므로, O(N) 혹은 O(N * log N)의 알고리즘을 구현해야 함

  • 동명이인 조건으로 인해 참가자 별 등장 횟수를 저장해야 함

    • 해시(딕셔너리) 사용
      
      

• 구현

  def solution(participant, completion):
      dict = {}
  
      for p in participant:
          dict[p] = dict.get(p, 0) + 1
  
      for c in completion:
          dict[c] -= 1
  
      for key in dict:
          if dict[key] == 1:
              return key

2. [Greedy] 체육복

---

• 탐욕법(Greedy Algorithm)

  • 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하는 알고리즘

  • 현재의 선택이 마지막 해답의 최적성을 해치지 않을 경우 사용
    
    

• 풀이

  • 각 단계에서 이후의 일은 고려하지 않고, 학생이 옆 학생에게 체육복을 빌릴 수 있는지만 고려

  • 만약 학생 수가 굉장히 많고 reserve는 적을 경우, reserve를 기준으로 문제를 푸는 것이 효과적

    • lost의 경우도 마찬가지
      
      

• 구현

  def solution(n, lost, reserve):
      stu = [1 for _ in range(n + 1)]
  
      for l in lost:
          stu[l] -= 1
  
      for r in reserve:
          stu[r] += 1
  
      for idx in range(1, n):
          if stu[idx] == 0:
              if idx == 1:
                  if stu[idx + 1] >= 2:
                      stu[idx] += 1
                      stu[idx + 1] -= 1                    
  
              else:
                  if stu[idx - 1] >= 2:
                      stu[idx] += 1
                      stu[idx - 1] -= 1
  
                  elif stu[idx + 1] >= 2:
                      stu[idx] += 1
                      stu[idx + 1] -= 1  
  
          else:
              continue
  
          # 마지막 학생이 체육복이 없는 경우
          if stu[-1] == 0 and stu[-2] >= 2:
                  stu[-1] += 1
                  stu[-2] -= 1
  
      count = 0
      for ele in stu[1:]:
          if ele >= 1:
              count += 1
  
      return count

3. [Sort] 가장 큰 수

---

• 풀이

  • 큰 수가 앞에 와야 만들 수가 커지기 때문에, 각 숫자의 첫째 자리가 큰 순서대로 정렬

  • 첫째 자리가 같은 경우, 원소의 최대값이 1000이므로 해당 원소를 반복해서 이어붙인 값의 앞 4자리까지 비교해서 큰 수가 우선순위가 더 높음

    • ex) 3, 30, 34 3 -> 333333... -> 3333
      30 -> 303030... -> 3030
      34 -> 343434... -> 3434

       -> 34, 3, 30순으로 정렬

      
      

• 구현

  def solution(numbers):
      answer = ''
      converted = []
  
      for num in numbers:
          converted.append(str(num))
  
      converted.sort(key = lambda x : (x * 4)[:4], reverse = True)
  
      # 모든 원소가 0으로만 이루어져있는 경우, '0'만 return
      if converted[0] == '0':
          answer = '0'
  
      else:
          for s in converted:
              answer += s
  
      return answer

4. [Greedy] 큰 수 만들기

---

• 풀이

  • 주어진 숫자를 한 자리씩 검사해 현재 숫자보다 작은 이전의 숫자들은 제거하고, 현재 숫자 추가

    • stack 활용
      
      

  • 끝까지 검사했는데 제거할 개수(k)를 다 채우지 못한 경우, 뒤에서부터 남은 개수만큼 제거

• 코드

  def solution(number, k):
      stack = []
  
      for num in number:
  
          # 스택의 최상단부터 검사해 현재 숫자보다 작은 수는 pop()하고 카운트 감소
          while stack and stack[-1] < num and k > 0:
              stack.pop()
              k -= 1
  
          stack.append(num)
  
      # 제거할 숫자가 남았으면 뒤에서부터 제거
      if k > 0:
          stack = stack[:-k]
  
      return ''.join(stack)

메모

---

• dictionary.get(key, default_value)

  • 딕셔너리에 key가 없을 경우 default_value를 넣고, 있을 경우에는 해당 값을 가져옴
    
    

• 집합 정렬

  • ls = sorted(set_A)