[NHN NEXT] Sparce Matrix 구현하기

sparce_matrix.cpp

#include <stdio.h>
#include <stdlib.h>

typedef struct SparceMatrix{
	int rowId;
	int colId;
	int value;
}SparceMatrix;

int Arr[3][3] = {{0,3,0},
{0,0,2},
{4,0,2}};
int Brr[3][3] = {{2,1,0},
{0,0,1},
{5,0,0}};
int Crr[3][3];

int calculate(SparceMatrix p);

int main(void)
{
	int i,j,k;
	int Acount = 0, BCount = 0;
	// 미리 Count
	for( i = 0 ; i < 3 ; i ++ ){
		for( j = 0 ; j < 3 ; j ++ ){
			if( Arr[i][j] != 0 ) Acount++;// Acount : A배열 0이 아닌 원소수
			if( Brr[i][j] != 0 ) BCount++;// Bcount : B배열 0이 아닌 원소수
		}
	}
	// sparce배열 만들기
	int AsparceCount=0, BsparceCount=0;
	SparceMatrix *Asparce = (SparceMatrix*)malloc(sizeof(SparceMatrix)* Acount);
	SparceMatrix *Bsparce = (SparceMatrix*)malloc(sizeof(SparceMatrix)* BCount);
	for( i = 0 ; i < 3 ; i ++ ){
		for( j = 0 ; j < 3 ; j ++ ){
			if( Arr[i][j] != 0 ){
				Asparce[AsparceCount].rowId = i;	// rowId
				Asparce[AsparceCount].colId = j; // colId;
				Asparce[AsparceCount].value = Arr[i][j];// value
				AsparceCount++;
			}
			if( Brr[i][j] != 0 ){
				(Bsparce+BsparceCount)->rowId = i;	// rowID
				(Bsparce+BsparceCount)->colId = j;	// colID
				(Bsparce+BsparceCount)->value = Brr[i][j];//value
				BsparceCount++;
			}
		}
	}

	// 덧셈
	int Amove=0, Bmove=0;
	SparceMatrix* Csparce;
	int Cmove = 0;
	while(Amove < Acount || Bmove < BCount){
		if( Amove == Acount ){  // A 화살표가 밖으로 나가면
			// B처리
		}
		else if( Bmove == BCount ){  // B화살표가 밖으로 나가면
			// A처리
		}
		else{								// 둘다 범위 안에 있을때
			if( calculate(Asparce[Amove]) == calculate(Bsparce[Bmove]) ){
				Csparce[Cmove].rowId = Asparce[Amove].rowId;
				Csparce[Cmove].colId = Asparce[Amove].colId;
				Csparce[Cmove].value = Asparce[Amove].value + Bsparce[Bmove].value;
			}	// A,B 합하여 더함
			else if( calculate(Asparce[Amove]) < calculate(Bsparce[Bmove]) ){
				Csparce[Cmove] = Asparce[Amove];
			}	// A만 대입해줌
			else if( calculate(Asparce[Amove]) > calculate(Bsparce[Bmove] )){
				Csparce[Cmove] = Bsparce[Bmove];
			}
		}
	}
	return 0;
}

int calculate(SparceMatrix p)
{
	return p.rowId * 3 + p.colId;		// 행의 갯수
}