[코테] 리트코드 파이썬 49번, 46번, 48번 - permutations 등

46번 Permutations

Permutations - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

정수 array의 라이브러리를 사용하지 않고 permutations을 모두 구하는 문제이다.

 

특정 정수 array가 주어졌을 때 순서상 다음 permutations을 return하는 함수를 사용하여 전체 순열을 구했다. 이때 함수를 호출하는 횟수는 array의 길이를 통한 팩토리얼 계산으로 수행하였다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result=[]
        answer=1
        for i in range(1,len(nums)+1):
            answer*=i

        def nextPermutation(nums: List[int]) -> None:
            n=len(nums)
            for i in range(len(nums)-1,0,-1):
                if nums[i]>nums[i-1]:
                    j=i
                    while j<n and nums[j] >nums[i-1]:
                        idx=j
                        j+=1
                    nums[idx],nums[i-1]=nums[i-1],nums[idx]

                    for k in range((n-i)//2):
                        nums[n-k-1],nums[i+k]=nums[i+k],nums[n-k-1]
                    break
            else:
                nums.reverse()

            return nums

        for i in range(answer):
            check=nextPermutation(nums)
            result.append(check)
            nums=list(check)


        return result

 

---

48. Rotate Image

Rotate Image - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

matrix를 시계 방향으로 90도 뒤집는 문제이다.

 

주어진 2차원 배열을 column 단위로 읽어, 거꾸로 뒤집어서 결과 matrix의 한 행으로 구성하면 90도로 뒤집은 결과물이 나오는 것을 활용하였다.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        check=len(matrix)
        for i in range(check):
            result=[]
            for j in range(check):
                result.append(matrix[j][i])
            result.reverse()
            matrix.append(list(result))

        for i in range(check):
            matrix.pop(0)

 

---

49. Group Anagrams

Group Anagrams - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

문자열의 구성 문자가 같은 그룹끼리 묶어 리스트로 구성한 뒤 return하는 문제이다.

 

처음 시도는, 문자열을 set으로 바꿔, 같은 그룹인지 확인하는 코드를 짰지만, 구성 문자는 같으나 각 문자의 개수가 다른 케이스를 통과하지 못했다. 이때 딕셔너리는 각 그룹의 문자열들을 저장하는 용도로 작성하였다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        resultss=[]
        dicts=dict()
        for strss in strs:
            result=set([i for i in strss])
            for i in dicts.keys():
                if set([j for j in i])==result:
                    dicts[i].append(strss)
                    break
            else:
                dicts[strss]=[strss]
            #print(dicts)

        for i in dicts.values():
            resultss.append(i)
        return resultss

 

 

각 문자의 종류뿐만 아니라 개수도 파악해야 한다는 문제 해결을 위해, 다른 접근 방식으로  주어진 문자열을 정렬하여 비교한다면 같은 그룹인지 쉽게 확인할 수 있다. 이때의 딕셔너리는 각 그룹의 위치를 저장한다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result=[]
        dicts=dict()

        for s in strs:
            sorted_str = ''.join(sorted(s))
            if sorted_str in dicts:
                result[dicts[sorted_str]].append(s)
            else:
                dicts[sorted_str] = len(result)
                result.append([s])
                
        return result