본문 바로가기

Algorithm/LeetCode

 (9)
Algorithm/LeetCode LeetCode #017 - Letter Combinations of a Phone Number(전화번호 문자 조합) 풀이(2가지 방식) 문제 문제의 내용을 간단히 요약하자면, 입력받은 번호에 해당하는 알파벳을 순서대로 조합한 문자열을 반환하는 것이다. 예를 들어, 아래와 같이 '234'를 입력받았을 때, 조합한 문자열의 길이는 입력받은 문자열의 길이와 동일하게 3이어야 하며, 각각 ['abc'] + ['def'] + ['ghi'] 순서대로 조합된 모든 문자열을 찾아야 한다. input : ['234'] output: ['adg', 'adh', 'adi', 'aeg', 'aeh', 'aei', 'afg', 'afh', 'afi', 'b..
Algorithm/LeetCode LeetCode #561 - Array Partition I(배열 파티션 1) 풀이 문제 문제에서는 길이가 2n인 정수 리스트를 입력받고, 정수를 n쌍으로 묶은 후 각각의 쌍의 최소값을 합한 결과가 최대가 되도록 하여 반환할 것을 요구하고 있다. 내용을 이해하는데 약 30분 정도 소요되었으며, 생각보다 간단하게 해결할 수 있었다. 길이가 6인 정수 리스트를 입력 받는 경우 n은 3이 되고, 리스트를 3조각으로 나누고, 나누어진 조각의 최소값들을 모두 더했을때 가장 큰 값이 되어야 하는 것이다. 풀이 입력받는 리스트를 오름차순으로 정렬하고, 합계를 0으로 초기화한다. nums.sort() sum = 0 입력받은 리스트를 반복하면서 짝수(0, 2, ..., 2n) 번째 인덱스에 해당하는 값을 1의 합계에 더하고, 반복이 종료되면 합계를 반환한다. for i in range(0, len(nu..
Algorithm/LeetCode LeetCode #015 - 3Sum(세 수의 합) 풀이 문제 문제에서는 정수 값을 리스트로 입력받아 세 개의 요소로 구성된 2차원 리스트(ex) [[i, j, k], [x, y, z]]로 반환할 것을 요구하고 있다(이때, 하나의 리스트([i, j, k])의 값은 서로 중첩되면 안 되며, 요소의 합이 0이 되어야 한다). 약 2시간 동안 다음과 같은 두 번의 시도를 하였는데 모두 실패하였고, 결국에는 교재의 풀이 과정을 들여다볼 수 밖에 없었다. 세 개의 요소를 가진 리스트를 만들기 위해 반복문으로 접근하였으나 시간 초과로 인해 실패하였다. 교재에서 언급한 투 포인터 방식과 유사하게 구현은 하였으나, 중복 제거 처리 및 이미 확인한 값을 건너뛰는 코드를 구현하지 않아 실패하였다. 실패 내용 중 첫 번째 방식과 같이 매우 단순 무식한 알고리즘을 브루트 포스라고 ..
Algorithm/LeetCode LeetCode #409 - Longest Palindrome(가장 긴 팰린드롬) 풀이 문제 문제에서 등장하는 팰린드롬은 문자열의 가운데를 기준으로 하여 2개로 나누었을 때, 첫 번째 문자열과 두 번째 문자열의 역순이 같은 문자열을 말하며 다음과 같이 규칙성을 정리해보았다. 문자열을 구성하는 문자의 개수가 모두 짝수인 경우 모든 문자를 팰린드롬으로 배치 가능 ex) 'aabbcc' -> 'aabbcc' 문자열을 구성하는 문자의 개수 중 홀수가 포함되어 있는 경우 개수가 홀수인 문자를 짝수로 활용하고, 가운데에 홀수인 문자로 하여 팰린드롬으로 배치 가능 ex) 'aaabbbccc' -> 'abcccba' 따라서. 문자열을 구성하는 문자의 개수가 홀수인 경우 이를 짝수로 만들고, 문자열의 가운데에 끼워줄 홀수 개의 문자 1개를 나중에 더..
Algorithm/LeetCode LeetCode #622 - Design Circular Queue(원형 큐 디자인) 풀이 문제 문제에서 나오는 원형 큐는 FIFO 정책에 따라 연산을 수행하고 마지막 위치를 첫 번째 위치에 연결하여 원을 만드는 선형 데이터 구조로, 링 버퍼라고도 한다. 원형 큐의 장점 중 하나는 공간을 활용할 수 있다는 것이다. 일반적인 큐에서는 데이터가 가득차면 큐에 공간이 있어도 다음 요소를 삽입할 수가 없다. 그러나, 원형 큐를 사용하면 공간을 사용하여 새로운 값을 저장할 수 있다. 문제에서 구현해야 할 MyCircularQueue 클래스의 메소드는 다음과 같다. __init__(k: int) -> None : 큐 개체의 크기를 k로 초기화 Front() -> int : 큐의 맨 앞의 데이터를 가져오되, 비어있는 상태인 경우 -1을 반환한다. Rear() -> int : 큐의 맨 뒤의 데이터를 가져오되..
Algorithm/LeetCode LeetCode #232 - Implement Queue using Stacks(스택을 이용한 큐 구현) 풀이 문제 2개의 스택만을 사용하여 FIFO 큐를 구현하여야 하는 문제이다. 구현된 큐는 일반 큐의 모든 기능(push, pop, empty)를 지원하여야 하며 구현해야 하는 MyQueue 클래스는 다음과 같다. push(x: int) -> void : x를 큐의 맨 뒤에 넣는다. pop() -> int : 큐의 가장 앞에 있는 요소를 삭제하고 반환한다. peek() -> int : 큐의 맨 앞에 있는 요소를 반환한다. empty() -> boolean : 큐가 비어있으면 true, 그렇지 않으면 false를 반환한다. 이때, 아래 사항을 참고하여야 한다. 스택의 기본 연산(push to top, peek or pop from top, size 및 is empty)만 사용하여야 한다. 언어에 따라서는 스택이 ..
Algorithm/LeetCode LeetCode #049 - Group Anagrams(그룹 애너그램) 문제 풀이 문제 문제의 애너그램은 특정 문자열의 문자를 재배치하여 만든 새로운 문자열이며, 문제에서는 여러 개의 문자열이 배열로 주어질 때 애너그램으로 짝짓고 반환할 것을 요구하였다. 문제를 보자마자 엑셀에서의 '중복 제거'가 떠올랐다. 즉, 특정 대상의 통계를 구하기 위해서는 해당 대상을 중복 제거하여야 한다. 이를 가능케 하는 방법으로 다음과 같이 크게 2가지를 떠올려보았다. 문자열을 구성하는 문자의 ascii 코드의 총 합을 기준으로 중복 제거가 가능하다. 문자열을 구성하는 문자를 정렬하면 중복을 제거할 수 있다. 이 중에서 두 번째 방법이 훨씬 직관적인 코드로 나타낼 수 있다고 생각하여 두 번째 방법으로 시도해보았다. 풀이 딕셔너리를 사용한 해시테이블 생성 딕셔너리의 key는 문자열의 문자를 ..
Algorithm/LeetCode LeetCode #206 - Reverse Linked List(역순 연결 리스트) 풀이 문제 문제의 내용을 요약하면, 연결 리스트를 역순으로 재구성한 후 반환하여야 한다. 풀이 이 문제는 21. Merge Two Sorted Lists와 같이 새로운 노드를 생성하는 방식으로 해결하는데, 문제에서 주어진 예시로 과정을 나타내보면 다음과 같다. 더미 노드 생성 현재 노드(current)를 연결 리스트의 head로 정하고, 새로운 노드(node를 None으로 초기화한다. current, node = head, None 반복하며 스와핑 현재 노드 즉, 기존 연결 리스트의 head가 되는 모든 노드를 탐색하며 새로운 노드로 값을 넘겨준다. 이 과정을 다음과 같이 나타낼 수 있다. 첫 번째 반복 current: ListNode: [1 -> 2 -> 3 -> 4 -> 5] 1) next = ListNo..
Algorithm/LeetCode LeetCode #021 - Merge Two Sorted Lists(두 개의 연결 리스트 병합) 풀이 문제 문제내용을 살펴보면, 정렬된 두 개의 연결 리스트의 노드를 결합하여 다음 그림과 같이 하나의 정렬된 연결 리스트로 병합하여야 한다. 본 내용은 leetcode에서 제공한 아래 그림을 토대로 작성하였기 때문에 그림 1(node2로 이동), 그림 5(node1로 이동)와 같이 값이 동일한 경우 포인터를 어디로 변경할 것인지 헷갈릴 수 있다. 결론만 말하자면, 두 개의 노드 값이 동일한 경우 node1, node2 중 아무거나 선택해도 무방하다. 풀이 문제에서 주어진 예시(list1 = [1, 2, 4], list2 = [1, 3, 4])를 그림으로 나타내면 다음과 같다. 이 둘은 노드의 값을 기준으로 오름차순으로 정렬되어 있으며, 가장 왼쪽에 있는 노드가 각 연결 리스트의 head라고 할 수 있다. 그..

티스토리툴바