[코딩테스트] N으로 표현

문제

---

N으로 표현 문제 바로가기

제출 코드(JAVA)

---

첫번째 코드 제출

    private int n;
    private int target;
    private int answer = Integer.MAX_VALUE;

    public int solution(int N, int number) {
        n = N;
        target = number;
        answer = Integer.MAX_VALUE;
        dfs(0, 0);
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    private void dfs(int count, int prev) {
        if (count > 8) {
            answer = -1;
            return;
        }

        if (prev == target) {
            answer = Math.min(answer, count);
            return;
        }

        int tempN = n;
        for (int i = 0; i < 8 - count; i++) {
            int newCount = count + i + 1;
            dfs(newCount, prev + tempN);
            dfs(newCount, prev - tempN);
            dfs(newCount, prev / tempN);
            dfs(newCount, prev * tempN);

            tempN = tempN * 10 + n;
        }
    }

규칙

• count가 증가하면서 이전 리스트에 사칙연산을 적용하며 탐색

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (5.12ms, 52.4MB)
테스트 2 〉	통과 (5.09ms, 51.8MB)
테스트 3 〉	통과 (6.33ms, 52.2MB)
테스트 4 〉	통과 (5.76ms, 52.1MB)
테스트 5 〉	통과 (5.73ms, 51.4MB)
테스트 6 〉	통과 (4.90ms, 53.1MB)
테스트 7 〉	통과 (5.89ms, 52.9MB)
테스트 8 〉	통과 (5.52ms, 52.4MB)
테스트 9 〉	통과 (2.77ms, 52.7MB)

제출 코드(Python)

---

첫번째 코드 제출

answer = -1


def DFS(n, pos, num, number, s):
    global answer
    if pos > 8:
        return
    if num == number:
        if pos < answer or answer == -1:
            #print(s)
            answer=pos
        return

    nn=0
    for i in range(8):
        nn=nn*10+n
        DFS(n, pos+1+i, num+nn, number, s+'+')
        DFS(n, pos+1+i, num-nn, number, s+'-')
        DFS(n, pos+1+i, num*nn, number, s+'*')
        DFS(n, pos+1+i, num/nn, number, s+'/')


def solution(N, number):
    DFS(N, 0, 0, number, '')
    return answer

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (2509.93ms, 10.3MB)
테스트 2 〉	통과 (2125.87ms, 10.2MB)
테스트 3 〉	통과 (2313.78ms, 10.2MB)
테스트 4 〉	통과 (2486.79ms, 10.1MB)
테스트 5 〉	통과 (2349.62ms, 10.2MB)
테스트 6 〉	통과 (2340.09ms, 10.1MB)
테스트 7 〉	통과 (2482.17ms, 10.2MB)
테스트 8 〉	통과 (2497.02ms, 10.2MB)
테스트 9 〉	통과 (1399.92ms, 10.3MB)

java 풀이와 동일하게 진행했건만 성능에서 큰 차이를 보이고 있다.

두번째 코드 제출

def solution(N, number):
    possible_set = [0,[N]] 
    if N == number: 
        return 1
        
    for i in range(2, 9): 
        case_set = [] 
        basic_num = int(str(N)*i) 
        case_set.append(basic_num)
        
        for i_half in range(1, i//2+1):
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]:
                    case_set.append(x+y)
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            if number in case_set:
                return i
            possible_set.append(case_set)
    return -1 

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (3.72ms, 11MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.06ms, 10.3MB)
테스트 4 〉	통과 (261.75ms, 83.7MB)
테스트 5 〉	통과 (224.59ms, 83.4MB)
테스트 6 〉	통과 (1.09ms, 10.5MB)
테스트 7 〉	통과 (1.04ms, 10.4MB)
테스트 8 〉	통과 (224.83ms, 83.5MB)
테스트 9 〉	통과 (0.00ms, 10.2MB)

DFS가 아닌 DP방식으로 진행하니 성능이 개선되었다..!