알고리즘 (6월 29일)

1. 문제 (다항식 계산)

---

2. 생각

• 변수 타입(다항식)에 대해서 먼저 생각해볼 필요가 있다.
  ▶ 다항식은 여러 개의 항들이 모여서 만든 식이라는 점을 생각
  ▶ 각 항들은 계수와 차수 값을 저장할 수 있는 인스턴스 변수들이 존재하는 Term 클래스 정의▶ 다항식은 여러 개의 항들을 배열 형태로 저장하고, 실제 항들의 갯수와 다항식의 이름을 저장할 수 있는
       Polynomial 클래스 정의
• add 명령어를 통해 새로운 항이 들어오면 어떻게 저장할 것인가?
  ▶ 미리 차수를 기준으로 내림차순 저장하는 것이 나중에 출력할 때, 편리할 거 같다.
  ▶ 새로운 항의 차수를 통해 위치를 찾는다. 
  ▶ for문을 이용하여 차수가 낮은 항들을 한 칸씩 뒤로 옮긴다.
  
• 하지만, add 했는데, 이전 계수와 더해져서 계수가 0이 된 경우에는? (ex, -4x + 4x = 0*x)
  ▶ 더해져서 계수가 0이 될 경우, 해당항을 삭제하기 위해서 다음 항의 참조 변수를 한 칸씩 앞으로 옮긴다.
• print 명령어 과정에서 계수가 -1과 1인 경우에 대해서 생각해 볼 필요가 있다.

---

3. 풀이 및 코드 분석

package Chapter2;

import java.util.Scanner;

public class CalculatePolynomial {
	static Polynomial[] polynomial = new Polynomial[100];
	static int countPolynomial = 0;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		while(true) {
			System.out.print("$");		
			String command = scan.next();
			
			if(command.equalsIgnoreCase("create")) {
				char name = scan.next().charAt(0);
				int result =checkPolynomial(name);
				if(result >= 0)
					System.out.println("That name of polynomial alreay existed.");
				else {
					polynomial[countPolynomial] = new Polynomial();
					polynomial[countPolynomial].name = name;
					countPolynomial++;
				}		
			}else if(command.equalsIgnoreCase("add")) {
				char name = scan.next().charAt(0);
				int nPoly = checkPolynomial(name);
				
				if(nPoly==-1)
					System.out.println("No such Polynomial exists");
				else {
					int newCoeff = scan.nextInt();
					int newExpo = scan.nextInt();
					
					addTerm(nPoly, newCoeff, newExpo);
				}
			}else if(command.equalsIgnoreCase("calc")) {
				char nameOfPoly = scan.next().charAt(0);
				int result = checkPolynomial(nameOfPoly);
		
				if(result == -1)
					System.out.println("No such Polynomial exists");
				else {
					int inputData = scan.nextInt();
					calculate(polynomial[result], inputData);
				}		
			}else if(command.equalsIgnoreCase("print")) {
				char nameOfPoly = scan.next().charAt(0);
				printPolynnomial(nameOfPoly);
			}else if(command.equalsIgnoreCase("exit")) {
				System.exit(0);
			}else {
				System.out.println("You entered an wrong command.");
			}
		}
	}
	
	public static int checkPolynomial(char name) {
		for(int i=0; i<countPolynomial; i++) {
			if(polynomial[i].name == name)
				return i;
		}
		return -1;
	}
	
	public static void addTerm(int nPoly, int newCoeff, int newExpo) {
		int	checkExpo = -1;
		Polynomial poly = polynomial[nPoly];
		
		for(int i=0; i<poly.nTerm; i++) {
			if(poly.terms[i].expo==newExpo) {
				checkExpo = i;
				break;
			}
		}
		
		if(checkExpo != -1) {
			int sumCoeff = newCoeff+poly.terms[checkExpo].coeff;
			
			if(sumCoeff==0) {
				for(int i=checkExpo+1; i<poly.nTerm; i++)
					poly.terms[i-1] = poly.terms[i];
				poly.terms[poly.nTerm-1] = null;
				poly.nTerm--;
			}
			else 
				poly.terms[checkExpo].coeff = sumCoeff;
			
		}else {
			int i = poly.nTerm - 1;

			while(i>=0&&poly.terms[i].expo<newExpo) {
				poly.terms[i+1]=poly.terms[i];
				i--;
			}
			poly.terms[i+1] = new Term();
			poly.terms[i+1].coeff=newCoeff;
			poly.terms[i+1].expo=newExpo;
			poly.nTerm++;
		}
	}
	
	public static void printPolynnomial(char nameOfPoly) {
		int result = checkPolynomial(nameOfPoly);
		
		if(result == -1) {
			System.out.println("No such polynomial exists");
			return;
		}else {
			printTerms(polynomial[result]);
		}
	}
	
	public static void printTerms(Polynomial poly) {
		if(poly.nTerm == 0) {
			System.out.printf("%c = 0\n", poly.name);
			return;
		}
		
		System.out.printf("%c=", poly.name);
		for(int i=0; i<poly.nTerm; i++) {
			int getCoeff = poly.terms[i].coeff;
			int getExpo = poly.terms[i].expo;
			
			if(i!=0&&getCoeff>0)
				System.out.print("+");
			
			if(getExpo==1) 
				if(getCoeff==1)
					System.out.print("x");
				else if(getCoeff==-1)
					System.out.print("-x");
				else
					System.out.printf("%dx",getCoeff);
			else if(getExpo==0) 
				System.out.printf("%d",getCoeff);
			else 
				if(getCoeff==1)
					System.out.printf("x^%d", getExpo);
				else if(getCoeff==-1)
					System.out.printf("-x^%d", getExpo);
				else
					System.out.printf("%dx^%d",getCoeff, getExpo);
			
			if(i==poly.nTerm-1)
				System.out.println();
		}
	}
	
	public static void calculate(Polynomial poly, int input) {
		int sum = 0;
		
		for(int i=0; i<poly.nTerm; i++) {
			int getCoeff = poly.terms[i].coeff;
			int getExpo = poly.terms[i].expo;
			
			sum += getCoeff*(Math.pow(input, getExpo));
		}
		
		System.out.printf("The result of calculation is %d. \n",sum);
		return;
	}
}

