CodeIQ：アイテム類似度のレコメンド

問題の概要

私のプログラム

Javaで解答しています。

import java.io.*;
import java.util.*;


public class Main{
	static int[][] DataArray;	// 入力データの行列 （行：アイテム番号、列：ユーザ番号） 0始まり
	static int nItem;	// アイテム数
	static int nUser;	// ユーザ数
	static int nRating;	// レーティング数
	static int retItemNum;	// 類似度を出力するアイテム数
	static int[] retItems;	// 類似度を出力するアイテム番号 0始まり

	static double[] ItemVecLenArray;
	static double[][] SimCosArray;

	/**
	 *	データ数情報をセットする
	 *	@param line 入力行（ユーザ数 アイテム数 レーティング数）
	 */
	public static void parseDataNum(String line){
		String[] splited = line.split(" ");
		int[] ret = new int[splited.length];
		for(int i=0; i<splited.length; i++){
			ret[i] = Integer.parseInt(splited[i]);
		}

		nUser = ret[0];
		nItem = ret[1];
		nRating = ret[2];
	}

	/**
	 *	データの配列を作成する
	 *	行番号はアイテム番号（入力値は1始まり、実装は0始まり）
	 *	列番号はユーザ番号（入力値は1始まり、実装は0始まり）
	 *	※ 問題の表とは行列が入れ替わる
	 */
	public static void createDataArray(){
		DataArray = new int[nItem][];
		for(int i=0; i<nItem; i++){
			DataArray[i] = new int[nUser];
		}
	}

	/**
	 *	データ行列に値を設定する
	 *	@param line 入力値（ユーザ番号 アイテム番号 レーティング）
	 */
	public static void setDataArray(String line){
		String[] splited = line.split(" ");
		int[] ret = new int[splited.length];
		for(int i=0; i<splited.length; i++){
			ret[i] = Integer.parseInt(splited[i]);
		}

		int u = ret[0]-1;	// ユーザ番号
		int i = ret[1]-1;	// アイテム番号
		int r = ret[2];	// レコメンド

		DataArray[i][u] = r;
	}

	/**
	 *	データ行列を表示する（デバッグ）
	 */
	public static void printDataArray(){
		for(int[] l: DataArray){
			for(int i: l){
				System.out.print(i);
				System.out.print(" ");
			}
			System.out.println("");
		}
	}

	/**
	 *	結果を表示するアイテム番号のリストを作る
	 */
	public static void createRetItems(String line){
		retItemNum = Integer.parseInt(line);
		retItems = new int[retItemNum];
	}

	/**
	 *	結果を表示するアイテム番号のリストにアイテム番号をセットする
	 *	@param line 入力値（0始まりに直す）
	 *	@param n 何番目に入力された値か（0始まり）
	 */
	public static void setRetItems(String line, int n){
		int i = Integer.parseInt(line);
		retItems[n] = i-1;
	}

	/**
	 *	アイテム番号のリストを表示する（デバッグ）
	 */
	public static void printRetItems(){
		for(int i: retItems){
			System.out.print(i);
			System.out.print(" ");
		}
		System.out.println("");
	}

	/**
	 *	各アイテムの√Σ(レーティング^2)を計算して表にしておく
	 */
	public static void calcItemVecLenArray(){
		ItemVecLenArray = new double[nItem];
		for(int j=0; j<DataArray.length; j++){
			long s = 0;
			for(int i: DataArray[j]){
				s += i*i;
			}
			ItemVecLenArray[j] = Math.sqrt(s);
		}
	}

	/**
	 *	各アイテムの√Σ(レーティング^2)を表示する
	 */
	public static void printItemVecLenArray(){
		for(double d: ItemVecLenArray){
			System.out.println(d);
		}
	}

	/**
	 *	コサイン類似度の計算結果行列領域を作成する
	 */
	public static void createSimCosArray(){
		SimCosArray = new double[nItem][];
		for(int i=0; i<nItem; i++){
			SimCosArray[i] = new double[nItem];
		}
	}

	/**
	 *	コサイン類似度の計算結果行列領域を表示する（デバッグ）
	 */
	public static void printSimCosArray(){
		for(double[] l: SimCosArray){
			for(double d: l){
				System.out.printf("%4f ", d);
			}
			System.out.println("");
		}
	}

	/**
	 *	Σ(a*b)を計算する
	 */
	private static double calcAB(int[] a, int[] b){
		double s = 0;
		for(int i=0; i<nUser; i++){
			s += a[i] * b[i];
		}
		return s;
	}

	/**
	 *	コサイン類似度を全アイテムに対して計算し、結果を表に収める
	 */
	public static void simCos(){
		for(int i=0; i<nItem; i++){
			for(int j=i+1; j<nItem; j++){
				int[] a = DataArray[i];
				int[] b = DataArray[j];

				SimCosArray[i][j] = calcAB(a, b) / (ItemVecLenArray[i] * ItemVecLenArray[j]);
				SimCosArray[j][i] = SimCosArray[i][j];
			}
		}
	}

	/**
	 *	指定されたアイテムと類似度の高いもの3個の番号（1始まり）を表示する
	 *	@param index 対象のアイテム番号（0始まり）
	 */
	private static void printMax3(int index){
		double[] l = SimCosArray[index];
		double max[] = new double[3];
		int max_i[] = new int[3];

		for(int i=0; i<l.length; i++){
			if(max[0] < l[i]){
				max[2] = max[1];
				max_i[2] = max_i[1];
				max[1] = max[0];
				max_i[1] = max_i[0];
				max[0] = l[i];
				max_i[0] = i;
			}
			else if(max[1] < l[i]){
				max[2] = max[1];
				max_i[2] = max_i[1];
				max[1] = l[i];
				max_i[1] = i;
			}
			else if(max[2] < l[i]){
				max[2] = l[i];
				max_i[2] = i;
			}
		}

		String s = String.valueOf(index + 1) + " ";
		for(int i=0; i<3; i++){
			s += String.valueOf(max_i[i]+1) + " ";
		}
		s = s.trim();
		System.out.println(s);
	}

	/**
	 *	結果を表示する
	 */
	public static void printResult(){
		for(int i: retItems){
			printMax3(i);
		}
	}

	public static void main(String args[]) throws IOException{
		try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
			String line;

			for(int i=0; (line = br.readLine()) != null; i++){
				line = line.trim();

				if(i == 0){
					parseDataNum(line);
					createDataArray();
				}
				else if(i <= nRating){
					setDataArray(line);
				}
				else if(i == nRating+1){
					createRetItems(line);
				}
				else{
					setRetItems(line, i-(nRating+2));
				}
			}

			calcItemVecLenArray();
			createSimCosArray();
			simCos();
			printResult();
		}
	}
}

解説

★★★★の問題ですが私はあまり難しいとは思いませんでした。
問題の説明は詳しいですし、ロジックは明確に示されていてその通りに実装すれば良いと思います。

雑感

解答を書いて投稿する段では「これで時間切れになったら改善する方法を思いつかない（せいぜいItemVecLenArrayを入力を読みながら作るくらい）」と思って緊張しましたが、余裕でパスしてどこが難しかったんだろうというのが感想です。