[Mock] Amazon 5

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

My Answer 1: Accepted (Runtime: 48 ms - 62.85% / Memory Usage: 14.6 MB - 11.88%)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            # 중복 값일 때 index 겹치는 문제때문에 tmp 에 복사해주고 nums[i] 값은 변경해줌
            tmp = nums[i]
            nums[i] = float('inf')
            if target - tmp in nums:
                return [i, nums.index(target - tmp)]

투썸이가 마존이 문제였구만~

이중 for 문은 안썼지만 O(n^2) 인듯요~...

딕셔너리 써도 괜찮겠다 싶음

---

957. Prison Cells After N Days

There are 8 prison cells in a row and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.

Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.

You are given an integer array cells where cells[i] == 1 if the ith cell is occupied and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.

Return the state of the prison after n days (i.e., n such changes described above).

My Answer 1: Accepted (Runtime: 40 ms - 67.42% / Memory Usage: 14.3 MB - 30.63%)

class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        # 그럼 the first and the last cells 는 어쩌라는 의미인지...?
        
        def change(cells):
            # Copy cells -> prevCells
            prevCells = [0]*len(cells)
            for i in range(len(cells)):
                prevCells[i] = cells[i]
            
            # Change
            for i in range(1, len(cells)-1):
                if prevCells[i-1] == prevCells[i+1]:
                    cells[i] = 1
                else:                       # if prevCells[i-1] != prevCells[i+1]:
                    cells[i] = 0
            
            cells[0] = 0
            cells[-1] = 0
        
        # 14일 주기로 반복됨
        length = n%14
        if length == 0:
            length = 14
            
        for i in range(length):
            change(cells)
        
        return cells

첨에 case 1 개는 잘 통과됐는데 그 다음 case 마다 n 값이 1000000000, 300663720 이따구였음

그래서 아~~ 주기가 있겠구나~ 싶어서 쭉 훑어보니... 14 일을 주기로 값이 반복되덥니다.

근데 Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors. 라는데..............

the first and the last cells 는 걍 0 이 되는 게 맞는지 모르겠네요