파이썬 알고리즘 인터뷰 - Day 5 #1

원종운·2020년 8월 31일
algorithm

자신 이전의 수의 합

  • 입력 : nums = [1, 2, 3, 4]
  • 출력 : [1, 3, 6, 10]

풀이 1) 누적

  • 실행 속도 : 28 ms
  • 요소를 방문하면서 이전의 요소들의 합을 누적하여 계산하는 방식
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        p: int = 0
        result: List[int] = []

        for num in nums: # for loop
            p += num # accumulate num
            result.append(p) # add elem at list
            
        return result # return list

풀이 2) itertools 사용

  • 실행 속도 : 28 ms
  • itertools의 accmulate 사용
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        return list(itertools.accumulate(nums))

사탕 부자

  • 입력 :
    • candies = [2,3,5,1,3]
    • extraCandies = 3
  • 출력 : [true, true, true, false, true]
  • 설명 : [ 2 + 3 >= 5, 3 + 3 >= 5, 5 + 3 >= 5, 1 + 3 >= 5, 3 + 3 >= 5]

풀이 1) 단순 비교

  • 실행 속도 : 36 ms
  • 사탕의 수의 배열을 순회하면서 여분의 사탕 수를 더해서, 이전의 가장 많이 사탕을 가진 아이보다 큰지를 검사
class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
    	# calculate max candy
        max_candies: int = max(candies)        
        return [True if (candy + extraCandies) >= max_candies else False for candy in candies]

좌표 매칭

  • 입력 :
    • nums = [2,5,1,3,4,7]
    • n = 3
  • 출력 : [2,3,5,4,1,7]

풀이 1) 상대적 위치

  • 실행 속도 : 64 ms
  • 매칭이 되는 좌표끼리 n만큼 인덱스가 떨어져있으므로, i번째와 i+n번째의 요소를 순서대로 더해주는 방식
class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        left = 0
        result: List[int] = []
        
        for index in range(n):
            result += [nums[index], nums[index + n]]
            
        return result

좋은 쌍의 찾기

  • 입력 : nums = [1,2,3,1,1,3]
  • 출력 : 4

풀이 1) 브루트포싱

  • 실행 속도 : 28 ms
  • 기준이 되는 지점부터 끝까지를 비교하여 조건이 만족되는 쌍이 있으면 누적하면서 기준을 배열 끝 이전까지 증가시키면서 반복 
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:  
        pairs = 0
        
        for i in range(0, len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    pairs += 1
                    
        return pairs

풀이 2) 조합, Counter

  • 실행 속도 : 32 ms
  • 배열에서 각 수가 등장하는 횟수(n)를 Counter Object를 이용하여 구한 후, 그 수로 조건을 만족하는 쌍의 수는 C(n, 2)임을 이용
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:  
        return sum((val * (val-1)) // 2 for val in collections.Counter(nums).values())

defanged IP Address

  • 입력 : address = "1.1.1.1"
  • 출력 : "1[.]1[.]1[.]1"

풀이 1) 문자열 치환

  • 실행 속도 : 28 ms
  • str.replace()를 사용하여 '.'를 '[.]'로 치환
class Solution:
    def defangIPaddr(self, address: str) -> str:
        return address.replace('.','[.]')

0 만들기

  • 입력 : num = 14
  • 출력 : 6

풀이 1) 기본 구현

  • 실행 속도 : 32 ms
  • 주어진 조건대로 홀수이면 1을 빼고, 짝수이면 2를 나눌때마다 회수 누적
class Solution:
    def numberOfSteps (self, num: int) -> int:
        step = 0
        
        while num:
            num, step = num - 1 if num % 2 else num >> 1, step + 1

        return step

문자열 섞기

  • 리트코드 1528번 문제 : https://leetcode.com/problems/shuffle-string/
  • 섞인 문자열의 i번째 문자는 주어진 인덱스 배열의 i번째 값을 가지는 인덱스의 요소를 만족한다. 섞인 문자열을 구하여라.
  • 입력 :
    • s = "codeleet"
    • indices = [4,5,6,7,0,2,1,3]
  • 출력 : "leetcode"
  • 설명 :

풀이 1) 기본 구현

  • 실행 속도 : 56 ms
  • 주어진 조건에 맞게 작성
class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        result = [''] * len(indices)
        
        for index, value in enumerate(indices):
            result[value] = s[index]
            
        return ''.join(result)

풀이 2) zip 함수

  • 실행 속도 : 60 ms
  • 시퀀스 형인 문자열 s와 리스트 indices를 zip 함수를 사용하여 순차적으로 튜플 쌍으로 묶은 후, index 기준으로 정렬한 후, 튜플 중 문자만 join으로 합치는 방식
class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        return ''.join([char[1] for char in sorted(list(zip(indices, s)))])
profile
원종운
Java, Python, JavaScript Lover
이전 포스트

파이썬 깨알 상식

다음 포스트

파이썬 알고리즘 인터뷰 - Day 6 #1

0개의 댓글