[LeetCode # 47 ~ 49] 문제 풀이

# 47. Permutations II

# 46. 과 유사하지만, 주어진 배열에 중복값이 있을 수 있어 Unique 한 순열을 찾기 위한 조건이 하나 추가된 문제

 

배열에 중복값이 존재하기 때문에, 배열을 우선 정렬을 하고 문제 풀이를 시작했고,

앞서 DFS 방식으로 문제를 해결한 부분에 추가적으로 적용한 조건이 이미 해당 위치에서 사용한 값은 넘기도록 하는 조건을 추가했다.

 

void recursivePermutation(vector<vector<int>>& ans, vector<int>& nums, vector<int>& cur, bool used[]){
    if (nums.size() == cur.size()){
        ans.push_back(cur);
        return;
    }
    int prev = -30;

    for (int i = 0; i<nums.size(); i++){
        if (used[i])
            continue;
        if (prev != -30 && prev == nums[i])
            continue;
        prev = nums[i];
        used[i] = true;
        cur.push_back(nums[i]);
        recursivePermutation(ans, nums, cur, used);
        cur.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    vector<int> vec;
    bool used[10];
    recursivePermutation(ans, nums, vec, used);

    return ans;
}

# 48. Rotate Image

주어진 Matrix 를 우측으로 90도 회전하는 문제

 

이 문제는, 처음 마주했을 때 그 위치를 어떻게 계산해서 바꿔줄까를 고민하고 있었는데 그러던 중 Solution 을 보고 그 방법이 너무 간단해서 그 방법대로 문제를 해결하게 되었다.

어떤 행렬을 우측으로 90도 회전하는 것은, 그 행렬의 전치행렬을 구하고 col 을 reverse 하게 되면 우측으로 90도 회전한 것과 같아진다는 것이 그 방법이었다.

 

void rotate(vector<vector<int>>& matrix) {
    int n = matrix[0].size();

    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    for (int j = 0; j < (n + 1) / 2; j++){
        for (int i = 0; i<n; i++){
            swap(matrix[i][j], matrix[i][n - j - 1]);
        }
    }
}

# 49. Group Anagrams

문자열 배열이 주어졌을 때, 문자열들을 Anagram* 끼리 그룹을 묶어 주는 문제

* Anagram 이란, 문자열에 속한 문자들이 같은 경우를 Anagram 이라 한다.

 

이 문제는, 해시테이블을 활용하면 쉽게 해결할 수 있을 거라 생각했다.

우선, 각 문자열들이 동일한 문자를 갖는 지를 확인하기 위한 방법으로 각각의 문자열들을 정렬하고, 정렬된 문자열을 Key 로 리스트에 저장하는 방식으로 문제를 해결했다.

최종적으로는 해시테이블을 벡터로 변환해서 Return 해서 문제를 간단하게 해결했다.

 

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    map<string, vector<string>> table;

    for (string str : strs){
        string sorted = str;
        sort(sorted.begin(), sorted.end());

        map<string, vector<string>>::iterator it = table.find(sorted);
        if (it != table.end()){
            // Sorted String 을 Key 로 갖는 List 가 있을 때
            it->second.push_back(str);
        }
        else {
            vector<string> v = {str};
            table.insert(make_pair(sorted, v));
        }
    }
    vector<vector<string>> ans;
    for(map<string, vector<string>>::iterator it = table.begin(); it != table.end(); it++){
        ans.push_back(it->second);
    }
    return ans;
}