pjaehyun의 개발일지

문제

https://leetcode.com/problems/push-dominoes/

There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

• dominoes[i] = 'L', if the ith domino has been pushed to the left,
• dominoes[i] = 'R', if the ith domino has been pushed to the right, and
• dominoes[i] = '.', if the ith domino has not been pushed.

Return a string representing the final state.

1. n개의 도미노가 주어지고, 각 도미노는 수직으로 세워져있고, 각 도미노는 동시에 왼쪽 또는 오른쪽으로 밀린다.

2. 왼쪽으로 쓰러지는 도미노는 왼쪽에 인접한 도미노를 밀어내고, 오른쪽으로 쓰러지는 도미노는 오른쪽에 인접한 도미노를 밀어낸다.

3. 양쪽으로 동시에 도미노가 쓰러질 때 힘의 균형으로 인해 수직인 도미노는 유지된다.

dominoes의 초기상태를 나타내는 문자열이 제공된다.

• dominoes[i] = 'L', 도미노가 왼쪽으로 밀릴 때
• dominoes[i] = 'R', 도미노가 오른쪽으로 밀릴 때
• dominoes[i] = '.', 도미노가 밀리지 않았을 때

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        dominoes = list(dominoes)
        right = -99
        i = 0
        
        while i < len(dominoes):
            if dominoes[i] == '.':
                i+=1
                continue
            elif dominoes[i] == 'L':
                if right < 0:
                    for j in range(i-1, -1, -1):
                        if dominoes[j] != '.':
                            break
                        else:
                            dominoes[j] = 'L'
                elif right >= 0 and right + 1 != i - 1 and right + 1 != i:
                    mid = ((i - right) // 2) + right
                    for j in range(right+1, mid+1 if (i-right) % 2 > 0 else mid):
                        dominoes[j] = 'R'
                    for j in range(mid+1, i):
                        dominoes[j] = 'L'
                right = -99
                i += 1
            elif dominoes[i] == 'R':
                if right >= 0:
                    for j in range(right+1, i+1):
                        dominoes[j] = 'R'
                right = i
                i+=1
        if right >= 0:
            for j in range(right+1, i):
                dominoes[j] = 'R'
                
        return ''.join(dominoes)

투포인터 방식으로 문제 접근

1. '.'을 만났을 때

  - i+1을 해준다.

2. 'L'을 만났을 때: right를 안만났을 때로 초기화하고, i + 1을 해준다

  - R을 만나지 않고 연속으로 L을 만났을 경우

      -> 현재 위치에서 하나씩 L로 바꾸면서 뒤로간다. '.'이 아닌 다른문자가 나오면 루프를 빠져나온다

  - 이전에 R이 존재했고, L을 만났을 경우

      -> 현재 R의 위치 + 1이 현재 L의 위치 - 1일 때, 현재 R의 위치 + 1이 i와 같을 때는 도미노가 쓰러지지 않는다

      -> R과 L은 동시에 쓰러지기 때문에 R과 L의 중간값을 구해서 R은 중간값 까지 'R'로 바꾸고 L은 중간값 + 1부터 현재 위치까지 'L'로 바꾼다

3. 'R'을 만났을 때: right를 현재위치로 초기화하고, i + 1을 해준다

  - L을 만나지 않고 연속으로 R을 만났을 경우

      -> 이전에 right값이 0보다 크고 현재위치가 아닐 때 R의 이전위치부터 현재위치까지 'R'로 바꿔준다

4. 루프를 빠져나오고 right값이 0보다 크면 right + 1부터 마지막까지 도미노를 오른쪽으로 'R'로 바꿔준다.

** 투포인터 방식으로 풀었지만 조건을 하나씩 다 처리하다보니 코드도 길어지고 가독성도 많이 떨어진거같음... 다음에 다시 보면서 줄일 수 있는건 줄이고 파이썬답게 풀어봐야겠다

문제

https://leetcode.com/problems/container-with-most-water/

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

길이가 n인 정수 배열 높이가 제공됩니다. i번째 선의 두 끝점이 (i, 0) 및 (i, height[i])가 되도록 n개의 수직선이 그려집니다.
컨테이너에 가장 많은 물이 담을 수 있도록 x축과 함께 컨테이너를 형성하는 두 개의 선을 찾아 담을 수 있는 최대 물의 양을 반환한다.

Example 1:

문제풀이 코드

첫번째 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer = [0 for _ in range(len(height))]
        for i in range(len(height) - 1):
            for j in range(i+1, len(height)):
                answer[i] = max(answer[i], (min(height[i], height[j]) * (j-i)))
        return max(answer)

모든 선을 탐색(완전탐색)하여 가장 큰 값을 리턴하는 코드, 타임아웃에러로 실패..

두번째 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height)-1
        answer = 0
        
        while True:
            if i == j:
                break
            answer = max(answer, min(height[i], height[j]) * (j - i))
            if height[i] <= height[j]:
                i += 1
            elif height[j] < height[i]:
                j -= 1
        return answer

