본문 바로가기

분류 전체보기252

ch9-2(leetcode 316). 중복 문자 제거 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 316번 ( https://leetcode.com/problems/remove-duplicate-letters/description/ ) 풀이방법 1. 재귀함수를 이용할 수 있다. 중복 문자를 제거해서 알파벳 순서(lexicographical order)가 가장 빠르려면, 알파벳에서 앞에 오는 문자는 앞에, 뒤에 오는 문자는 뒤에 있어야 한다(당연). set() 함수를 사용하면 문자열이나 리스트의 원소들 중 중복을 제거해서 지정된 순서 없이 리턴한다. 이후 sorted() 함수를 리스트에 사용하면 리스트의 원소들을 알파벳 순서에 맞게 정렬할 수 있다. for char in set(sorted(s)): 해당 풀이에서는 조건에 맞는.. 2023. 1. 10.
ch9-1(leetcode 20). 유효한 괄호 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 20번 ( https://leetcode.com/problems/valid-parentheses/description/ ) 풀이방법 1. 스택을 이용해서 풀이한다. 파이썬에는 별도의 스택이나 큐 자료구조가 없다. 리스트 자료형으로도 스택의 push()와 pop(), 큐의 enqueue(), dequeue() 메소드를 사용할 수 있다. 다만 리스트는 포인터가 1개라서 리스트의 맨 앞에서 원소를 제거하는 데는 O(n)이 걸리므로, 성능을 생각한다면 collections 라이브러리의 deque 자료형을 쓰는 것이 더 빠르다. 괄호는 여는 문자 (, [, { 와 닫는 문자 ), ], } 로 이루어져 있다. 여는 문자가 나오면 스택에 넣.. 2023. 1. 10.
ch6-6(leetcode 5). 가장 긴 팰린드롬 부분 문자열 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 5번 ( https://leetcode.com/problems/longest-palindromic-substring/ ) 풀이방법 1. 투 포인터를 사용하면 된다. 보통 투 포인터는 입력의 양 끝에서 중앙으로 모이는 형태를 생각하지만, 반대로 특정 기준점에서 양쪽으로 퍼져 나가는 형태도 가능하다. left, right 포인터를 어느 지점을 기준으로 양쪽으로 퍼져 나갈지를 정하는 시작점이라고 보자. left 포인터는 문자열의 0번째 인덱스부터 len(string)-2번째 인덱스까지를 시작점으로 둘 수 있다. 반면 right 포인터는 문자열의 1번째 인덱스부터 len(string)-1번째 인덱스까지를 시작점으로 둘 수 있다. lef.. 2023. 1. 10.
ch6-5(leetcode 49). 그룹 애너그램 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 49번 ( https://leetcode.com/problems/group-anagrams/ ) 풀이방법 1. 주어진 입력을 그대로 사용하지 않고 변형한 뒤 사용하면 쉽게 풀 수 있는 문제였다. 특히 리스트가 주어졌지만 리스트의 인덱스를 리턴하는 문제가 아니라면 입력으로 주어진 리스트의 순서를 바꿔도 된다는 생각을 해 보면 좋겠다. 문자열 A와 B가 서로 애너그램일 경우, 문자열 A의 모든 문자를 단 한 번씩 사용해서 문자열 B를 나타낼 수 있으며, 그 반대도 성립한다. 서로 애너그램인 문자열들은 여러 개가 있을 수 있으며, 그 문자열들을 하나의 리스트로 묶기 위해서는 그 문자열들을 다른 문자열들과 구분할 수 있어야 한다. 특정.. 2023. 1. 9.
ch6-4(leetcode 819). 가장 흔한 단어 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 819번 ( https://leetcode.com/problems/most-common-word/ ) 풀이방법 1. 리스트 컴프리헨션(list comprehension)과 Counter 자료구조를 사용한다. list comprehension list comprehension이란 기존에 있는 리스트의 값을 사용해서 새로운 리스트를 만드는 것이다. 우선 주어진 문자열을 대소문자로 변환하고 특수문자를 제거한 뒤, 문자열 리스트로 만드는 작업이 필요하다. 그 이후에는 각 문자열이 banned_list에 있는 문자열이 아닌지를 확인해서 리스트에 추가 및 정렬하는 작업이 필요하다. list comprehension을 통해서 간단한 코드로 .. 2023. 1. 9.
ch6-3(leetcode 937). 로그 파일 재정렬 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 937번 ( https://leetcode.com/problems/reorder-data-in-log-files/ ) 풀이방법 1. 파이썬에서 기본으로 제공하는 정렬함수 sort를 이용하고, key 파라미터를 이용해서 정렬 기준을 함수나 람다표현식(lambda expression)으로 제공한다. sort() 함수는 리스트 자료형에만 사용할 수 있다. 만약 문자열을 sort() 함수로 정렬하고 싶다면 문자열을 리스트로 바꾼 뒤, 해당 리스트를 정렬하고, 다시 join() 등의 함수를 사용해서 리스트를 문자열로 바꾸는 작업이 필요하다. 또한 sort() 함수는 리스트 내부를 정렬한 뒤 값을 리턴하지 않는다. 반면 sorted() 함.. 2023. 1. 9.

티스토리툴바