[Interview] a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자

a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자

a, b, c, d는 자연수이므로 a^3 + b^3의 결과도 어떤 자연수 x로 표현할 수 있다. 즉, 아래와 같이 표현할 수 있다.

a^3 + b^3 = c^3 + d^3 = x

다시 바꾸어 말하면, 어떤 자연수 x는 위 조건을 만족하는 두 자연수의 쌍의 집합으로 표현할 수 있다.

a^3 + b^3 = c^3 + d^3

 = x1 [(a11^2 + b11^2), (a12^2 + b12^2), ...]

 = x2 [(a21^2 + b21^2), (a22^2 + b22^2), ...]

 = x3 [(a31^2 + b31^2), (a32^2 + b32^2), ...]

 = ...

이제 우리는 위 형태의 자료구조를 만들고 집합의 size가 1보다 큰 경우를 검사하여 그것들을 출력하면 된다.

어떤 자료구조를 사용할 것인가? 자료구조는 도구이다. 쓰임새에 적합한 도구를 찾아야 한다.

대략적인 구현 알고리즘을 플로우차트로 그려보자.

for loop로 중복되지 않는 두 자연수의 조합을 만들자

 -> a^3 + b^3 연산

 -> 연산 결과가 이미 존재하면 -> 원소 추가

 -> 연산 결과가 존재하지 않으면 -> 집합 생성 -> 원소 추가

이제 자료구조를 선택해보자.

 - key, value 형태로 저장이 가능해야 하고 검색 시 시간복잡도가 낮아야 한다.

 - HashMap<Integer, ArrayList<Node>>

---

직접 코딩을 해보면 아래와 같다.

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

/**
 *  a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자
 */

public class Main {

    static final int MAX = 100;

    public static void main(String[] args) throws IOException {

        HashMap<Integer, ArrayList<Node>> map = new HashMap<>();

        // For loop - each pair repeats only once
        for (int a = 0; a < MAX; a++) {
            for (int b = a; b < MAX; b++) {

                int x = a * a * a + b * b * b;

                if (!map.containsKey(x)) {

                    map.put(x, new ArrayList<>());
                }

                Node node = new Node(a, b);
                map.get(x).add(node);
            }
        }

        Iterator<Integer> it = map.keySet().iterator();

        while (it.hasNext()) {

            int key = it.next();

            if (map.get(key).size() > 1) {

                System.out.println(key + ", " + map.get(key));
            }
        }
    }
}

class Node {

    int a, b;

    Node(int a, int b) {

        this.a = a;
        this.b = b;
    }

    @Override
    public String toString() {

        return "(" + a + ", " + b + ")";
    }
}

* 실행 결과

32832, [(4, 32), (18, 30)]

327763, [(30, 67), (51, 58)]

65728, [(12, 40), (31, 33)]

704977, [(2, 89), (41, 86)]

.........