[프로그래머스] Level 2_예상 대진표(2017 팁스타운)

📌문제 유형

2017 팁스타운

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(79.4)

 - order(num) : a,b를 2로 나누기

• 나눈 값이 짝수이면 그대로 사용, 홀수면 +1

 - log2 : 대진이 발생할 수 있는 최대 횟수

• log함수는 float로 나옴, range 쓰기 위해 int로 바꿔주기

from math import log2

def order(num):
    if num % 2 == 0:
        num = num//2
    else:
        num = num//2 + 1
    return num
        
def solution(n,a,b):
    answer = 1
    k = int(log2(n))     # 대진이 발생할 수 있는 최대 횟수	# log함수는 float로 나옴

    for _ in range(k):
        a = order(a)
        b = order(b)
        
        if a+1 == b or b+1 == a:
            answer += 1
            return answer
        else:
            answer += 1

    return answer

2차 시도 (88.2)

 - 추가 사항

• order(num) : num이 1일때 1 리턴
• 첫 번째에 만나는 경우 answer 리턴

from math import log2

def order(num):
    if num == 1:
        return 1
    elif num % 2 == 0:
        return num//2
    else:
        return (num//2) + (num%2)
        
def solution(n,a,b):
    answer = 1
    k = int(log2(n))     # 대진이 발생할 수 있는 최대 횟수
    
    # 첫번째에 만나는 경우
    if a+1 == b or b+1 == a:
        return answer
        
    for _ in range(k):
        a = order(a)
        b = order(b)
        
        if a+1 == b or b+1 == a:
            answer += 1
            return answer
        else:
            answer += 1

    return answer

3차 시도(통과)

 - k : 대진이 발생할 수 있는 최대 횟수(log2 값은 float)

 - a가 항상 작도록 세팅

 - 첫 번째 만나는 상황

• a가 항상 작기때문에 a+1과 b를 비교
• a,b가 나눈 몫이 다른 경우에만 값 리턴
  • 만약, a =2이고 b = 3인 경우 -> 대진표에서 바로 만날 수 없음 ((1 2 / 3 4) 로 나뉘기 때문)

 -  두 번째 이후부터는 i로 리턴

• a, b값은 (a//2) + (a%2)로 갱신
• 만나는 상황은 상단 방법과 동일

from math import log2
        
def solution(n,a,b):
    k = int(log2(n))     # 대진이 발생할 수 있는 최대 횟수
    
    # a가 더 작도록 만들기
    if a > b:
        a,b = b,a

    # 첫번째에 만나는 경우
    if a+1 == b and a//2 != b//2:
        return 1
        
    for i in range(2,k+1):
        a = (a//2) + (a%2)
        b = (b//2) + (b%2)
        
        if a+1 == b and a//2 != b//2: 
            return i
        else:
            continue

 

📌다른 사람의 풀이

1) 

 - bit_length()

출처: https://codetorial.net/tips_and_examples/int_function.html

23. 파이썬 int() 함수 사용하기 - Codetorial

 - xor : 이진수로 나타내었을때, 각 자릿수 비교하여 다르면 1 같으면 0

파이썬 비트연산자 사용법 정리 (Python 비트연산)

def solution(n,a,b):
    return ((a-1)^(b-1)).bit_length()

2) 나눈 몫을 같게 만든 후, 비교

def solution(n,a,b):
    answer = 0
    while a != b:
        answer += 1
        a, b = (a+1)//2, (b+1)//2

    return answer

 

📌리뷰

 - log함수는 float로 출력된다.

 - 당연한 것도 의심해보기