-
JUNGOL...157일지 2021. 11. 3. 10:16
Intermediate_Coder/백트래킹-DFS/DNA 조합
문제
도훈이는 학교에서 배운 유전자 실험을 이용해서 자신만의 실험을 계획하고 있다
(프로그램을 작성해주는 복제인간을 만드는 것이 목표라고 한다).
도훈이가 갖고 있는 DNA 조각은 n(2<=n<=7)개가 있다.
이들 DNA 조각은 복제인간이 가져야 할 중요한 유전자를 담고 있기 때문에,
이 조각들의 정보를 그대로 유지시키면서 가장 짧은 DNA 순열을 새로 만들고 싶다.
DNA 순열을 조합하는 과정은 아래와 같다.
1) n개의 DNA조각을 임의의 순서로 나열한다.
2) 인접한 두 DNA조각에서 앞쪽 조각의 오른쪽 끝 부분이
뒤쪽 조각의 왼쪽 끝 부분과 최대한 많이 일치하는 부분을 찾는다.
3) 모든 인접한 두 DNA에서 중복되는 부분을 제거하고 나머지 부분을
순서대로 모아 새로운 문자열을 만든다.4) 새로운 문자열을 만들때 인접한 문자열의 공통부분만 제거할 수 있음에 유의한다.
예를 들어 ABC, D, BCD 를 순서대로 연결하는 경우 ABCD가 아닌 ABCDBCD가 된다.
예를 들어, ‘GATTA’와 ‘TACA’는 ‘GATTACA’로 조합될 수 있다.
왜냐하면 ‘GATTA’의 오른쪽 두 글자 ‘TA’가 ‘TACA’의 왼쪽 두 글자 ‘TA’와 일치하기 때문이다.
어떤 경우에는 한 조각이 다른 조각의 내용을 모두 포함하고 있을 수도 있고, 어떤 경우에는 단 한 글자도 일치하지 않을 수도 있다.
‘GATTACA’와 ‘TTACA’는 완벽하게 겹치는 반면에 ‘GATTACA’와 ‘TTA’는 한 글자도 겹치지 않는다.
아래에 조합의 몇 가지 예가 있다.
GATTA+TACA -> GATTACA
TACA+GATTA -> TACAGATTA
TACA+ACA -> TACA
TAC+TACA -> TACA
ATAC+TACA -> ATACA
TACA+ACAT -> TACAT
입력 형식
첫 줄에 n이 입력되고, 두 번째 줄부터 n개의 줄에 걸쳐 각 DNA 조각이 입력된다.
DNA조각의 길이는 1 ~ 7 이다.출력 형식
첫 번째 줄에 n개의 DNA를 모두 조합해서 하나의 DNA 순열로 만들었을 때 최소 길이를 출력한다.
입력 예
4 | 3
GATTA | ABC
TAGG | BCD
ATCGA | ABCD
CGCAT |출력 예
13 | 4
DNACombination.h
#include <iostream> #include <string> #include <algorithm> using std::string; class DNACombination : public Base { private: size_t GetMinLengthOfCombination(string arr[7], int n, string combination = ""); void CopyArrWithoutIdx(string arr[7], string copyArr[7], int n, int idx); string CombineDNA(string originDNA, string addDNA); };DNACombination.cpp
void DNACombination::Code() { int n; std::cin >> n; string arr[7]; for (int i = 0; i < n; i++) { std::cin >> arr[i]; } std::cout << GetMinLengthOfCombination(arr, n); } /// <summary> /// DNA를 조합할 때 최소 길이가 되는 조합의 길이를 반환한다. /// </summary> /// <param name="arr">DNA 배열</param> /// <param name="n">배열의 길이</param> /// <param name="combination">조합 결과</param> /// <returns>조합의 길이</returns> size_t DNACombination::GetMinLengthOfCombination(string arr[7], int n, string combination) { if (n == 0) { return combination.size(); } size_t minLength{ 999'999'999 }; string newArr[7]; for (int i = 0; i < n; i++) { CopyArrWithoutIdx(arr, newArr, n, i); size_t length{ GetMinLengthOfCombination(newArr, n - 1, CombineDNA(combination, arr[i])) }; if (length < minLength) { minLength = length; } } return minLength; } /// <summary> /// 배열의 주어진 인덱스를 제외한 값을 새로운 배열에 복사한다. /// </summary> /// <param name="arr">배열</param> /// <param name="copyArr">복사할 배열</param> /// <param name="n">배열의 길이</param> /// <param name="idx">제외할 인덱스</param> void DNACombination::CopyArrWithoutIdx(string arr[7], string copyArr[7], int n, int idx) { for (int i = 0, j = 0; i < n; i++) { if (i != idx) { copyArr[j++] = arr[i]; } } } /// <summary> /// 기존 DNA와 새 DNA를 조합한다. /// </summary> /// <param name="originDNA">기존 DNA</param> /// <param name="addDNA">새로 추가된 DNA</param> /// <returns>조합된 DNA</returns> string DNACombination::CombineDNA(string originDNA, string addDNA) { size_t originSize{ originDNA.size() }; size_t addSize{ addDNA.size() }; size_t restIdx{ 0 }; for (size_t i = 0; i < originSize; i++) { bool notCombined{ false }; for (restIdx = 0; restIdx < addSize && i + restIdx < originSize; restIdx++) { // 중간에 다른 값이 있으면 포함되지 않는다. if (originDNA[i + restIdx] != addDNA[restIdx]) { notCombined = true; break; } } // 안에 완전히 넣어지는 경우를 제외한다. if (restIdx == addSize && i + restIdx < originSize) { notCombined = true; } if (notCombined) { continue; } break; } return originDNA.append(addDNA.substr(restIdx)); }
실행 결과 Accepted(90)
원인 중간에 묻히는 경우를 제외했어도 동일한 결과가 출력되었다.
처리 방법 실제 조합된 값과 길이를 출력해 본 결과 정상적으로 동작하는 것 같아 질문을 올려봐야 할 것 같다.
출력결과
5 TAG TGCAG CA T ACTG TAGTGCAGCATACTG 15 TAGTGCAGCACTGT 14 TAGTGCAGTCACTG 14 TAGTGCAGTACTGCA 15 TAGTGCAGACTGCAT 15 TAGTGCAGACTGTCA 15 TAGCATGCAGTACTG 15 TAGCATGCAGACTGT 15 TAGCATGCAGACTG 14 TAGCATACTGCAG 13 TAGCACTGCAGT 12 TAGCACTGTGCAG 13 TAGTGCAGCACTG 13 TAGTGCAGACTGCA 14 TAGTCATGCAGACTG 15 TAGTCACTGCAG 12 TAGTACTGCAGCA 13 TAGTACTGCAG 11 TAGACTGCAGCAT 13 TAGACTGCAGTCA 13 TAGACTGCAGT 11 TAGACTGCATGCAG 14 TAGACTGTGCAGCA 14 TAGACTGTCATGCAG 15 TGCAGTAGCATACTG 15 TGCAGTAGCACTGT 14 TGCAGTAGTCACTG 14 TGCAGTAGTACTGCA 15 TGCAGTAGACTGCAT 15 TGCAGTAGACTGTCA 15 TGCAGCATAGTACTG 15 TGCAGCATAGACTGT 15 TGCAGCATAGACTG 14 TGCAGCATACTGTAG 15 TGCAGCACTGTAGT 14 TGCAGCACTGTAG 13 TGCAGTAGCACTG 13 TGCAGTAGACTGCA 14 TGCAGTCATAGACTG 15 TGCAGTCACTGTAG 14 TGCAGTACTGTAGCA 15 TGCAGTACTGCATAG 15 TGCAGACTGTAGCAT 15 TGCAGACTGTAGTCA 15 TGCAGACTGCATAGT 15 TGCAGACTGCATAG 14 TGCAGACTGTAGCA 14 TGCAGACTGTCATAG 15 CATAGTGCAGTACTG 15 CATAGTGCAGACTGT 15 CATAGTGCAGACTG 14 CATAGTACTGCAG 13 CATAGACTGCAGT 13 CATAGACTGTGCAG 14 CATGCAGTAGTACTG 15 CATGCAGTAGACTGT 15 CATGCAGTAGACTG 14 CATGCAGTACTGTAG 15 CATGCAGACTGTAGT 15 CATGCAGACTGTAG 14 CATAGTGCAGACTG 14 CATAGACTGCAG 12 CATGCAGTAGACTG 14 CATGCAGACTGTAG 14 CATACTGTAGTGCAG 15 CATACTGCAGTAG 13 CACTGTAGTGCAGT 14 CACTGTAGTGCAG 13 CACTGCAGTAGT 12 CACTGCAGTAG 11 CACTGTAGTGCAG 13 CACTGTGCAGTAG 13 TAGTGCAGCACTG 13 TAGTGCAGACTGCA 14 TAGCATGCAGACTG 14 TAGCACTGCAG 11 TAGACTGCAGCA 12 TAGACTGCAG 10 TGCAGTAGCACTG 13 TGCAGTAGACTGCA 14 TGCAGCATAGACTG 14 TGCAGCACTGTAG 13 TGCAGACTGTAGCA 14 TGCAGACTGCATAG 14 TCATAGTGCAGACTG 15 TCATAGACTGCAG 13 TCATGCAGTAGACTG 15 TCATGCAGACTGTAG 15 TCACTGTAGTGCAG 14 TCACTGCAGTAG 12 TACTGTAGTGCAGCA 15 TACTGTAGCATGCAG 15 TACTGCAGTAGCA 13 TACTGCAGCATAG 13 TACTGCATAGTGCAG 15 TACTGCAGTAG 11 ACTGTAGTGCAGCAT 15 ACTGTAGTGCAGTCA 15 ACTGTAGCATGCAGT 15 ACTGTAGCATGCAG 14 ACTGTAGTGCAGCA 14 ACTGTAGTCATGCAG 15 ACTGCAGTAGCAT 13 ACTGCAGTAGTCA 13 ACTGCAGCATAGT 13 ACTGCAGCATAG 12 ACTGCAGTAGCA 12 ACTGCAGTCATAG 13 ACTGCATAGTGCAGT 15 ACTGCATAGTGCAG 14 ACTGCAGTAGT 11 ACTGCAGTAG 10 ACTGCATAGTGCAG 14 ACTGCATGCAGTAG 14 ACTGTAGTGCAGCA 14 ACTGTAGCATGCAG 14 ACTGTGCAGTAGCA 14 ACTGTGCAGCATAG 14 ACTGTCATAGTGCAG 15 ACTGTCATGCAGTAG 15 10NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)
NadanKim/CodingTest_JUNGOL
JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.
github.com