문제

 

 

Solution.82 Remove Duplicates from Sorted List II

82. Remove Duplicates from Sorted List II
Solved
Medium
Topics
Companies
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

 

Example 1:


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


Input: head = [1,1,1,2,3]
Output: [2,3]
The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

 

range = 300 개 이므로 시간 복잡도는 넉넉히 존재가능하다.

 

 

 

 

위 표는 1초 동안 수행할 수 있는 최대 연산 횟수를 기준으로, 시간 복잡도를 분석한 결과를 나타낸다. 즉, 입력 크기가 300 이하일 때, 최적의 해결법을 찾기 위해 O(N3) 이상의 시간 복잡도를 고려해야 한다는 의미다.

 

풀이

  • 시간 복잡도: O(N)
  • 공간 복잡도: O(N)

시간 제한을 엄격히 두어 결국 문제를 풀지 못한 채 종료되었다. 접근 방식은 유사했지만, 마지막 마무리를 짓지 못한 점이 아쉬웠다.

이 문제에서 핵심은 ListNode를 이전(prev), 현재(curr), 다음(next) 총 세 개를 관리하며 비교하는 것이다. 만약 현재 노드(curr)와 다음 노드(next)의 값이 같다면, 이전 노드(prev)를 활용해 현재 노드를 삭제하고, 이후 노드들과 계속 비교해 나가는 것이 중요하다.

결국, 값을 어떻게 삭제하느냐에 따라 해결 방식이 달라지며, 삭제 과정만 명확하면 이후의 로직은 자연스럽게 동작한다.

 

 
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Iterative T.C O(N) & S.C O(1)
        dummy = ListNode(-1)
        dummy.next = head
        prev, curr = dummy, head
        while curr:
            if curr.next and curr.next.val == curr.val:
                while curr.next and curr.next.val == curr.val:
                    curr = curr.next
                prev.next = curr.next
            else:
                prev = prev.next
            curr = curr.next
        return dummy.next

 

'IT > 알고리즘' 카테고리의 다른 글

LeetCode - P.6  (0) 2025.03.25

문제

 

 

Solution.6 Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);


Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
Example 3:

Input: s = "A", numRows = 1
Output: "A"
Constraints:
1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000

 

s.length ≤ 1000, numRows ≤ 1000 이므로 전체 문자 수는 최대 1,000,000 이하다.

위 표는 1초 동안 수행할 수 있는 최대 연산 횟수를 기준으로, 시간 복잡도를 분석한 결과를 나타낸다. 즉, 입력 크기가 1,000,000 이하일 때, 최적의 해결법을 찾기 위해 O(N log N) 이상의 시간 복잡도를 고려해야 한다는 의미다.

 

풀이

  • 시간 복잡도: O(N)
  • 공간 복잡도: O(N)

여기서 핵심은 주어진 입력이 문자열이라는 점입니다. 이를 해결하기 위해 리스트를 순회하며 문자들을 순차적으로 배치하면 된다.

즉, 문자열을 한 글자씩 꺼내어 numRows 개의 그룹(방)을 만든 후, 순서대로 문자를 채워 넣습니다. 마지막으로, 각 그룹을 차례로 합치면 원하는 결과를 얻을 수 있다.

 

 
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        board = ["" for i in range(numRows)]
        if numRows == 1 or numRows >= len(s):
            return s
        pos = -1
        index = 1
        for i in range(len(s)):
            ch = s[i]
            pos += index
            if pos == numRows-1:
                index = -1
            elif pos == 0 :
                index = 1
            board[pos] += ch
        return "".join(board)

- numrows가 1이거나 s보다 numRows가 큰 경우 s 값을 리턴한다.

- 다른 값일 경우 지그재그 알고리즘을 사용한다.

 

'IT > 알고리즘' 카테고리의 다른 글

LeetCode - 82  (0) 2025.03.27

+ Recent posts

티스토리툴바