[Mock] Facebook 10

859. Buddy Strings

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

My Answer 1: Accepted (Runtime: 36 ms - 50.92% / Memory Usage: 14.5 MB - 71.88%)

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        # 길이 다르면 X
        if len(s) != len(goal):
            return False
        
        # 알파벳 종류 다르면 X
        scnt = collections.Counter(s)
        gcnt = collections.Counter(goal)
        if scnt != gcnt:
            return False
        
        # two letters 넘어가면 X
        diff = []
        for i in range(len(s)):
            if s[i] != goal[i]:
                diff.append([s[i], goal[i]])
            if len(diff) > 2:
                return False
        
        # swap 가능한지 판단
        if len(diff) == 2:
            if diff[0][0] == diff[1][1] and diff[0][1] == diff[1][0]:
                return True
            else:
                return False
        
        # s == goal 의 경우, 알파벳이 2 개 이상이어야 swap 가능
        for v in scnt.values():
            if v > 1:
                return True
        
        return False

직접 swap 하는 건 넘 헤비할 거 같아서... 그냥 모든 경우를 확인해줌

우선 서로 길이 비교 => False / 서로 알파벳의 종류 비교 => False

s[i] != goal[i] 일 때의 값을 diff 에 넣어줌 => 길이가 2 개를 넘어가면 X

[a, b], [b, a] 처럼 크로스로 같으면 True / [a, c], [b, a] 처럼 다르면 False

s == goal 일 때는 개수가 2개 이상인 알파벳이 있으면 True
(같은 알파벳끼리 바꾸면 되니까)

나머지는 False

조각조각 끼워맞췄다~고 생각했는데 루션이랑 비슷해서 다행..~
루션이는 counter 대신 seen 을 활용함
알아두자!!

if s == goal:
    seen = set()
    for a in s:
        if a in seen:
            return True
        seen.add(a)
    return False

My Answer 2: Time Limit Exceeded (24 / 34 test cases passed.)

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        # 길이 다르면 X
        if len(s) != len(goal):
            return False
        
        s = list(s)
        for i in range(len(s)):
            for j in range(i+1, len(s)):
                s[i], s[j] = s[j], s[i]
                if ''.join(s) == goal:
                    return True
                s[i], s[j] = s[j], s[i]
        
        return False

조건이 넘 많아서 걍 고대로 swap 해봤는데 역시 타임리밋이군요..

---

1329. Sort the Matrix Diagonally

https://leetcode.com/problems/sort-the-matrix-diagonally/

My Answer 1: Accepted (Runtime: 84 ms - 75.38% / Memory Usage: 14.8 MB - 25.88%)

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        def func(i, j):
            self.list.append(mat[i][j])
            if i+1 < len(mat) and j+1 < len(mat[0]):
                func(i+1, j+1)
            else:
                self.list.sort()
            mat[i][j] = self.list.pop()
        
        self.list = []
        
        for i in range(len(mat)):
            if i == 0:
                for j in range(len(mat[0])):
                    func(i, j)
            else:
                func(i, 0)
        
        return mat

행렬의 맨 윗줄과 맨 왼쪽줄이 시작점이므로 그 값들만 재귀 돌리기

self.list 에 해당 대각선 값들을 다 넣어주고
다음 대각선값이 존재하면 그 값으로 재귀 넘어감

다음 대각선값이 존재하지 않으면 self.list sort 한 후,
가장 큰 값부터 pop 하면서 행렬값 바꿔주기
=> 대각선 끝 값 -> 시작 값 순서대로 바뀜