99클럽 코테 스터디 15일차 TIL + Leetcode 187. Repeated DNA Sequences

오늘의 학습 키워드

• 자바 문자열 처리
• Sliding Window 알고리즘
• HashSet을 활용한 중복 데이터 처리

   [ Leetcode 187. Repeated DNA Sequences ]

문제 요약

DNA 서열 문자열이 주어졌을 때,
길이가 10인 부분 문자열 중 두 번 이상 등장하는 문자열을 찾는 문제

 

해결 방법

• 문자열을 길이 10 윈도우로 잘라가며 탐색
• 중복 체크를 위해 HashSet 사용
• 처음 등장한 문자열은 seen Set에 저장
• 두 번째 등장한 문자열은 result Set에 저장

알고리즘 동작 방식

• HashSet : 중복 여부 체크  

Java 코드 구현

 

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int L = 10; // 서브스트링 길이
        int n = s.length();
        Set<String> seen = new HashSet<>();
        Set<String> repeated = new HashSet<>();

        for (int i = 0; i <= n - L; i++) {
            String sub = s.substring(i, i + L);
            if (seen.contains(sub)) {
                repeated.add(sub);
            } else {
                seen.add(sub);
            }
        }
        return new ArrayList<>(repeated);
    }
}

 

오늘의 회고

What?

DNA 서열 문자열에서 길이가 10인 부분 문자열 중 두 번 이상 등장하는 문자열 찾기

How?

Sliding Window 기법으로 고정 길이 서브스트링을 추출하고
HashSet으로 중복 여부를 체크하여 문제 해결