[leetcode] 3133. Minimum Array End 풀이

안녕하세요. 오늘은 leetcode에서 3133. Minimum Array End 문제를 풀어봤습니다.

• https://leetcode.com/problems/minimum-array-end/description/

1. 문제

이 문제에서는 두 개의 수 n과 x가 주어졌을 때 다음을 만족하는 수열의 마지막 수를 찾는 문제입니다.

1. 길이 n 짜리 증가 수열을 만들어야 합니다.
2. 1에서 만든 수열 내의 모든 수를 AND 연산했을 때의 결과값은 x여야 합니다.

문제를 이해하는데 도움을 드리고자 용어들을 간단히 설명드리겠습니다.

 

1.1. 수열

수열이란 문자 그대로 숫자들을 나열시킨 것입니다.

 

그냥 아무런 규칙 없이 숫자들을 쓰더라도 수열입니다. 여기서 특징을 가지고 있는 수열들에 이름이 붙습니다.

그 중에서 이 문제에서 사용되는 증가 수열에 대해서 알아보겠습니다.

 

1.2. 증가 수열

증가 수열이란 간단히 말해서 계속해서 증가하는 수열입니다.

• 두번째 수는 첫번째 수보다 크고, 세번째 수는 두번째 수보다 크고, ...

예시를 들어보면 다음과 같습니다.

• 증가 수열 O
  • 1, 2, 3, 4, 5, 6, 7
  • 1, 3, 5, 7, 9, 11
  • 1, 5, 10, 50, 100
• 증가 수열 X
  • 1, 1, 1, 1, 1, 1
  • 1, 2, 2, 3, 4, 5
  • 20, 1, 30, 40, 50

1.3. AND 연산

AND 연산은 일반적으로 사용되지 않는 연산이라서 난해할 수 있습니다만 생각보다 간단합니다.

 

1. AND 연산에 사용되는 두 숫자를 모두 2진법으로로 표현합니다.

2. 두 수가 같은 자리 수에 1을 가지고 있을 때만 1을 남깁니다.

 

AND 연산 예시

• 2 AND 3
  1. 2진법으로 표현하기: 2 => 10, 3 => 11
  2. 두 수가 같은 자리 수에 1을 가지고 있을 때만 1을 남기기: 10 AND 11 => 10
• 3 AND 8
  1. 2진법으로 표현하기: 3 => 11, 8 => 1000
  2. 두 수가 같은 자리 수에 1을 가지고 있을 때만 1을 남기기: 11 AND 1000 => 0
• 3 AND 7
  1. 2진법으로 표현하기: 3 => 11, 7 => 111
  2. 두 수가 같은 자리 수에 1을 가지고 있을 때만 1을 남기기: 11 AND 111 => 11

2. 문제 풀이

이 문제의 핵심은 '수열 내의 모든 수를 AND 연산했을 때의 결과값은 x여야 합니다.' 입니다.

 

위의 예시를 보시면 아시다시피 AND 연산의 결과값은 사용된 수들보다 작거나 같습니다.

이를 통해서 수열 내의 모든 수는 x보다 크거나 같아야 한다는 사실을 알 수 있습니다.

 

그리고 x보다 큰 숫자들도 2진법으로 표현했을 때 x와 같은 자리에 1을 가지고 있어야 한다는 사실을 알 수 있습니다.

예를 들어서 x가 9(2진법으로 표현하면 1001)라면

수열 내의 다른 숫자들을 2진법으로 표현했을 때 xxx1xx1 과 같은 형태를 가져야 하는 것입니다.

 

 

유추해낸 사실들을 종합하여 수열을 만들어보면 다음과 같습니다.

1. x를 2진법으로 표현했을 때 0으로 채워진 부분들을 하나씩 1로 바꾸면서 큰 수를 만듭니다.
2. 만약 1에서 만든 수들로도 n만큼의 수를 채우지 못했으면 x의 앞에 1을 붙입니다.
3. n개의 수를 만들 때까지 1-2를 반복합니다. 

+ 코드

설명을 잘 설명하지 못한 것 같네요...ㅜ

이해하시는데 도움이 될 것 같아 제 풀이도 공유드립니다 🙏

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n = n - 1

        bin_x = bin(x)[2:]
        power = len(bin_x)
        zero_index = []
        for i in range(len(bin_x)):
            if bin_x[len(bin_x) - 1 - i] == '0':
                zero_index.append(i)
        empty_place = pow(2, len(zero_index))

        return x + fill_empty(zero_index, n % empty_place) + pow(2, power) * (n // empty_place)

def fill_empty(zero_index, num):
    result = 0
    bin_num = bin(num)[2:]
    for i in range(len(bin_num)):
        if bin_num[len(bin_num) - 1 - i] == '1':
            result += pow(2, zero_index[i])
    return result