#30 [파이썬] 프로그래머스: N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

해결 과정

• 1~8개의 N을 사용할 수 있다. 사용 개수에 따라 가능한 모든 경우를 저장한 후, number가 있는 지 없는 지 판단한다.
• 사용 개수를 key, 가능한 경우를 value로 하여 dictionary를 만든다.
• 5, 55, 555, 5555와 같이 연산이 아닌 단순히 이어붙인 경우는 따로 미리 포함시킨다.
• 첫번째 for문은 1~8개를 차례대로 고려하는 것이다. (최솟값을 찾는 것이므로 작은 수 부터)
• 두번째 for문을 이해하기 위해서는 아래 예시를 이해해야 한다.
  • [3개 경우]
    • 1개 리스트 원소 (+, -, *, //) 2개 리스트 원소
    • 2개 리스트 원소 (+, -, *, //) 1개 리스트 원소
  • [4개 경우]
    • 1개 리스트 원소 (+, -, *, //) 3개 리스트 원소
    • 2개 리스트 원소 (+, -, *, //) 2개 리스트 원소
    • 3개 리스트 원소 (+, -, *, //) 1개 리스트 원소
• 예를 들어, 4개로 만들 수 있는 경우를 고려해보자.
• 두번째 for문은 1개부터 최대 3개로 만들어진 원소와 결합할 수 있음을 나타낸다. (피연산자 리스트1로 명명)
• 세번째 for문은 피연산자 리스트1의 모든 원소와 계산하기 위한 루프이다.
• 네번쨰 for문은 피연산자 리스트2의 모든 원소와 계산하기 위한 루프로, (4개 - 피연산자 리스트1 개수)로 두어 총 개수가 4개로 일치하도록 한다.

 

---

 

 

1. 첫번째 풀이 (number > 0 고려 안 함)

• 최대 시간 17.03ms

from collections import defaultdict

def solution(N, number):
    s = defaultdict(set)

    for i in range(1, 9):
        s[i].add(int(str(N)*i))
        for j in range(1, i):
            for n1 in s[j]:
                for n2 in s[i-j]:
                    s[i].add(n1 + n2)
                    s[i].add(n1 - n2)
                    s[i].add(n1 * n2)
                    if n2 != 0:
                        s[i].add(n1 // n2)
        if number in s[i]:
            return i
    return -1

 number가 1이상인 것을 고려하지 않아서 각 리스트에는 무수히 많은 음수가 들어있다. 따라서 number를 찾는 과정이 그만큼 오래 걸리므로 최대 17.03ms로 비교적 시간 복잡도가 크다.

 

---

 

2. 두번째 풀이 (모든 조건 고려하였으나 if문 남발.. 시간은 제일 빠름)

• 최대 시간 9.06ms

from collections import defaultdict

def solution(N, number):
    s = defaultdict(set)
    for i in range(1, 9):
        s[i].add(int(str(N)*i))
        for j in range(1, i):
            for n1 in s[j]:
                for n2 in s[i-j]:
                    plus = n1 + n2
                    if plus > 0:
                        s[i].add(plus)
                    minus = n1 - n2
                    if minus > 0:
                        s[i].add(minus)
                    multiplication = n1 * n2
                    if multiplication > 0:
                        s[i].add(multiplication)
                    if n2 != 0:
                        div = n1 // n2
                        if div > 0:
                            s[i].add(div)
        if number in s[i]:
            return i
    return -1

계산한 후 1이상인 경우만 add하여 number를 찾을 때 불필요한 경우를 탐색하지 않는다. 하지만 if문을 너무 많이 썼다.. (좋은 방법 있으면 댓글 달아주세요!)

 

---

 

3. 세번째 방법 (위의 if문 남발을 개선함. 시간은 조금 더 걸리지만 첫번째 방법보다는 훨씬 빠름!) 

• 최대 시간 11.66ms

from collections import defaultdict

def solution(N, number):
    s = defaultdict(set)
    for i in range(1, 9):
        s[i].add(int(str(N)*i))
        for j in range(1, i):
            for n1 in s[j]:
                for n2 in s[i-j]:
                    operate = [n1 + n2, n1 - n2, n1 * n2]
                    if n2 != 0:
                        operate.append(n1 // n2)
                    for op_i in operate:
                        if op_i > 0:
                            s[i].add(op_i)
        if number in s[i]:
            return i
    return -1

if문 폭탄을 지우고 양수 체크하는 코드를 하나로 합쳤다. 사칙연산을 리스트에 넣은 후 하나씩 1이상인지 체크한 후 add한다. 연산을 하고 나서 양수 체크 후 바로 add하는 것이 아니라, 사칙연산 리스트를 다 만들고 나서 다시 하나씩 꺼내어 양수 체크하고 add하므로 두번째 방법보다 시간은 조금 더 걸린다. 하지만 첫번째 방법과 비교하면 훨씬 빠르다!