코딩 테스트는 프로그래밍 실력을 검증하는 중요한 수단으로, 기업에서는 이를 통해 지원자의 알고리즘적 사고능력과 문제 해결 능력을 평가합니다. 이번 강좌에서는 자바스크립트를 이용하여 DNA 비밀번호 문제를 해결하는 과정을 자세히 살펴보겠습니다.
문제 설명
DNA 비밀번호 문제는 다음과 같습니다:
문제: 길이 N인 문자열 DNA가 주어지면, DNA 문자열에서 비밀번호가 될 수 있는 모든 부분 문자열의 개수를 구하시오. 비밀번호의 조건은 ‘A’, ‘C’, ‘G’, ‘T’ 중에서 정확히 1개에서 2개가 포함되어야 하며, 최소 1개이어야 한다.
예시 입력 및 출력
입력: "ACGTACGTA"
출력: 16
문제 해결 과정
이 문제를 해결하기 위해 우리는 다음 단계를 따릅니다:
1단계: 문제 분석
주어진 DNA 문자열에서 비밀번호를 만족하는 모든 부분 문자열을 찾아야 합니다. 비밀번호는 ‘A’, ‘C’, ‘G’, ‘T’ 중에서 1개 또는 2개가 포함되어야 합니다. 따라서, 각 문자가 포함된 부분 문자열의 경우를 고려해야 합니다.
2단계: 부분 문자열 생성
DNA 문자열의 모든 부분 문자열을 생성하기 위해서는 두 개의 포인터를 이용하여 시작Index와 끝Index를 정할 수 있습니다. 이 과정은 O(N^2)의 경우의 수를 생성합니다.
3단계: 비밀번호 조건 확인
각 부분 문자열에서 ‘A’, ‘C’, ‘G’, ‘T’의 개수를 확인해야 합니다. 이를 위해 정규 표현식이나 카운팅 배열을 사용할 수 있습니다.
4단계: 코드 구현
이제 문제 해결을 위한 자바스크립트 코드를 구현해보겠습니다:
function countDNAPasswords(dna) {
const n = dna.length;
let count = 0;
// 모든 부분 문자열 생성
for (let start = 0; start < n; start++) {
const charCount = { 'A': 0, 'C': 0, 'G': 0, 'T': 0 };
for (let end = start; end < n; end++) {
// 현재 문자 카운트
const char = dna[end];
if (charCount[char] !== undefined) {
charCount[char]++;
}
// 비밀번호 조건 체크
const uniqueCount = Object.values(charCount).filter(x => x > 0).length;
if (uniqueCount >= 1 && uniqueCount <= 2) {
count++;
}
}
}
return count;
}
// 예시 사용
const dnaString = "ACGTACGTA";
console.log(countDNAPasswords(dnaString)); // 출력: 16
코드 설명
위에서 작성한 코드의 주요 기능은 다음과 같습니다:
countDNAPasswords함수는 DNA 문자열을 입력으로 받아 비밀번호의 개수를 계산합니다.- 두 개의 중첩된
for루프를 사용하여 모든 부분 문자열을 생성합니다. - 각 부분 문자열에 대해
charCount객체를 사용하여 ‘A’, ‘C’, ‘G’, ‘T’의 개수를 세고, 비밀번호 조건을 확인합니다. - 조건에 맞는 경우를 count합니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N^2)입니다. 두 개의 중첩된 루프를 사용하여 모든 부분 문자열을 생성합니다. 하지만 이 방식은 문자열의 길이가 길어질 경우 성능에 문제를 일으킬 수 있습니다. 따라서, 최적화된 방법이나 다른 알고리즘을 적용하는 것도 고려할 수 있습니다.
결론
이번 강좌에서는 자바스크립트를 이용하여 DNA 비밀번호 문제를 해결하는 방법을 알아보았습니다. 알고리즘 문제에서 출발하여, 코드를 구현하고 결과를 도출하는 과정을 자세히 살펴보았습니다. 이와 같은 문제는 코딩 테스트에서 자주 등장하기 때문에 꾸준한 연습이 필요합니다.
이러한 연습을 통해 반복적으로 문제 해결 능력을 향상시킬 수 있으니, 다양한 문제를 풀어보는 것을 추천합니다. 감사합니다!