완전탐색이 실패하여 투포인터로 풀어보았다.

1. i는 배열의 첫번째 값, j는 배열의 마지막 값을 바라보도록 인덱스 설정

2. 기존 answer값과 새로운 물의 크기중 더 큰 값을 answer에 삽입

3. height[i]가 height[j]보다 작거나 같으면 i에 1을 더해주고

4. height[j]가 height[i]보다 작으면 j에 1을 빼준다.

5. i와 j가 같을 때 루프를 종료하고 answer를 리턴해준다.

문제

https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        return int(''.join([format(x, 'b') for x in range(1, n+1)]), 2) % 1000000007

1. 1부터 n까지의 원소들을 2진수로 리스트에 저장하여 join을 통해 하나의 문자열로 만들어준다.

2. 만들어진 2진수를 10진수로 변환하고 10^9 + 7의 나머지를 구한다.

문제

https://leetcode.com/problems/reverse-words-in-a-string-iii/

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

문자열 s가 주어지면 공백과 초기 단어 순서를 유지하면서 문장 내 각 단어의 문자 순서를 반대로 뒤집는다.

예제 1

문제풀이 코드

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join([''.join(reversed(list(x))) for x in s.split(' ')])

1. 문자열 s를 띄어쓰기로 split한다

2. x를 리스트로 변환하고 reversed한다.

3. 뒤집어진 리스트를 다시 문자열로 바꾸고 각 단어를 띄어쓰기로 합쳐준다.

문제

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Given a string s, find the length of the longest substring without repeating characters.

1. 문자열 s가 주어지고, 연속으로 다른 알파벳이 나오는 가장 긴 문자열을 찾아라.

문제풀이 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) <= 0:
            return 0
        result = [0 for _ in range(len(s))]
        idx = 0
        s = list(s)
        while s:
            char = s.pop(0)
            lst = [char]
            for i in range(len(s)):
                if char == s[i] or s[i] in lst:
                    break
                lst.append(s[i])
            result[idx] = len(lst)
            idx += 1
        return max(result)

1. 문자열의 각 문자별로 최대 길이를 담는 리스트를 생성

2. 문자열 s의 첫번째 문자를 pop한다

3. 뽑혀나온 문자를 문자열s의 요소들을 하나씩 비교

4. char과 s[i]가 같거나 s[i]가 lst에 들어있다면(중복되어있다) for루프를 빠져나온다

5. 둘다 아니라면 lst에 s[i]를 삽입

6. for루프가 정상적으로 종료되었을 때 lst는 char로 시작하는 연속된 문자열이 들어가있다

7. lst의 길이를 result에 넣어준다

8. 문자열의 모든 문자별로 가질 수 있는 최대값이 result에 들어있으므로 max값을 return

문제

https://leetcode.com/problems/add-two-numbers/

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

