2/21기록 - 백준 1969

주말 내내 바쁜일들이 많아서 쿨하게 알고리즘 문제풀이를 패스했다... 이러면 안되는데 ㅠㅠ 곧 개강이라 더 바쁠텐데...

휴~

 

각설하고 오늘의 문제는 백준 1969번 DNA문제이다.

 

 

문제를 이해하기 어려울 수 있는데, N개의 M개 뉴클레오타이드로 구성된 DNA구조를 입력받는다. 그리고 각 인덱스마다 비교하여 가장 많이 나온 문자가 기준 문자가 된다. 이렇게 했을 때 사실상 대부분 기준문자로 이루어진 DNA구조가 Hamming Distance가 가장 작은 DNA가 될 것이므로, max값을 구해야함을 알 수 있다. 그리고 마지막에 모든 DNA의 Hamming Distance의 합을 구하면 된다. 구하는 것이 두 개 이므로 두 구역으로 나누어 생각하면 조금 더 간단할 수 있을것이다.

 

나는 구역을 총 3개로 끊었다. 

1. 문자 세팅

2. max값 구해서 Hamming Distance가 가장 작은 DNA를 구하기

3. 모든 DNA의 Hamming Distance의 합 구하기

 

1. 문자 세팅

 

 

DNA구조를 담을 arr[]배열을 N개의 크기로 선언, 알파벳을 하나하나 체크할 DNAarr[][]배열을 N*26 이차원 배열로 선언한다. N개만큼 arr[]배열에다 입력하고, 26개의 알파벳을 점검하기 위해 charAt()으로 arr[] 배열을 쪼개고 - 'A'해준다. 이 알파벳을 DNAarr[][]배열의 열 인덱스로 넣고 ++시켜서 인덱스를 체크할 수 있게 해준다.

 

 

2. max값 구해서 Hamming Distance가 가장 작은 DNA를 구하기

 

 

max를 구해야 하므로 max값을 구할 때 흔히 많이 쓰는 방식을 택했다. max를 -1로 초깃값 설정을 하고, DNAarr[][] 배열이 max보다 크면 max에 DNAarr[][]배열을 담아주었다. 그리고 index를 열(j)로 만들어주어 해당 열에 StringBuilder의 append 기능으로 문자를 담아 max 문자를 출력시킬 수 있도록 해주었다.

 

 

3. 모든 DNA의 Hamming Distance의 합 구하기

 

 

 

모든 Hamming Distance의 합을 구하는 것이므로 각각 DNA구조의 Hamming Distance를 구해서 더할 필요가 없다. 그냥 전부 다 하나하나 체크하면서 조건에 만족하면 다 ++ 시키면 그만이다. 그래서 위 처럼 if문 안에서 arr[]배열의 charAt()과 StringBuilder로 만들어준 기준 DNA의 charAt()이 다르면 그냥 다 길이에 더하기 시켜주었다.

 

 

<전체코드>

 

 

이렇게 해결할 수 있었다. 끊어서 생각을 하면 더 간단하다. 정말 맨 처음에는 문자세팅 시 switch case문을 사용할까 했는데, 시간복잡도가 더 걸릴거 같은 느낌이라 지금의 방식을 택했다. 근데 다시 생각해 보니 이중 for문이 더 오래 걸릴 거 같긴하다..... 하나하나 끊어서 생각하고 문제를 푸니 생각보다 간단한 문제였다.

 

2/21 기록 끝!!!!!!!!