Today I Learned

오늘 할일
1. LeetCode
2. 강의??!!
3. 창의엔트리 업무
4. 인공지능 개론 과제

오늘 한일
1. 창의엔트리 업무

• 2차 담당학생 초대, 1차 공동문서 성적 업데이트

2. LeetCode

• 1657. Determine if Two Strings Are Close는 특정한 규칙으로 구성된 비슷한 문자열의 조건을 만족하는지에 대한 문제이다. 비슷한 문자열은 두 문자를 swap하는 행위가 범용적으로 허용되는데 글자 1개씩 swap과 글자 전체의 swap이 가능하다. 주안점은 1개씩 swap후 전체를 swap하는 둥 연속적인 처리과정 역시 고려해야한다는 점이다.

첫번째 접근으로, 마땅한 알고리즘이 생각나지 않아 TDD방식으로 접근하였다. 테스트 케이스 1~3을 만족하는 코드는 아래와 같다.

    public boolean closeStrings(String word1, String word2) {
        int size1=word1.length();
        int size2=word2.length();
        if(size1!=size2)
            return false;
        return true;
    }

두 문자열의 길이가 다른 경우엔 swap으로 해결이 안되기 때문이다.
그 결과

무려 100개가 넘는 테스트 케이스를 통과했다.

두번째 접근으로, 위에서 오류가 발생한 예시에는 문자열1에 없는 문자가 문자열2에 들어가있다는 것을 알 수 있었다. 고로 두 문자열을 set으로 만들어 서로 같은 문자로만 이루어졌는지 확인하였다.

        //TDD2. test case 108
        Set word1_chset=word1.chars().boxed().collect(Collectors.toSet());
        Set word2_chset=word2.chars().boxed().collect(Collectors.toSet());
        if(!word1_chset.containsAll(word2_chset) && !word2_chset.containsAll(word1_chset))
            return false;

세번째 접근으로, 더 나아가다가 현재 131번 testcase는 위의 알고리즘으로 걸러져야함을 알아차렸다. 위의 코드의 if 조건문을 ||로 수정했다.

네번째 접근으로, 위의 비교규칙에 의하면 문자의 빈도수가 다른 경우 현재의 swap규칙을 만족하지 못한다.

        //TDD3. test case 146
        //문자의 개수가 안맞을 경우 word1 a_2, b_2, c_1, z_2 / word2 a_1, b_2, c_1, z_3
        List word1_chlist=word1_chset.stream().toList();
        List word2_chlist=word2_chset.stream().toList();
        int[] word1_counts=new int[word1_chlist.size()];
        int[] word2_counts=new int[word2_chlist.size()];
        for(int c: word1.toCharArray()){
            word1_counts[word1_chlist.indexOf(c)]++;
        }
        for(int c: word2.toCharArray()){
            word2_counts[word2_chlist.indexOf(c)]++;
        }
        Arrays.sort(word1_counts);
        Arrays.sort(word2_counts);
        if(!Arrays.equals(word1_counts, word2_counts))
            return false;