12025 장난꾸러기 영훈 비트마스킹

좋다고 말로만 들었던 비스마스킹 문제를 풀어보았다. 경우의 수가 두 가지 있는데, 해당 내용을 기록해두어야 하는 경우에 사용하면 유용할 것이라고 생각이 들었다.

해당 문제를 보면 특정 수열이 있고, 이 수열 중의 특정 문자는 바뀌었거나, 바뀌지 않았거나 둘 중의 하나이다.

그리고 이 수열이 가장 작을 경우부터 가장 큰 경우까지 만들어지는 경우의 수가 있는데, 이 중 가장 작은 경우의 k번째의 수열을 구하는 문제이다. 즉 바뀌어버린 비밀번호는 내가 가장 작은 경우의 수를 구하기 위해 사용한다. 그리고 k를 이진수로 바꾸어 해당 비트를 포인터로 이동시키면서 바꾸어야 하는 숫자를 찾는 문제이다.

def solution():
    s = input()
    k = int(input())
    binary = bin(k-1)
    bit = ""
    answer =""

    count = 0
    p = len(binary)-1 # 비트 포인터
    for i in s: # 가장 작은 경우를 만드는 for문
        if i == "1" or i == "2": 
            count += 1
        if i == "6":
            bit += "1"
            count += 1
        elif i == "7":
            bit += "2"
            count += 1
        else:
            bit += i
            
    if k > 2**count: # 바꿀 수 있는 비트 수보다 k가 크면 존재하지 않는 k
        print(-1)
        return

    for i in bit[::-1]: # 수열을 뒤집어서 뒤부터 실행
        if i == "1": # 숫자가 1인지 2인지 확인
            if binary[p] == "1": # 비트가 1이라면 뒤집어야 함
                answer = "6" + answer
                p -= 1
            elif binary[p] == "0": # 비트가 0이면 그대로 지나감
                answer = i + answer
                p -= 1
            else:
                answer = i + answer
        elif i == "2":
            if binary[p] == "1":
                answer = "7" + answer
                p -= 1
            elif binary[p] == "0":
                answer = i + answer
                p -= 1
            else:
                answer = i + answer
        else:
            answer = i + answer
    print(answer)

    return

solution()