[프로그래머스]이진 변환

[65] 이진 변환

책 구매하기

문제 정보

• 분류: 시뮬레이션
• 정답률: 76%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 문자열 반복, 0 개수, 이진 변환, 반복 시뮬레이션
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/70129

문제를 읽을 때 체크할 포인트

문자열에서 0을 지우고 남은 1의 개수만큼 다시 이진수 문자열로 바꾸는 과정을 반복하는 문제다. 결국 카운트만 정확히 누적하면 된다.

규칙을 그대로 따라가는 문제처럼 보여도 상태를 어떻게 단순하게 들고 갈지가 더 중요하다. 좌표나 값의 변화만 깔끔하게 관리하면 의외로 짧게 끝난다.

풀이 흐름

1. 문자열이 '1'이 될 때까지 반복한다.
2. 현재 문자열에서 0 개수와 1 개수를 센다.
3. 0 개수는 누적하고, 1 개수를 이진 문자열로 바꿔 다음 단계로 넘긴다.

구현할 때 놓치기 쉬운 부분

변환 횟수와 제거한 0의 개수를 따로 세어야 한다. 문자열 길이만 보거나 1의 개수만 세면 누적 정보가 빠져 결과가 맞지 않는다.

파이썬 정답 코드

def solution(s):
  # 문자열이 '1'이 될 때까지 반복한다.
  transform_count = 0
  removed_zero = 0

  # 현재 문자열에서 0 개수와 1 개수를 센다.
  while s != "1":
    # 0 개수는 누적하고, 1 개수를 이진 문자열로 바꿔 다음 단계로 넘긴다.
    zeros = s.count("0")
    removed_zero += zeros
    ones = len(s) - zeros
    s = bin(ones)[2:]
    transform_count += 1

  return [transform_count, removed_zero]

시간 복잡도

N은 처음 문자열 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.