[Short Code] 숫자를 바라보는 관점에 따른 알고리즘의 변화

부호를 바라본 관점에 따른 알고리즘의 차이

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/76501

해설

absolute에는 어떤 정수의 절대값이 저장되어 있고, signs를 통해 특정 index의 숫자값이 기존에 양수였는지 음수였는지 알 수 있다. signs[i]의 값이 True라면 absolute[i]의 값이 양수고 signs[i]의 값이 Flase라면 absolute[i]의 값이 음수이다.

이때 실제 정수들의 합을 구하는 알고리즘을 구하는 것이 문제이다.

예를 들어 absolute = [4,7,12], signs = [true,false,true] 라면 answer = 4 -7 +12로 답은 9가 된다. 이때 7을 앞에 숫자에서 7을 빼는 것으로 볼것인지 7에 -1을 곱한후 더하는 것으로 볼것인지에 따라서 관점이 달라진다.

전자의 경우로 볼때의 코드는 아래와 같다.

코드

def solution(absolutes, signs):
    answer = 0

    for index, value in enumerate(absolutes):
        if signs[index]:
            answer += absolutes[index]
        else:
            answer -= absolutes[index]

    return answer

후자의 경우로 코드는 아래와 같다. (삼항연산자를 이용)

def solution(absolutes, signs):
    answer = 0

    for index, value in enumerate(signs):
        answer = answer + (absolutes[index] * (1 if value else -1))

    return answer

후자의 경우를 코드로 구현하는 또 다른 방법은 해시를 이용하는 것

def solution(absolutes, signs):
    answer = 0

    check ={True:1,False:-1}

    for index, value in enumerate(signs):
        answer = answer + (absolutes[index] * check[value])

    return answer

나머지를 바라보는 관점에 따른 알고리즘의 차이

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12985

해설

N명이 게임에 참가하고 1<->2, 3<->4, 5<->6, ... N-1<->N 규칙으로 대결을 한다. 그리고 이긴 승자는 다음라운드에 진출하고 다시 번호를 부여 받는다. 이 규칙을 표현하면 다음과 같다.

'''

1 2   3 4   5 6   7 8

  1     2      3     4

     1             2

'''

첫 번째 방식

다음 라운드를 진행할 때마다 바뀌는 번호를 구하는 규칙을 처음에는 다음과 같이 구했다. 현재 번호가 짝수라면 2를 나눈 몫이 다음 라운드 번호이고 홀수라면 1을 더하고 2를 나눈 몫이 다음 라운드 번호이다. 그리고 현재 번호가 짝수라면 자신보다 1이 작은 숫자와 대결하고 홀수라면 자신보다 1이 큰 숫자랑 대결한다.

이 규칙으로 알고리즘을 구하면 다음과 같다.

1. a 숫자가 짝수라면 b의 값이 a-1인지 비교한다. 그리고 같다면 현재 라운드에 대결을 한 것이다. 만약 b와 a-1이 다르다면 다음 라운드로 진행하고 a의 다음라운드 숫자를 a 나누기 2의 몫으로 변경한다.

a 숫자가 홀수라면 b의 값이 a+1인지 비교한다. 그리고 같다면 현재 라운드에서 대결을 한 것이다. 만약 b와 a+1이 다르다면 a의 다음 숫자를 a+1를 2로 나눈 몫으로 변경한다.

현재 라운드에서 a와 b가 대결하지 않은것이라면 b의 숫자도 다음 라운드 숫자로 변경하여야 하는데 위의 짝수, 홀수규칙에 따라 b가 짝수라면 b를 2로 나눈 몫으로 변경하고 b가 홀수라면 b+1을 2로 나눈 몫으로 변경한다.

a와 b가 대결할 때 까지 위 과정을 반복한다.

코드

def solution(n,a,b):
    answer = 0

    for i in range(1,n//2):
        if a%2 == 0:
            if b == a-1:
                answer = i
                break
            else:
                a = a//2
        else:
            if b == a + 1:
                answer = i
                break
            else:
                a = (a+1)//2

        if b%2 == 0:
            b = b//2
        else:
            b = (b+1)//2
    else:
        answer = n//2

    return answer

두 번째 방식

두 번째 방식은 다음 라운드 숫자의 번호를 구하는 규칙이 첫 번째 방식과 다르다. 조금 다른 관점에서 생각하면 코드도 훨씬 간결해진다. 수학을 잘하는 프로그래머가 코드를 잘 짜는 이유이다.

다음 라운드 숫자의 번호를 구하는 규칙은 현재 번호에서 2로 나눈 나머지와 몫을 더하면 다음 라운드의 번호가 된다. 그리고 다음 라운드의 예상 번호가 같다는 것은 현재 라운드에서 대결을 했다는 것이다. 예를 들면 3번과 4번 중에 3번이 이겼다면 다음라운드에 2번이 되고 4번이 이겼어도 2번이 된다.

이런 방식으로 계속 대결을 해나갈때 a,b가 몇 라운드에 대결하게 되는지 구하는 것이다.

위에서 라운드 번호 규칙을 이용해서 알고리즘을 만들면 다음과 같다.

1. a, b의 다음 라운드 번호를 미리 구한다. a의 다음라운드 번호 = a를 2로 나눈 몫 + a를 2로 나눈 나머지, b의 다음 라운드 번호 = b를 2로 나눈 몫 + b를 2로 나눈 나머지

2. 다음 라운드의 a, b 번호를 비교하여 같지 않다면 라운드 값을 하나 증가한다. 그리고 1번으로 돌아간다.

만약 다음 라운드의 a, b 번호를 비교하여 같다면 a, b는 현재 라운드에서 대결을 한 것이다. 라운드 값을 증가하지 않는다. 그리고 1번으로 돌아가지 않고 반복문을 종료한다.

코드

def next_round_number(a,b):
    next = [a//2+a%2, b//2+b%2]

    return next

def solution(n,a,b):
    answer = 1

    next_number = next_round_number(a,b)

    while True:
        if next_number[0] == next_number[1]:
            break
        answer+=1

        next_number= next_round_number(next_number[0], next_number[1])

    return answer