package Chapter2;

public class Polynomial {
	public char name;
	public int nTerm=0;
	public Term[] terms = new Term[100];
}

package Chapter2;

public class Term {
	public int coeff;
	public int expo;
}

---

4. 메모

int i = poly.nTerm - 1;

while(i>=0&&poly.terms[i].expo<newExpo) {
	poly.terms[i+1]=poly.terms[i];
	i--;
}

int i = poly.nTerm - 1;

while(poly.terms[i].expo<newExpo&&i>=0) {
	poly.terms[i+1]=poly.terms[i];
	i--;
}

• 위 두 코드는 같은 것 같지만, 약간의 차이점이 존재한다. (이 부분때문에 문제점 찾는데, 20~30분 소요 ㅠ)
• 목표 : poly.nTerm = 0이면 i=-1 이기 때문에 while문을 실행하지 않고, 통과시키고 싶다.
• 문제점 : 아래 코드에서 "poly.terms[-1]은 존재하지 않는다."라는 문제가 발생
  (And 연산자를 기준으로 앞뒤가 바뀌었을 뿐, 같은 코드인거 같은데, 무엇이 문제인가?)
• 이유 : while문의 조건문에서 앞에서 조건을 따지기 때문에 위 코드인 경우에는 i가 0보다 크거나 같은지를 먼저 생각하지만, 아래 코드인 경우에는 poly.terms[i].expo<newExpo 인지를 먼저 생각한다.
  ▶ 이러한 이유로 위 코드은 원래 목표에 대해서 정상적으로 작동하지만, 아래 코드인 경우에는 i>=0인지를 따지기 전
       에  poly.terms[i].expo<newExpo 인지를 먼저 따져서 문제점 발생