[codesignal] commonCharacterCount

반응형
반응형

Given two strings, find the number of common characters between them.

Example

For s1 = "aabcc" and s2 = "adcaa", the output should be
commonCharacterCount(s1, s2) = 3.

Strings have 3 common characters - 2 "a"s and 1 "c".

Input/Output

  • [execution time limit] 0.5 seconds (cpp)

  • [input] string s1

    A string consisting of lowercase English letters.

    Guaranteed constraints:
    1 ≤ s1.length < 15.

  • [input] string s2

    A string consisting of lowercase English letters.

    Guaranteed constraints:
    1 ≤ s2.length < 15.

  • [output] integer

 

새로운 사이트를 찾았다. 코드 시그널이라는 사이트로 코딩 공부하기에 딱 좋은 사이트라 생각이 든다.

이제 백준문제를 올리는 것 보다 여기 문제를 올릴 것 같은데....ㅎㅎ

웹IDE도 훌륭하고(자동 완성도 지원한다.)

프로그래머스같은 UI 를 지원한다.

하지만 흠이라면 영어라는 게 흠이다. 아직 문제들이 그리 어렵지는 않지만 ..ㅎㅎ

아무튼 이 문제는

2개의 문자열이 주어지는데 같은 문자가 몇개인지 찾는 문제다.

나는 c++로 구현하였다.

근데 별로 마음에 들지 않는다.

int commonCharacterCount(std::string s1, std::string s2) {
    
    int count = 0;
    
    std::sort(s1.begin(),s1.end());
    std::sort(s2.begin(),s2.end());
    
    for(int i = 0;i<s1.size();i++) {
        for(int j = 0; j<s2.size();j++) {
            if (s1[i] == s2[j]) {
                count++;
                s2.erase(s2.begin()+j);
                break;
            }
        }
    }
    
    return count;
}

std가 거슬리긴 하지만 여기에서는 귀찮기도하고 그냥 사용해도 괜찮을거라 생각했다.

일단 정렬하였다.

왜냐하면 정렬하는 이유는

bcx axb 라는 문자열이 주어졌을때 정렬을 사용하게 되면

b c x

a b x 가 된다. 더 빨리 찾기 위해 정렬을 사용했다.

근데 문제는 정렬만 하게 되면 알파벳의 위치가 다를 경우

정확한 답이 나오지 않는다. 어쩌면 위 경우는 0이 나올지도 모른다.

그래서 이중 포문을 사용해서 이를 해결 하려고 했다.

하지만 이중 포문을 사용했기 때문에 모든 경우의 수가 검색이 된다.

즉 a a a 

    a b c 라는 식이 있다면 두 번째 abc의 a는 3번이 검색 당하기?때문에 결과적으로 

3이라는 오답이 나온다.

이를 방지하기 위해 break를 걸어 만약 2번째에서 그 값을 찾았다면 다시는 그 값을 검색하지 않게 만들었다.

break를 거는 것까지는 괸찮은데 문제가 발생했다.

완벽히 순서가 일치하지 않는 이상 오답이 나온다.

그래서 어쩔 수 없이 그 값을 지우는 것으로 결정했다.

즉, 그 값을 찾으면 지워지기 때문에 결과적으로 순서가 달라져도 값을 찾을 수 있게 되었다.ㅎㅎ

 

이 사이트는 복사가 되지 않기 때문에 어쩔 수 없이 캡처하였다. 내가 타이핑해도 되지만... 귀찮아서...

이건 더 간단하다.

s1과 s2를 배열로 저장시킨다. 그러면 a는 몇개 b는 몇개 ... z는 몇개 등등 이 나온다.

그리고 알파벳숫자 만큼 돌린다.

근데 문제는 s1에는 a가 2개 존재하지만 s2에는 3개 존재한다면 어떻게 될까

s1과s2가 일치하는 알파벳은2개다. a가 3개일때는 2개는 반드시 포함되기 때문이다.

그러한 결과를 전부 더해주면 답이 나온다.

개인적으로 이분이 하신게 더 마음에 든다.

 

반응형

'알고리즘' 카테고리의 다른 글

[codeSignal] avoidObstacles  (0) 2020.07.18
[codesignal] isIPv4 address  (0) 2020.07.16
[codesignal] commonCharacterCount  (0) 2020.07.13
집합 알고리즘 구현  (0) 2020.07.07
[알고스팟] 문제 아이디 : RATIO 승률 올리기  (0) 2020.06.18
수의 비밀(2020.03.14)  (0) 2020.03.14

댓글(0)

Designed by JB FACTORY