[웅's 프로그래머스] N으로 표현 - 파이썬(python) 풀이

우선 N으로 표현 코드를 설명하기 전, 저의 코드가 그다지 깔끔하고 예술적인 코드는 아니라는 점을 말씀드립니다.. 하지만 이 문제를 풀며 겪었던 생각들과 사고의 과정을 담아보고자 합니다 :)

 

N으로 표현은 코딩테스트 공부를 결심하고 가장 처음으로 풀었던 문제다.

(왜 이런 잘못된 선택을 했을까..)

 

처음에는 곱하기, 나누기, 더하기, 빼기를 다 섞어보며 어떻게든 모든 경우의 수에 부합하는 논리를 만들고자 했으나... 경우의 수가 너무 많다는 것을 깨달았다. 숫자를 자리수로 채울 수도 있는게 컸다. 이렇게 경우의 수가 많은 경우에는 모든 상황을 아우르는 궁극의 알고리즘을 찾아내려 하는 것이 아니라, 해당 문제에서만 가능한 알고리즘을 찾는 것이 바람직 하다는 것을 깨달았다! ( 예전에 수능 수리영역을 공부할 때도 느꼈던... )

 

결국 다른 사람의 조언 덕에 이 문제의 진의(?)를 알 수 있었다. 그리고 문제의 "제한 사항"을 주의 깊게 봐야한다는 것도

출저 : 프로그래머스 "N으로표현" 제한 사항

바로 최솟값이 8보다 클 경우에는 고려하지 않는 다는 점. 

알고리즘 문제를 풀 때는 반드시 반복문을 돌아야 하는데, 어떤 기준으로 반복을 할 것인가? 를 찾는 것이 어려웠다.

이 문제는 사용되는 N 의 개수를 기준으로 반복문을 도는 것이 가장 효율적인 방법이었다. 그리고 위에서 생각한 이 문제에서만 가능한 효율적인 알고리즘이었다.

 

N 을 기준으로 문제를 생각하면

- 만약 N의 개수가 1인 경우 만들 수 있는 자리 수는?

  > 그저 N을 추가하면 된다.

# N = 5 라고 가정했을 때
[5]

- 만약 N의 개수가 2 라면?

  > NN 을 추가한다

  > 1인 경우에 저장된 값과 "더하기, 빼기, 곱하기, 나누기" 를 통해 계산한 값을 추가 한다.

# N=5 라고 가정하면
[55, 10, 0, 25, 1]

- 만약 N의 개수가 3 이라면?

  > NNN 을 추가한다

  > 2인 경우에 저장된 값과 "더하기, 빼기, 곱하기, 나누기" 를 통해....

 

그런데 여기서 든 생각은 '빼기와 나누기의 경우 앞 뒤를 바꾸면 다른 값이 나오지 않나..?' 였다.

 

즉 N=2 인경우 & N=1 인경우 연산과,   N=1 인경우 & N=2인경우 순서를 바꾼 연산을 해줘야 한다는 점이었다.

N=1 일때 요소에서 N=2 일 때의 요소를 뺴는 것과 N=2 일때의 요소에서 N=1 일 때의 요소를 빼는 것은 부호가 다르게 나올 테니... 처음엔 절대값을 쓸까 생각도 했지만 나누기도 있어서 그냥 다 저장하기로 결정~~

 

이러한 논리에 의해서 N 의 개수가 5인 경우를 생각해보면

  > NNNNN 을 추가한다

  > N=1 일때의 리스트와 N=4 일때의 리스트 사이의 사칙연산 => 결과값 저장

  > N=2 일때의 리스트와 N=3 일때의 리스트 사이의 사칙연산 => 결과값 저장

  > N=3 일때의 리스트와 N=2 일때의 리스트 사이의 사칙연산 => 결과값 저장

  > N=4 일때의 리스트와 N=1 일때의 리스트 사이의 사칙연산 => 결과값 저장

 

그리고 N을 증가할 때마다 number 가 리스트 안에 포함됐는지 체크하는 함수를 추가하면 이번 문제를 해결할 수 있다!

 

참고로 나는 푸는데 2틀걸렸다...

list = [0,1,2,3,4,5,6,7,8]

def makeCombins(N):
    temp = []
    for i in range(1, N):
        temp.append([i, N-i])
    return temp

def calculation(temp, i, j):
    temp.append(i+j)
    if i-j > 0:
        temp.append(i-j)
    temp.append(i*j)
    if i%j == 0:
        temp.append(i//j)

def makeList(N, quantity):
    
    if(quantity==1):
        list[1] = [N]
        return [N]
    
    temp = []
    temp.append(getN(N, quantity))
    combins = makeCombins(quantity)
    for combin in combins:
        front = list[combin[0]]
        back = list[combin[1]]
        for i in front:
            for j in back:
                calculation(temp, i, j)

    list[quantity] = temp
    return temp

def getN(N, quantity):
    if(quantity==1):
        return N
    
    return getN(N*10+N%10, quantity-1)

def isPerfect(N, number):
    if number==0:
        return True
    (quotient, remainder) = divmod(number, 10)
    if remainder != N:
        return False
    return isPerfect(N, quotient)


def solution(N, number):
    for i in range(1,9):
        if number in makeList(N, i):
            return i
    
    return -1