HackerRank 문제풀이 - 11 (Sherlock and Anagrams)

1. 문제

문제는 다음과 같다.

한 문자열의 문자를 재배열하여 다른 문자열을 형성할 수 있는 경우 두 문자열은 서로의 애너그램 이라고 한다. 문자열이 주어졌을때, 서로의 애너그램인 문자열의 하위 문자열 쌍의 수를 찾아야 한다.

 

 

2. 1차 문제풀이

2.1 풀이 과정

function sherlockAndAnagrams(s) {    
    let count = 0;
    
    for(let len = 1; len < s.length; len++){
        for(let i = 0; i < s.length - len; i++){
            const orgStr = s.substr(i, len);
            // console.log("orgStr:", orgStr);
            
            for(let j = i + 1; j <= s.length - len; j++){
                const compareStr = s.substr(j, len);
                // console.log("  compareStr:", compareStr);
                
                let orgStrList = orgStr.split("");
                let isContained = true;
                for(let k = 0; k < compareStr.length; k++){
                    const str = compareStr.charAt(k);
                    // console.log(`    str: ${str}, orgStrList:`, orgStrList);
                    
                    if(orgStrList.includes(str)){
                        orgStrList.splice(orgStrList.indexOf(str), 1);
                    } else {
                        isContained = false;
                        break;
                    }
                }
                
                if(isContained) {
                    // console.log(`    ## isContained! >> orgStr: ${orgStr}, compareStr: ${compareStr}`);
                    count++; 
                }
            }
        }
    }
    
    return count;
}

 

풀이 과정은 다음과 같다.

• 1부터 주어진 문자열의 길이 -1 만큼 반복문을 돈다.
  • 이로써 길이 1부터 주어진 문자열 길이 -1만큼 문자열을 쪼개, 각 문자열들의 하위 문자열들을 구한다.
  • 같은 길이의 다른 index의 하위 문자열도 구하여, 서로 애너그램이 형성되는지 파악한다.
• 파악된 애너그램의 수 값을 리턴한다.

 

 

2.2 풀이결과

결과는 성공했다. 하지만 문제의 주요 핵심인 Dictionary나 HashMap 타입을 사용하지 않았다.

이를 사용한 버전으로 코드를 수정해야 한다.

 

 

 

3. 2차 문제풀이

3.1 풀이과정

function sherlockAndAnagrams(s) {    
    let count = 0;
    
    const getSortedString = (str) => {
        return str.split('').sort().join('');
    }
    
    const substringMap = new Map();
    
    for(let len = 1; len < s.length; len++){
        for(let i = 0; i <= s.length - len; i++){
            const substring = s.substr(i, len);
            const sortedSubstring = getSortedString(substring);
            
            if (substringMap.has(sortedSubstring)) {
                count += substringMap.get(sortedSubstring);
                substringMap.set(sortedSubstring, substringMap.get(sortedSubstring) + 1);
            } else {
                substringMap.set(sortedSubstring, 1);
            }
        }
        
        substringMap.clear();
    }
    
    return count;
}

문자열을 잘라 배열에 넣고, sort()메서드를 통해 정렬을 수행한다. 그리고 Map타입을 사용하여 문자열 별로 애너그램 수를 저장한다.

 

두 개의 중첩된 루프를 사용하여 가능한 모든 부분 문자열을 반복한다. 바깥쪽 루프는 다양한 부분 문자열 길이를 반복하며, 안쪽 루프는 해당 길이의 각 부분 문자열을 반복한다.

• 각 부분 문자열마다 getSortedString 함수를 사용하여 부분 문자열을 정렬하고, 정렬된 부분 문자열이 substringMap에 이미 존재하는지 확인한다.
  • 만약 정렬된 부분 존재한다면, 해당 키의 값만큼 'count'를 증가시킨다. 이는 현재 부분 문자열과 같은 문자를 가지는 다른 부분 문자열들과 애너그램 쌍을 형성할 수 있기 때문이다.
  • 그런 다음, Map에서 정렬된 부분 문자열에 대한 값을 업데이트하여 값을 증가시킨다.
  • 만약 정렬된 부분 문자열이 Map에 존재하지 않는다면, 해당 키를 1로 설정하여 새로운 항목을 Map에 추가한다.
  • 특정 길이의 모든 부분 문자열을 처리한 후, Map을 초기화한다.
  • 마지막으로, 찾은 애너그램 쌍의 총 개수를 반환한다.

 

 

 

 

3.2 풀이 결과

문제 해결에 있어서 주어진 과제를 효과적으로 수행하기 위해 우리는 언어의 다양한 타입들을 올바르게 활용할 필요가 있다. 위 코드에서처럼, 문제를 Map타입을 활용하여 해결함으로써 복잡한 작업을 단순하게 처리할 수 있었다.

 

이와 같이 동일한 문제를 해결하더라도 선택한 언어의 기능과 타입들을 최대한 활용함으로써 더 높은 퀄리티의 소프트웨어를 개발할 수 있다. 올바른 자료구조와 타입의 활용은 코드의 가독성과 유지보수성을 향상시키며, 성능도 향상시킬 수 있다.