BAEKJOON : 1248 의 궁금증

백준 1248 맞춰봐 문제

• 백준 1248 문제를 풀고 제출한 결과와 코드에 대한 궁금증

궁금증 발견

• 최종으로 제출한 코드는 아래 코드이며 시간은 956ms 만큼 걸렸다. 내가 처음에 구현했던 코드에 좀 더 효율적인 백트래킹 기법을 적용시켜서 3060ms 까지 시간을 많이 단축할 수 있었지만 그럼에도 시간 차이가 상당히 많이 났다. 어느 부분에서 차이가 나길래 시간이 이렇게 시간이 걸리는지 궁금했다

import sys

def check(n):
    temp = 0
    for i in range(n,-1,-1):
        temp += arr[i]
        if temp > 0 and s[i][n] =='+':
            continue
        elif temp == 0 and s[i][n] == '0':
            continue
        elif temp < 0 and s[i][n] =='-':
            continue
        else:
            return False
    return True


def solution(level):
    if level >= n:
        print(*arr)
        exit()
    else:
        if s[level][level] == '0':        # 결과의 level 번째 요소 자리가 0이면
            arr[level] = 0
            if check(level) == True:
                solution(level+1)
        elif s[level][level] == '+':      # 결과의 level 번째 요소 자리가 양수이면
            for i in range(1,11):
                arr[level] = i
                if check(level) == True:
                    solution(level+1)
        else:                              # 결과의 level 번째 요소 자리가 음수이면
            for i in range(-10,0):
                arr[level] = i
                if check(level) == True:
                    solution(level+1)
           

n = int(sys.stdin.readline())
matrix = list(sys.stdin.readline().rstrip())
s = [[0]*n for _ in range(n)]

k = 0
for i in range(n):
    for j in range(i,n):            # (n) 하면 s[1][0] 이 될 수도있음 
        s[i][j] = matrix[k]         # 두 번째 입력으로 들어온 부호배열을 앞에서부터 하나씩 삽입 
        k += 1

arr = [0] * n
solution(0)

코드 비교

• 먼저 가장 차이가 나는 부분은 아래 코드 부분이였다. (왼쪽 952ms, 오른쪽 3060ms)

• 처음에는 별 차이가 없다고 생각했는데, 지금보니 for 문이 중첩된 것만 봐도 차이를 느낄 수 있었다.
• 왼쪽 코드는 n = 9 라고 가정했을 때 뒤에서부터 99,89,79....09 위치에 있는 값들의 누적합을 구한뒤 check 를 수행한다.

s[9][9] -> s[8][9] -> s[7][9] 

• 하지만 왼쪽 코드는 n = 9 라고 가정했을 때 앞에서부터 이미 check를 했던 부분을 불필요하게 다시 계산한다.

s[0][0] -> s[0][1] -> s[0][2] ... -> s[8][8]

잘못된 리팩토링

• 불필요한 작업으로 인해 시간이 오래 걸린 것을 깨닫고 이번에는 코드를 좀 더 이해할 수 있도록 아래와 같이 변경했다.

def check(n):
    for i in range(n):
        temp = sum(arr[i:n])
    
        if temp > 0 and s[i][n-1] =='+':
            continue
        elif temp == 0 and s[i][n-1] == '0':
            continue
        elif temp < 0 and s[i][n-1] =='-':
            continue
        else:
            return False
    return True

• n = 9 라고 가정했을 때 0~8 번째까지의 누적합, 1~8 번째까지의 누적합 ... 이런식으로 누적합을 구해서 check 를 수행하는 것은 동일하다. 하지만 제출한 결과를 보니 시간이 4008ms 으로 오히려 시간이 증가했다.
• 최종 코드에서는 누적합을 구할 때 하나씩 덧셈을 하기 때문에 최대 9번 덧셈을 수행한다면 위에 코드는 누적합을 구할 때마다 0~9, 1~8, 2~7 이렇게 처음부터 다시 덧셈을 수행하므로 시간이 더 걸린 것이였다.

느낀점

• 잘 모르는 상태에서 불필요한 리팩토링은 오히려 독이 되는 것 같다. 가장 기본적이고 기초적인 코드가 최적의 코드가 되는 경우가 많은 것 같다.
• 문제는 한시간안에 PyPy3 를 이용해서 풀긴 풀었지만 만족하지 못해서 제출 빌런으로 삽질을 꽤나 했다.. 개발자에게 필요한 덕목 중 하나는 삽질이라고 생각한다 :)