[Mock] Random 14

얘도 마존이 문제~

---

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: 436 ms - 11.73% / Memory Usage: 15 MB - 15.25%)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        two = []
        for i in range(len(nums)):
            if nums[i] in two:
                ans.append(two.index(nums[i]))
                ans.append(i)
                return ans
            two.append(target-nums[i])

답은 unique 한 값이니까 target - nums[i] 를 two 에 쭉 저장
two 에 있는 값을 발견하면 ans 에 짝꿍 인덱스와 지금 인덱스 넣어주기

어떻게 하면 더 빠르게 할 수 있을까 했지만.. 못찾음ㅠ

Solution 1: Accepted (Runtime: 60 ms - 23.57% / Memory Usage: 15.6 MB - 9.55%)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        
        for i in range(len(nums)):
            if nums[i] in dic:
                return [dic[nums[i]], i]
            else:
                dic[target - nums[i]] = i 

비슷한데
리스트에 넣는 것 보단 딕셔너리에 넣으면 한방에 해결 가능~

---

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: 32 ms - 94.47% / Memory Usage: 14.4 MB - 27.33%)

class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        nextCells = [0] * len(cells)
        times = n
        if n % 14 == 0:
            times = 14
        else:
            times %= 14
        for d in range(times):
            for i in range(1, len(cells)-1):
                if (cells[i-1] == 0 and cells[i+1] == 0) or (cells[i-1] == 1 and cells[i+1] == 1):
                    nextCells[i] = 1
                else:
                    nextCells[i] = 0
            for i in range(len(cells)):
                cells[i] = nextCells[i]
                
        return cells

이런 문제는 무조건 반복되는 게 있다고 보고 반복되는 기점을 찾음 => 14 일마다 반복됨

그래서 day 는 n%14 (14 로 나누어 떨어질 경우는 우선 14번 돌리긴 해야하니까 14)

나머지는 인접한 두 cell 이 둘다 0/1 이면 1 로, 아니면 0 으로 설정

이전 날의 기준이 있어야 하므로 nextCells 로 수정한 값을 매일 cells 에 복사