[python3] 859. Buddy Strings

풀이 일자: 23.07.03

난이도: [Easy]

분류: [Hash]

문제 내용

2개의 string이 주어지고 s에서 2 문자의 자리를 바꿨을 때 goal이 될 수 있는지 리턴하는 문제이다.

 

문제 해결 흐름

1. 일단 불가능한 경우과 가능한 경우가 있을텐데 불가능한 경우의 경우의 수가 훨씬 많을 것이다. 

→ 크게 나누면 len이 다른 경우, len이 같은데 들어가 있는 문자 수가 다른 경우, 자리를 바꾸더라도 불가능한 문자인 경우 이렇게 나눌 수 있을 것이다.

 

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        sc = Counter(s);
        gc = Counter(goal);
        
        if sc != gc: # 크기가 다르거나 문자의 갯수가 다른 경우
            return False;
        else:
            if s == goal: # s와 goal이 같은 문자이고 s에 같은 문자가 2개이상 있는 경우 무조건 가능
                for i in sc.values():
                    if i >=2:
                        return True;

        idx = -1;
        for i in range(len(s)): # 바꾸더라도 같지 않은 경우 찾기 위한 for문.
            s = list(s)
            if s[i] != goal[i]:
                if idx == -1:
                    idx = i;
                else:
                    s[i], s[idx] = s[idx], s[i];
                    return True if "".join(s)==goal else False;
        return False;

→ Easy문제였지만 고려해야할 예외사항이 여럿 있었고 알고리즘 문제라기보다는 구현 문제에 가까운 것 같다. 실제로 정답률이 크게 낮았다.

 

Time Complexity:  O(N²)

시간복잡도는 밖의 for문과 join을 이용했기 때문에 N^2의 시간복잡도를 가진다고 봐야한다.

 

Space Complexity: O(N)

Counter라는 함수를 사용하여 dictionary를 만들었기 때문에 최대 N의 시간복잡도를 가질 것이다.

 

 

다른 해결 방식

1. 범위를 좁혀놓고 바꿔서 처리하자.(다른사람 풀이)

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        n = len(s)
        if s == goal:
            temp = set(s)
            return len(temp) < len(goal)

        i = 0
        j = n - 1

        while i < j and s[i] == goal[i]:
            i += 1

        while j >= 0 and s[j] == goal[j]:
            j -= 1

        if i < j:
            s_list = list(s)
            s_list[i], s_list[j] = s_list[j], s_list[i]
            s = ''.join(s_list)

        return s == goal

→ 여러 예외사항에 대한 처리를 하지 않고 간결하게 처리한 방식인 듯.

 

Time Complexity:  O(N)

그대로 N의 시간복잡도를 가질 것이다.

 

 

Space Complexity: O(N)

공간복잡도는 s의 고유한 글자의 length만큼의 복잡도를 가질 것이다.

 

 

문제 링크

https://leetcode.com/problems/buddy-strings/description/

Buddy Strings - LeetCode