중복 문자 없는 가장 긴 부분 문자열

3. Longest Substring Without Repeating Characters

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

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

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = "" Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

-----------------------------------------------------------------------------------------------------------------------------------

# 풀이 1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절
def lengthOfLongestSubstring(self, s: str) -> int:
    used = {}
    max_length = start = 0
    for index, char in enumerate(s):

        # 이미 등장했던 문자라면 'start' 위치 갱신
        if char in used and start <= used[char]:
            start = used[char] + 1

        else: # 최대 부분 문자열 길이 갱신
            max_length = max(max_length, index - start + 1)

        # 현재 문자의 위치 삽입
        used[char] = index
    return max_length

중복 문자 제거

316. Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: s = "bcabc" Output: "abc"

Example 2:

Input: s = "cbacdcbc" Output: "acdb"

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

-----------------------------------------------------------------------------------------------------------------------------------

풀이 1. 재귀를 이용한 분리

def removeDuplicateLetters(self, s:str) -> str:
    #집합으로 정렬
    for char in sorted(set(s)):
        suffix = s[s.index(char):]
        #전체 집합과 접미사 집합이 일치할 때 분리 진행
        if set(s) == set(suffixx):
            return char + self.removeDuplicateLetters(suffix.replace(char, ''))
    return ''

풀이 2. 스택을 이용한 문자 제거

def removeDuplicateLetters(self, s: str) -> str:
    counter, seen, stack = collections.Counter(s), set(), []

    for char in s:
        counter[char] -= 1
        if char in seen:
            continue
        #뒤에 붙일 문자가 남아 있다면 스택에서 제거
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            seen.remove(stack.pop())
        stack.append(char)
        seen.add(char)

    return ''.join(stack)

H-Index

https://programmers.co.kr/learn/courses/30/lessons/42747

[문제 설명]

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고
합니다. 위키백과(https://en.wikipedia.org/wiki/H-index)에 따르면, H-Index는 다음과 같이 구합니다.

 - 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면    
    h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

[제한사항]

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

[입출력 예]

[입출력 예 설명]

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다.

그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

나의 풀이

def solution(citations):
    answer = 0
    max_num = max(citations)
    
    for h in range(max_num, 0, -1):
        if len([x for x in citations if x >= h]) >= h:
            return h
    return answer

다른 사람들의 Best 풀이

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

세상에 이렇게 간단하게,,, 열심히 더 공부해야겠다!

큐를 이용한 스택 구현

225. Implement Stack Using Queues

https://leetcode.com/problems/implement-stack-using-queues/

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 2, 2, false] Explanation MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

-----------------------------------------------------------------------------------------------------------------------------------

풀이. push()할 때, 큐를 이용해 재정렬

class MyStack:
    def __init__(self):
        self.q = collections.deque()

    def push(self, x):
        self.q.append(x)
        #요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q) -1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

연결된 리스트 뒤집기

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2] Output: [2,1]

Example 3:

Input: head = [] Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

-----------------------------------------------------------------------------------------------------------------------------------

풀이 1. 재귀 구조로 뒤집기

def reverseList(self, head: ListNode) -> ListNode:
    def reverse(node: ListNode, prev: ListNode = None):
        if not node:
            return prev
        next, node.next = node.next, prev
        return reverse(next, node)
    
    return reverse(head)

풀이 2. 반복 구조로 뒤집기

def reverseList(self, head: ListNode) -> ListNode:
    node, prev = head, None
    
    while node:
        next, node.next = node.next, prev
        prev, node = node, next
    
    return prev

유효한 괄호

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = [] Output: []

Example 3:

Input: l1 = [], l2 = [0] Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

-----------------------------------------------------------------------------------------------------------------------------------

풀이. 재귀 구조로 연결

def mergeTwoLists(self, l1:ListNode, l2: ListNode) -> ListNode:
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1
    if l1:
        l1.next = self.mergeTwoLists(l1.next, l2)
    return l1

로그 파일 재정렬

937. Reorder Data in Log Files

https://leetcode.com/problems/reorder-data-in-log-files/

Write a function that reverses a string. The input string is given as an array of characters s.

Example 1:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

Constraints:

• 1 <= s.length <= 105
• s[i] is a printable ascii character.

Follow up: Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

• Letter-logs: All words (except the identifier) consist of lowercase English letters.
• Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering.

Return the final order of the logs.

Example 1:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"] Explanation: The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig". The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".

Example 2:

Input: logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"] Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Constraints:

• 1 <= logs.length <= 100
• 3 <= logs[i].length <= 100
• All the tokens of logs[i] are separated by a single space.
• logs[i] is guaranteed to have an identifier and at least one word after the identifier.

-----------------------------------------------------------------------------------------------------------------------------------

풀이 1. 람다와 + 연산자를 이용

def reorderLogFiles(self, logs: List[str]) -> List[str]:
    letters, digits = [], []
    for log in logs:
        if log.split()[1].isdigit():
            digits.append(log)
        else:
            letters.append(log)

    # 2개의 키를 람다 표현식으로 정렬
    letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits

문자열 뒤집기

344. Reverse String

https://leetcode.com/problems/reverse-string/

Write a function that reverses a string. The input string is given as an array of characters s.

Example 1:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

Constraints:

• 1 <= s.length <= 105
• s[i] is a printable ascii character.

Follow up: 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. 투 포인터를 이용한 스왑

def reverseString(self, s: list[str]) -> None:
    left, right =0, len(s) -1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

풀이 2. 파이썬 다운 방식

def reverseString(self, s: list[str]) -> None:
    s.reverse()