[LeetCode] Repeated DNA Sequences

늘지 않는 실력에 맘이 쪼끔 힘들어서 쉬운거 들고 왔다!

JAVA 로 코테를 보다보니 IDE를 쓰지 못해 아주 극한의 상황이라고 느껴진 적도 있었다. 그날 이후로는 IDE를 쓰지 않고 테스트페이지에서 바로 풀어보려는게 조금은 익숙해진 것 같다.

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.

• 문제 풀이
  • substring이 문제의 조건을 만족하는지 찾는 것이기 때문에, 전형적인 Sliding window문제이다.
  • 심지어 길이 10의 Fixed length를 가진 window를 사용하여 푸는 문제다.
  • 문제에서는 " 한 번" 보다 더 많이 등장한 DNA sequence를 찾으라고 하고 있기 때문에, 이미 등장했었던 적 있는 sequence인지 빠르게 찾기 위하여 Hash 구조를 사용해야한다.

import java.util.*;
class Solution {
    
    /**
    The DNA sequence is composed of  a series of nucleotides 
    'A', 'C','G','T'
    1.  it has to be DNA sequence which is "more than once" ! occured in the DNA molecule
    2. LENGTH is 10!! 
    */
    public List<String> findRepeatedDnaSequences(String s) {
        // IF molecule is shorter than 10 -->  
        List<String> ans = new ArrayList<>();
        if(s.length()<10) return ans; 
        Map<String,Integer> map = new HashMap<>();
        String cur ="";
        int windStart=0;
        
        //have to use HashMap : to store (specific sequence, the number of occur)
        for(int windEnd=0;windEnd<s.length();windEnd++){
            cur+= Character.toString(s.charAt(windEnd));
            // CHECK ONLY in the case of that the length of window is 10 - FIXED SIZE WINDOW 
            // WHEN SHRINK ???? There's no need to shrink in this problem
						// 길이가 고정된 윈도우이기 때문에, 한 번 10의 길이가 되면 오른쪽으로 sliding만 해주면된다. 
            if(windEnd-windStart+1 ==10){
                // Once reach this point, just slide window.
                int numb= map.getOrDefault(cur,0);
                if(numb==1){
                    ans.add(cur);
                
                map.put(cur,numb+1);
                windStart++;
                cur = cur.substring(1);
            }
        }
        return ans;
    }

다른 사람들의 풀이를 보고 개선해보기

• Fixed Window 문제이기 때문에 windStart변수가 사실 필요하지 않다.
• 대신 윈도우를 움직이는 것은, window가 만들어질 수 있는 경우, 즉 s의 길이가 10이상은 되어야지만 가능한 것이다.

import java.util.*;
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
         List<String> ans = new ArrayList<>();
        if(s.length()<10) return ans; 
        Map<String,Integer> map = new HashMap<>();
        String cur ="";
        
        for(int windEnd=10;windEnd<=s.length();windEnd++){
            cur = s.substring(windEnd-10,windEnd);        
            int numb= map.getOrDefault(cur,0);
            if(numb==1){
                ans.add(cur);
            }
            map.put(cur,numb+1);
             
        }
        return ans;
        
    }
}

그리고, 하나 이상한점

Constraints:

• 1 <= s.length <= 105
• s[i] is either 'A', 'C', 'G', or 'T'.
• 그리고 이 사이트 제약 조건 자체가 s의 길이는 10만 이하다. 라고 적혀있는데, 여기서 2ms가 나오는 코드를 보면 이런식으로 해줘야 한다... 흠..

if(s.length()==100000 ||s.length()<10) return ans;
이거나
if(s.length()>=100000 ||s.length()<10) return ans;
이거나 둘다 2ms가 나온다. 

뭘까....