[LeetCode # 17 ~ 19] 문제 풀이

# 17. Letter Combinations of a Phone Number

각 문자가 '2-9' 정수로 이루어진 문자열이 주어졌을 때, 해당 버튼을 abc keyboard 에서 눌렀을 때 만들 수 있는 모든 경우를 구하는 문제

ex ) 2 - abc, 3 - def, ... 9 - wxyz

말 그대로 각 숫자 별로 출력 가능한 문자들이 정해져 있어 이 문자들의 조합을 만들도록 코드를 구현했다.

// 각 숫자 별로 입력 가능한 문자들 저장
string letters[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

vector<string> letterCombinations(string digits) {
    if (digits.empty()){
        return {};
    }
    vector<string> result;
    result.push_back("");

    for (auto digit : digits) {
        vector<string> tmp;
        for (auto s : result) {
            for (auto candidate : letters[digit - '0']) {
                tmp.push_back(s + candidate);
            }
        }
        result.swap(tmp);
    }
    return result;
}

# 18. 4 Sum

3 Sum 과 유사한 문제로, 정수형 배열이 주어졌을 때 a + b + c + d = target 값이 되는 a, b, c, d 의 조합을 찾는 문제

3 Sum 은 하나의 값만 정해놓고 left, right 인덱스 두 개로 탐색했지만 이 문제는 두 값을 정해놓고 left, right 인덱스 두 개로 탐색

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;

    for (int i = 0; i < nums.size(); i++) {
        int t1 = target - nums[i]; // 연산량을 줄이기 위해 앞에서 미리 계산
        for (int j = i + 1; j < nums.size(); j++) {
            int t2 = t1 - nums[j];
            int l = j + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum < t2) {
                    l++;
                }
                else if (sum > t2) {
                    r--;
                }
                else {
                    vector<int> v(4, 0);
                    v[0] = nums[i];
                    v[1] = nums[j];
                    v[2] = nums[l];
                    v[3] = nums[r];
                    ans.push_back(v);

                    while (l < r && nums[l] == v[2]){
                        l++;
                    }
                    while (l < r && nums[r] == v[3]){
                        r--;
                    }
                }
            }
            while (j < nums.size() - 1 && nums[j] == nums[j + 1]){
                j++;
            }
        }
        while (i < nums.size() - 1 && nums[i] == nums[i + 1]){
            i++;
        }
    }
    return ans;
}

# 19. Remove Nth Node From End of List

리스트가 주어졌을 때, n 번째 노드를 리스트에서 삭제하는 문제

Single Linked List 가 주어지기 때문에 단순히 뒤에서부터 n 개를 탐색할 수는 없었다.

대신 앞에서부터 탐색을 하되 총 노드의 개수를 저장하고 각각의 노드를 배열에 저장함으로써 뒤에서 n 번째 노드를 바로 찾고, 그 앞의 노드를 그 다음 노드로 연결하도록 했다.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *arr[31] = {0, }, *tmp, dummy;
    int size;
    dummy = ListNode(0, head);
    arr[0] = &dummy;

    for (tmp = head, size = 1; tmp != nullptr; tmp = tmp->next, size++) {
        arr[size] = tmp;
    }    
    if (size == 2) {
        return nullptr;
    }
    arr[size - n - 1]->next = arr[size - n + 1];
    return arr[0]->next;
}