HackerRank 문제풀이 - 10 (Two Strings)

1. 문제

문제는 다음과 같다.

두 string이 주어졌을때, 공통되는 문자가 있으면 “YES”, 없으면 “NO” 를 출력해야 한다.

 

 

 

 

2. 1차 문제풀이

2.1 풀이 과정

function twoStrings(s1, s2) {
    // Write your code here
    const splitS1 = s1.split("");
    const splitS2 = s2.split("");
    
    var result = false;
    splitS1.forEach((char)=>{
        if(splitS2.indexOf(char) !== -1){
            result = true;
            return;
        }
    })

    return result? "YES": "NO";
}

풀이 과정은 다음과 같다.

• “result” 변수를 false로 초기화한다.
• 주어진 두 문자 “s1”, “s2”를 split하여, char list로 변환한다.
• 한 문자 char list를 순회한다
  • 다른 문자의 char list와 공통되는 character가 있으면 “result” 값을 true로 설정하고 순회를 종료한다.
• “result”변수의 값에 따라 “YES” 혹은 “NO”를 반환한다.

 

 

2.2 풀이 결과

일반적으로 순회하는 방법을 사용하니, 대량의 값을 다룰때는 Time limit으로 실패하였다.

알고리즘을 개선하여, 문제 해결 성능을 높여야 했다.

 

 

 

3. 2차 문제풀이

3.1 풀이 과정

function twoStrings(s1, s2) {
    // Write your code here
    const setS1 = new Set(s1);
    
    for(let char of s2){
        if(setS1.has(char)){
            return "YES";
        }
    }
    
    return "NO";
}

풀이 과정은 다음과 같다.

• 주어진 “s1” string값을 “Set”형식으로 변환한다.
• 주어진 “s2” string을 “for()” 메서드로 값을 순회한다.
  • “Set”형식의 “has()”메서드를 이용하여, 다른 string에 포함된 문자인지 확인한다
    • 다른 string에 포함된 문자이면 “YES”를 반환한다.
• 마지막까지 순회를 돌았을때, 포함된 문자가 없으면 “NO”를 반환한다.

 

이로써 1차 풀이 대비 성능상 개선된 사항은 다음과 같다:

1. “Set”형식을 사용하여 문자열의 문자들을 고유한 값으로 저장
2. “Set”형식을 통해 내부적으로 해시 테이블을 사용하여 멤버십 확인의 효율성 증대
3. 비효율적이었던 forEach순회방식 및 “indexOf()” 메서드를 통한 검색 수행 방식 폐기

이에 대한 성능상의 차이는 배열의 크기가 커질수록 큰 영향을 끼치므로, 개선사항을 통해 좋은 결과를 기대할 수 있게 되었다.

 

 

 

3.2 풀이 결과

이와 같이 로직을 수정하니 모든 Test case가 통과됨을 확인할 수 있었다.

데이터 구조와 선회 방식의 차이가 성능에 어떻게 영향을 끼치는지 몸소 느끼며 공부할 수 있던 시간이었다.