[자료구조] LinkedList - BigInt클래스 실습

java에서는 숫자의 범위에 따라서 int, long, float 등 다양한 자료형이 존재한다. 그러나 이러한 자료형들은 어디까지나 숫자의 한계가 있다. 한계를 벗어나는 숫자를 입력받게 되면 오류가 발생하게 된다. 

import java.util.Scanner;

public class main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		System.out.println(a);
	}

}

자료형을 벗어나는 숫자를 입력받게 된 경우

그래서 어떠한 숫자가 와도 받아낼 수 있는 하나의 객체형 자료 타입인 BigInt에 관하여 실습해보았다. BigInt 클래스는 숫자를 한자리 한자리 쪼개서 숫자 하나하나를 노드의 data값으로 넣어서 연결하는 것이다. 밑에는 실습 코드이다. String으로 입력 받은 경우, int형으로 입력 받은 경우 등등에 관련한 메소드와 간단한 BigInt간의 덧셈에 관하여 작성해보았다. 시간이 되면 뺄셈, 나눗셈, 곱셈 까지하여서 사칙연산까지 만들어보고자 한다. 

class BigInt {
	private Node start;

	private static class Node {
		int digit;
		Node next;

		Node(int digit) {
			this.digit = digit;
		}

	}

	public BigInt(int n) {
		if (n < 0)
			throw new IllegalArgumentException(n + "<0");
		start = new Node(n % 10);
		Node p = start;
		n /= 10;
		while (n > 0) {
			p = p.next = new Node(n % 10);
			n /= 10;
		}
	}

	public BigInt(String s) {
		if (s.length() == 0) {
			throw new IllegalArgumentException("empty string");
		}
		start = new Node(digit(s, s.length() - 1));
		Node p = start;
		for (int i = s.length() - 2; i >= 0; i--) {
			p = p.next = new Node(digit(s, i));
		}
	}

	private int digit(String s, int i) {
		String ss = s.substring(i, i + 1);
		return Integer.parseInt(ss);
	}

	public String toString() {
		StringBuffer buf = new StringBuffer(Integer.toString(start.digit));
		Node p = start.next;
		while (p != null) {
			buf.insert(0, Integer.toString(p.digit));
			p = p.next;
		}
		return buf.toString();
	}

	public BigInt plus(BigInt y) {
		Node p = start, q = y.start;
		int n = p.digit + q.digit;
		BigInt z = new BigInt(n % 10);
		Node r = z.start;
		p = p.next;
		q = q.next;
		while (p != null && q != null) {
			n = n / 10 + p.digit + q.digit;
			r.next = new Node(n % 10);
			p = p.next;
			q = q.next;
			r = r.next;
		}
		while (p != null) {
			n = n / 10 + p.digit;
			r.next = new Node(n % 10);
			p = p.next;
			r = r.next;
		} // 현재 클래스가 BigInt y보다 자릿수가 더 긴 경우
		while (q != null) {
			n = n / 10 + q.digit;
			r.next = new Node(n % 10);
			q = q.next;
			r = r.next;
		} // 현재 클래스가 BigInt y보다 자릿수가 더 짧은 경우
		if (n > 9)
			r.next = new Node(n / 10);
		return z;
	}

}

public class TestBigInt {
	public static void main(String[] args) {
		BigInt x = new BigInt(0);
		BigInt y = new BigInt(1);
		BigInt z = new BigInt(1);
		for (int i = 0; i < 100; i++) {
			x = y;
			y = z;
			z = x.plus(y);
			System.out.println(z);
		} // BigInt를 이용하여 100번째 피보나치수 까지 구하는 것이다. 
	}
}