[Baekjoon] 1969_DNA

Silver IV

문제(출처: https://www.acmicpc.net/problem/1969)

---

< DNA >

 

문제 풀이 

 

Hamming Distance의 합이 가장 작은 DNA를 구하기 위해서는 N개의 DNA에서 각 i번째 글자가 많이 겹치는 문자를 뉴클레오티드로 정하면 된다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _1969_ { // DNA
	static class Dna implements Comparable<Dna> {
		private char x;
		private int cnt;

		public Dna(char x, int cnt) {
			this.x = x;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Dna o) {
			if (this.cnt == o.cnt)
				return this.x - o.x;
			return o.cnt - this.cnt;
		}
	}

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		ArrayList<HashMap<Character, Integer>> list = new ArrayList<>();
		String arr[]=new String[n];
		for (int i = 0; i < m; i++) {
			list.add(new HashMap<>());
		}

		for (int i = 0; i < n; i++) {
			arr[i] = bf.readLine();
			for (int j = 0; j < m; j++) {
				if (list.get(j).containsKey(arr[i].charAt(j))) {
					list.get(j).replace(arr[i].charAt(j), list.get(j).get(arr[i].charAt(j))+1);
				} else {
					list.get(j).put(arr[i].charAt(j), 1);
				}
			}
		}

		String result = "";
		int answer=0;
		PriorityQueue<Dna> queue = new PriorityQueue<>();

		for (int i = 0; i < m; i++) {
			list.get(i).forEach((key, value) -> {
				queue.add(new Dna(key, value));
			});
			char temp=queue.poll().x;
			for(int j=0; j<n; j++) {
				if(arr[j].charAt(i) != temp) {
					answer+=1;
				}
			}
			result += temp;
			queue.clear();
		}

		System.out.println(result);
		System.out.println(answer);
	}
}

 

Main

변수)
n : DNA 수
m : 문자열의 길이
list : ArrayList <HashMap <Character, Integer>>
arr : DNA 저장
result : Hamming Distance의 합이 가장 작은 DNA
answer : Hamming Distance의 합
queue : PriorityQueue <Dna>

 

- DNA의 수(n), 문자열의 길이(m) 입력

- DNA를 입력받아 j번째 문자가 j번째 HashMap에 있는지 없는지 확인 후 없으면 HashMap에 추가, 있으면 value만 추가

- HashMap m개를 탐색

: HashMap에 있는 값을 모두 우선순위 큐에 넣음 (value가 큰 순으로, value가 같다면 알파벳 순으로 정렬)

: 우선순위 큐 젤 앞에 값을 poll

: 저장해 둔 DNA를 탐색하며 Hamming Distance 합 구함

- Hamming Distance 합이 가장 작은 DNA(result), Hamming Distance의 합(answer) 출력

---

---