百俊1969号.
https://www.acmicpc.net/problem/1969

質問する

DNAはある種の遺伝物質を構成する分子である.このDNAは4つの異なるヌクレオチドから構成されている.あるDNAの物質を発現するとき、このDNAを形成するヌクレオチドの最初の字を取って発現します.胸腺-アドレナリン-セピリジン-グリシン-セピリジン-セピリジン-グリシン-アドレナリン-胸腺からなるDNAがある場合は、「TAACTGCCGAT」で発現することができる.また、同じ長さのDNAが2つある場合、各位置のヌクレオチド文字は異なる個数である.「AGCAT」と「GGAFT」の1番目と3番目が異なる場合、hamminDistanceは2です.
私たちがしなければならないことは以下の通りです.N個の長さMのDNA s 1,s 2,...,これはsnが与えられたとき,ズームオフ度の和の最小のDNAを求めたものである.つまり、sとs 1の水泳距離+sとs 2の水泳距離+sとs 3の水泳距離...これは和解が最低限になることを意味する.

入力

1行目はDNAの数Nと文字列の長さMを与える.そして,第2列からN+1列にN個のDNAを与えた.Nは1000以下の自然数、Mは50以下の自然数である.

しゅつりょく

1行目には遊程と最小のDNA、2行目には遊程とを出力してください.そのようなDNAが複数ある場合は、辞書順に先頭の

入力例

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

サンプル出力

TAAGATAC
7

ACGTACGTAA
6

考える

この問題は解決しやすいように見えるが、複雑だ.
1文字に数文字貼ればいいのですが、
これは最小のDNAを印刷させる問題ですが、文字が異なるとこの問題が増えるので、最も多くの文字を選んで文字列を作成すればいいのです.

アクション

		N = Integer.parseInt(st.nextToken()); // DNA의 수
		M = Integer.parseInt(st.nextToken()); // 문자열의 길이
		
		arr = new String[N];
		for(int i=0; i<N; i++) {
			arr[i] = br.readLine();
		}

最初に導入された遺伝子はarrの配列に貯蔵される.いずれにしても文字列の長さは同じで、Nで1回繰り返すだけでいいです.
DNA()関数を実行しましょう.

		// 각 글자마다 가장 많이 나온 글자를 result에 연결시킨다.
		for(int i=0; i<M; i++) {
			HashMap<Character, Integer> map = new HashMap<>();
			max = 0;
			
			for(int j=0; j<N; j++) {	
				String str = arr[j];
				
				map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1);
			}
				

遺伝子文字列を含むarr配列から1文字Mが分離された.
どの字が何回出たかをループ全体で数えます.
この値はMap形式に適しているので、アルファベットをキー値、出現回数をvalueとします.mapに保管されています.

			Iterator<Entry<Character, Integer>> it = map.entrySet().iterator();
			
			while(it.hasNext()) {
				Entry<Character, Integer> entrySet = (Entry<Character, Integer>)it.next();
				int value = entrySet.getValue();
				char key =  entrySet.getKey();
				
				// 가장 많이 나온 알파벳 선택.
				if( max < value ) {
					max = value;
					ch = key;
				}
				// 값이 같을 경우 사전순으로 나열
				else if(max == value) {
					// 기존에 있던 ch와 key값을 사전순서로 비교해야함
					char temp = key;
					
					int num1 = Character.getNumericValue(ch);
					int num2 = Character.getNumericValue(temp);
					
					if(num1 > num2) {
						ch = temp;
					}
				}
			}

現在、mapが完了しています.
Identrarを使用してvalueとkeyを抽出
ここでは、最も多くの文字を検索する必要があるので、max変数を使用します.
最大値を更新し続け、各ワード接続result最後の結果が得られる.

コード#コード#

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class Main {
	static int sum = 0;
	static String result = "";
	static int N, M;
	static String arr[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new String[N];
		for(int i=0; i<N; i++) {
			arr[i] = br.readLine();
		}

		DNA();

		System.out.println(result);
		System.out.println(sum);

	} // End of main

	static void DNA() {
		char ch = ' '; // 문자
		int max; // 최대값

		for(int i=0; i<M; i++) {
			HashMap<Character, Integer> map = new HashMap<>();
			max = 0;

			for(int j=0; j<N; j++) {	
				String str = arr[j];

				map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1);
			}
			
			Iterator<Entry<Character, Integer>> it = map.entrySet().iterator();

			while(it.hasNext()) {
				Entry<Character, Integer> entrySet = (Entry<Character, Integer>)it.next();
				int value = entrySet.getValue();
				char key =  entrySet.getKey();

				if( max < value ) {
					max = value;
					ch = key;
				}
				else if(max == value) {
					char temp = key;

					int num1 = Character.getNumericValue(ch);
					int num2 = Character.getNumericValue(temp);

					if(num1 > num2) {
						ch = temp;
					}
				}
			}

			sum += N - max;
			result += ch;
		}
		
	} // End of solution
} // End of class