99클럽 코테 스터디 15일차 TIL + 해시(2)

187. Repeated DNA Sequences

 

 

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

• For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

 

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either 'A', 'C', 'G', or 'T'.

 

 

---

 

[목표]

 

 

- 문자열에서 길이가 정확히 10인 서브스트링들을 전부 찾고

- 그 중에서 2번 이상 등장하는 것들만 골라서 결과에 담음

 

 

예시 )  입력 문자열: "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

 

0~9   : AAAAACCCCC  
1~10  : AAAACCCCCA  
2~11  : AAACCCCCAA  
...  
10~19 : AAAAACCCCC  

 

-> 답 : ["AAAAACCCCC", "CCCCCAAAAA"]

 

 

 

 

 

 

< 접근 방법 >

 

중복된 값을 자동으로 제거해주는 HashSet 사용!!

-> "AAAACCCC"가 3번 나와도 한 번만 저장함.

 

 

1) 받은 문자열을 저장하는 HashSet

2) 중복 문자열을 구분하는 HashSet

 

Set<String> seen = new HashSet<>();
Set<String> repeated = new HashSet<>();

 

 

 

 

3) 반복문으로 문자열에서 10개씩 잘라서 hash에 저장

- 만약 seen에 있는 문자열과 동일한 문자열이 들어오면 repeated에 저장

	for(int i=0; i<=s.length()-10; i++){
            String sub = s.substring(i, i+10);

             if(seen.contain(sub))){
                repeated.add(sub);
             }else{
                seen.add(sub);
             }
        }

 

!! 여기서 헷갈렸던 점

 

1) 왜 범위를 s.length() - 10이렇게 잡지?

- substring(i, i + 10)를 쓰려면 i+10이 문자열을 넘으면 안된다. 

- 즉, i+10 <= s.length() 이므로 i <= s.length() - 10

 

** substring(i, i+10)이라면 i ~ i+9까지

 

 

 

 

4) 반환값

return new ArrayList<>(repeated);

 

- 메서드의 리턴 타입이 List<String> 타입이어야하는데 지금 Set<String> 타입이므로 

Set을 List로 바꿔주어야함. 

 

 

 

 

 

<전체코드>

 

import java.util.*;

public class RepeatedDNASequences {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> seen = new HashSet<>();
        Set<String> repeated = new HashSet<>();

        for (int i = 0; i <= s.length() - 10; i++) {
            String substring = s.substring(i, i + 10);
            if (seen.contains(substring)) {
                repeated.add(substring);
            } else {
                seen.add(substring);
            }
        }

        return new ArrayList<>(repeated);
    }
}

 

 

 

---

- 중복된 값을 자동으로 제거해주는 HashSet에 대해 더 공부할 것. 

- substring 범위에 주의할 것.