1. 정수로 이루어져있고, 비어있지 않은 두개의 링크드 리스트가 제공된다.

2. 숫자를 포함하고 있는 각각의 노드는 역순으로 저장되어 있다.

3. 두 정수를 더한 결과를 연결리스트의 형태로 반환하라.

Example 1:

문제풀이 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        num1 = listNodeToNum(l1)
        num2 = listNodeToNum(l2)
        values = list(str(num1 + num2))
        values.reverse()
        lstNode = ListNode(values.pop(0))
        for v in values:
            lstNode = insertNode(lstNode, v)
        return lstNode
        
def insertNode(curr, val):
    if (curr == None):
        return ListNode(val)
    else:
        curr.next = insertNode(curr.next, val)
    return curr

def listNodeToNum(listNode):
        res = []
        while listNode != None:
            val = listNode.val
            listNode = listNode.next
            res.append(str(val))
        res.reverse()
        return int(''.join(res))

1. Explanation을 보면 l1, l2에 담긴 value들을 뒤집어서 더하고 다시 뒤집으면 정답이 나옴

2. ListNode에 담긴 모든 value들을 꺼내서 뒤집은 값을 주는 함수(listNodeToNum) 생성

3. 결과 값은 ListNode로 보내야 하기 때문에 ListNode에 값을 추가하는 함수(insertNode) 생성

3. l1, l2의 뒤집어진 값을 더한다

4. 더해진 값 리스트로 변환하여 다시 뒤집는다

5. 루프를 돌면서 values에 들어있는 값을 하나씩 ListNode에 추가해준다

문제

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

1. 정렬된 수의 배열이 주어졌을 때 중복을 제거한 배열의 길이를 반환해라

2. 새로운 배열을 생성하는 것은 안된다

3. 공간복잡도는 O(1)을 유지

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

문제풀이 코드

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        k = 0
        for i in range(1, len(nums)):
            if nums[k] != nums[i]:
                result += 1
                nums[k] = nums[i]

        return k + 1

1. nums의 k번째 값을 i번째 값과 비교

2. k번째 값과 i번째 값이 다를경우 k+1번째와 i번째 값을 스왑

3. k값은 이동이 일어난 수를 의미하니 + 1 을 하면 배열의 길이가 나옴

4. k + 1값을 리턴

문제

https://leetcode.com/problems/valid-parentheses/

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

(),{},[]로 이루어진 문자열이 주어졌을 때 해당 문자열이 유효한지 확인해라.

    1. 열린 괄호와 닫힌 괄호는 같은 유형의 괄호여야한다.

    2. 열린 괄호는 올바른 순서대로 닫아야한다.

    3. 모든 닫힌 괄호는 같은 유형의 열린 괄호가 존재한다.

문제풀이 코드

class Solution:
    def isValid(self, s: str) -> bool:
        s = list(s)
        stack = []
        stack.append(s.pop(0))
        while s:
            if not stack:
                stack.append(s.pop(0))
            if not s:
                return False
            if stack[-1] == '(' and s[0] == ')' or stack[-1] == '{' and s[0] == '}' or stack[-1] == '[' and s[0] == ']':
                stack.pop()
                s.pop(0)
            else: 
                stack.append(s.pop(0))
        if stack:
            return False
        return True

풀이방법: stack

1. 주어진 문자열을 리스트로 변경

2. stack 초기화 -> 비교를 위해 리스트의 첫번째 인자를 stack에 담아준다

3. s에 값이 존재할 때 stack이 비어있으면 stack에 값 추가

4. s에 값이 존재하지 않으면 False를 리턴 

5. stack에 들어있는 마지막 값과 리스트s의 첫번째 값이 상응하는 괄호이면 stack과 s에서 제거

6.stack에 값이 존재하면 일치하지 않는 괄호가 존재함으로 False를 리턴

7. 리스트s가 존재하지 않을때까지 반복