알고리즘 스터디 6주차

LeetCode Top Interview Questions [Medium Collection]

Backtracking

Letter Combinations of a Phone Number

휴대폰에서 숫자 패드 조합을 넣을 경우 조합이 가능한 문자열 출력

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

숫자에 맞게 map생성
vector를 생성하여, 숫자 조합에 맞게 시작이 가능하게 초기화
이후에 길이만큼 for문을 돌면서 2에서 생성한 vector을 갱신 해준다.

class Solution {
    unordered_map<char, vector<string>> map;
public:
    Solution()
    {
        map['0'] = { "" };
        map['1'] = { "" };
        map['2'] = { "a", "b", "c" };
        map['3'] = { "d", "e", "f" };
        map['4'] = { "g", "h", "i" };
        map['5'] = { "j", "k", "l" };
        map['6'] = { "m", "n", "o" };
        map['7'] = { "p", "q", "r", "s" };
        map['8'] = { "t", "u", "v" };
        map['9'] = { "w", "x", "y", "z" };
    }

    vector<string> insertmap(string target, char digits)
    {
        vector<string> returnValue;
        for (string a : map[digits])
        {
            returnValue.push_back(target + a);
        }
        return returnValue;
    }

    vector<string> letterCombinations(string digits)
    {
        vector<string> ans = insertmap("", digits[0]);
        for (int i = 1; i < digits.length(); i++)
        {
            vector<string> tempans;
            for (auto a : ans)
            {
                vector<string> temp = insertmap(a, digits[i]);
                tempans.insert(tempans.end(), temp.begin(), temp.end());
            }
            ans = tempans;
        }
        return ans;
    }
};

이렇게 해보니 vector을 생성하는 시간을 단축 하고 싶어져 함수 호출 없이 수행하게 코드 변경

class Solution {
    unordered_map<char, vector<string>> map;
public:
    Solution()
    {
        map['0'] = { "" };
        map['1'] = { "" };
        map['2'] = { "a", "b", "c" };
        map['3'] = { "d", "e", "f" };
        map['4'] = { "g", "h", "i" };
        map['5'] = { "j", "k", "l" };
        map['6'] = { "m", "n", "o" };
        map['7'] = { "p", "q", "r", "s" };
        map['8'] = { "t", "u", "v" };
        map['9'] = { "w", "x", "y", "z" };
    }

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

        vector<string> ans = map[digits[0]];

        for (int i = 1; i < digits.length(); i++)
        {
            vector<string> tempans;
            for (auto& prefix : ans)
            {
                for (auto& letter : map[digits[i]])
                {
                    tempans.push_back(prefix + letter);
                }
            }
            ans = move(tempans);
        }
        return ans;
    }
};

Generate Parentheses

Explore - LeetCode

n개의 ()쌍으로 조합 가능한 string을 출력.

dp[0]을 빈 문자열로 초기화
dp[i]를 채워 넣는 코드 작성
1. dp[j]와, dp[target]으로 조합을 완성
2. target = i - j - 1; ⇒ i가 n개의 ()으로 만들 수 있는 string조합이므로 (j+1)을 빼서 총 n개의 쌍으로 구현. ⇒ 1을 더 빼주는 이유는 아래 코드에서 ()을 붙여주기 떄문에.
3. dp[j]의 양쪽에 ()을 붙여주고 dp[target]을 뒤에 붙여줌.

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        vector<vector<string>> dp(9, vector<string>());

        dp[0] = { "" };
        for (int i = 1; i <= n; i++)
        {
            // i = 괄호의 총 갯수
            // j = dp의 괄호수
            // n = i - j - 1 // j로 인해 들어가는 괄호수
            for (int j = 0; j < i; j++)
            {
                int target = i - j - 1;
                auto d1 = dp[j];
                auto d2 = dp[target];
                for (auto a : d1)
                {
                    for (auto b : d2)
                    {
                        dp[i].push_back("(" + a + ")" + b);
                    }
                }
            }
        }
        return dp[n];
    }
};

Permutations

Explore - LeetCode

n개의 숫자로 가능한 조합을 전부 출력하는 코드

위의 코드들과 유사하다.

사용한 원소들을 식별하기 위해 bitMask벡터를 생성 (진짜 비트마스킹 사용하면 좋을 것 같긴 하다.)
함수를 통해 아래 동작 수행
1. 사용한 index기록
2. 벡터에 사용한 num을 삽입
3. 생성된 vector이 nums의 크기와 같을 경우에 정답에 삽입.

class Solution {
    void Backtraking(vector<vector<int>>& ans, vector<int>& target, const vector<int>& nums, vector<int>& bitMask)
    {
        if (target.size() == nums.size())
        {
            ans.push_back(target);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (bitMask[i] != 0)
                continue;
            target.push_back(nums[i]);
            bitMask[i] = 1;

            Backtraking(ans, target, nums, bitMask);

            bitMask[i] = 0;
            target.pop_back();
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        // 사용한 원소 체크.
        vector<int> bitMask(6, 0);
        vector<int> value;
        Backtraking(ans, value, nums, bitMask);
        return ans;
    }
};

PREVIOUS알고리즘 스터디 5주차

NEXT알고리즘 스터디 7주차