알고리즘 스터디 1주차

LeetCode Top Interview Questions [Medium Collection]

Array and Strings

3 Sum

접근 방식

3중 포문 순회 방법 (O(n^3))
- 무한히 많은 0, 수가 많을 경우 시간 초과
2중 포문으로 변경 후에 x,y값이 정해지면 z는 find로 알고리즘 사용
- std::find알고리즘이 알고보니 전체 순회였음 (O(n^3))
find알고리즘 변경

Find를 할 경우 O(n)이므로 바이너리 서치를 통해 O(nlogn)으로 감소
std::map 사용으로 변경 (O(n^2*logn))
- 2중 루프 O(N^2) + map의 find O(log n)
- find알고리즘만 찾는 것 보다 전부를 hashmap같은 key, value에서 사용하는게 편할 것 같음 ⇒ C++ stl의 map은 ordered_map 이므로 0을 넘어가는 순간 break걸어도 될듯
Two Pointer사용

정렬을 한 뒤에 O(log n) 정렬된 순으로 이동하여 중복을 검출할 수 있다.

투포인터 순회 O(n^2)

3중 for (시간 초과)

O(n^3)

	vector<vector<int>> threeSum2(vector<int>& nums) {
        set<vector<int>> answer;
        //일단 정렬
		// O(nlogn)
        sort(nums.begin(), nums.end());

		// O(n^2 * find알고리즘)
		for (int i = 0; i < nums.size(); ++i)
		{
		    // 중복쌍은 피한다.
		    if (i > 0 && nums[i-1] == nums[i])
		    {
		        continue;
		    }

		    // 순차 정렬이 되어 있어서 첫 pair가 0보다 크면 더이상 검사하지 않아도 된다.
		    if (nums[i] > 0)
		    {
		        break;
		    }

		    if (i + 2 < nums.size() && nums[i] == 0 && nums[i+1] == 0&& nums[i+2] == 0)
		    {
		        answer.insert({0,0,0});
		        break;
		    }

		    int TempNum2 = 2147483647; // int_max

			for (int j = i + 1; j < nums.size(); ++j)
			{
			    // 동일값 검사 할 필요 없음.
			    if (i + 1 < j - 1 && nums[j] == nums[j-1])
			    {
			        continue;
			    }

			    TempNum2 = nums[j];

			    // 순차정렬 하여 0보다 크면 답이 없음.
			    if (nums[i] + nums[j] > 0)
			    {
			        break;
			    }


			    int TargetNum = -(nums[i] + nums[j]);
			    auto k = find(nums.begin() + j + 1, nums.end(), TargetNum);

			    if (k != nums.end())
			    {
					answer.insert({nums[i], nums[j], *k});
			    }
			}
		}

		return vector<vector<int>>(answer.begin(), answer.end());;
    }

map사용

O(n^2 logn)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    set<vector<int>> answer;
		map<int, int> numset;

		// O(n)
		for (auto num : nums)
		{
			numset[num]++;
		}

		for (auto i = numset.begin(); i != numset.end(); ++i)
		{
			numset[i->first]--;
			auto j = i;

			// 해당 값이 하나 밖에 없을 경우 다음 원소를 찾고, 아닐 경우 j에서 시작
			if (numset[i->first] <= 0)
			{
				j++;
			}

			for (;  j != numset.end(); ++j)
			{
				numset[j->first]--;

				int targetvalue = -(i->first + j->first);

				auto k = numset.find(targetvalue);
				if (k != numset.end() && k->second > 0)
				{
					vector<int> temp = {j->first, i->first, targetvalue};
					sort(temp.begin(), temp.end());
					answer.insert(temp);
				}
				numset[j->first]++;
			}
			numset[i->first]++;
		}

		return vector<vector<int>>(answer.begin(), answer.end());;
    }
};

Two Pointer 사용

O(n^2)

#include <vector>
#include <set>
#include <map>
#include <Algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> answer;

        sort(nums.begin(), nums.end());

        auto first = nums.begin();
        while (first != nums.end())
        {
            // 중복 제거
            if (first != nums.begin() && *first == *(first -1))
            {
                first++;
                continue;
            }

            auto second = first + 1;
            auto three = nums.end() - 1;
            while (second < three)
            {
                int sum = *first + *second + *three;
                if (sum > 0)
                {
                    three--;
                }
                else if (sum < 0)
                {
                    second++;
                }
                else if (sum == 0)
                {
                    answer.push_back({*first, *second, *three});
                    second++;
                    three--;

                    // 중복 제거
                    while (second < three && *three == *(three + 1)) three--;
                    while (second < three && *second == *(second - 1)) second++;
                }
            }
            first++;
        }

        return answer;
    }

};

정렬을 통해 같은 값이 다음에 오게될 경우 중복을 건너뛰는 방법 채용.
💡 투포인터 핵심 1. 배열을 **오름차순 정렬** 2. **두 포인터**를 배열의 양 끝에 둠 - 왼쪽 포인터 `l = 0`, 오른쪽 포인터 `r = n-1` 3. 합을 계산 후 조건에 따라 포인터 이동: - 합이 **목표값보다 작으면** → `l++` (왼쪽 값 키우기) - 합이 **목표값보다 크면** → `r--` (오른쪽 값 줄이기) - 합이 **목표값과 같으면** → 정답 저장 후, 양쪽 포인터 이동 ❗포인터를 이동할 때, 이전 값과 같으면 중복으로 판단하여 한번 더 이동한다.

Set Matrix Zeroes

Explore - LeetCode

Set사용

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

		set<int> rowIndex;
		set<int> colIndex;

		for (int i = 0; i < matrix.size(); i++)
		{
			for (int j = 0; j < matrix[0].size(); j++)
			{
				if (matrix[i][j] == 0)
				{
					rowIndex.insert(i);
					colIndex.insert(j);
				}
			}
		}
		for (auto i : rowIndex)
		{
			matrix[i].assign(matrix[i].size(), 0);
		}

		for (auto j : colIndex)
		{
			for (int i = 0; i < matrix.size(); i++)
			{
				matrix[i][j] = 0;
			}
		}
	}
};

접근 방식

배열을 순환
0을 찾아서 x,y좌표를 기록
기록된 x,y좌표에 따라 배열을 0으로 초기화

알고리즘

전채 배열을 순환하여 0을 기록
x,y좌표에서 찾아 0으로 초기화

힌트 확인 후 공간 적게 먹는 솔루션

class Solution {
public:
	void setZeroes(vector<vector<int>>& matrix) {

		// 맨뒤에 x좌표를 체크하기 위한 행을 추가
		matrix.push_back(vector<int>(matrix[0].size(), 0));

		for (int i = 0; i < matrix.size(); i++)
		{
			matrix[i].push_back(0); // 맨뒤에 y좌표를 체크하기 위한 열을 추가
		}

		// 추가된 열을 제외하고 순회 하여 x,y에 0이 있는지 체크
		for (int i = 0; i < matrix.size() - 1; i++)
		{
			for (int j = 0; j < matrix[i].size() - 1; j++)
			{
				if (matrix[i][j] == 0)
				{
					matrix[i][matrix[i].size() - 1] = 1; // 마지막 행에 x좌표를 체크
					matrix[matrix.size() - 1][j] = 1; // 마지막 열에 y좌표를 체크
				}
			}
		}

		// 행 체크
		for (int i = 0; i < matrix.size() - 1; i++)
		{
			if (matrix[i][matrix[i].size() - 1] == 1)
			{
				matrix[i].assign(matrix[i].size() - 1, 0); // 해당 열을 0으로 변경
			}
			else
			{
				matrix[i].pop_back();
			}
		}

		// 열 체크
		for (int j = 0 ; j < matrix[0].size(); j++)
		{
			if (matrix[matrix.size() - 1][j] == 1)
			{
				for (int i = 0 ; i < matrix.size() ; i++)
				{
					matrix[i][j] = 0;
				}
			}
		}

		matrix.pop_back();
	}
};

코드	시간 복잡도	공간 복잡도	특징
첫 번째 (set 사용)	`O(m * n * log(max(m, n)))`	`O(m + n)`	직관적, 구현 간단
두 번째 (matrix 재활용)	`O(m * n)`	`O(m + n)`	공간 효율 최고, 구현 복잡

첫 번째 (set 사용)

unordered_set사용시 시간 줄이기 가능

Group Anagrams

Explore - LeetCode

접근 방식

에너그램을 그룹화 해서 관리할 수 없을까? ⇒ map사용
에너그램을 vector으로 변환해서 리턴

O(n * k * (log k + log n))

class Solution
{
public:
	vector<vector<string>> groupAnagrams(vector<string> &strs)
	{
		map<string, vector<string>> anagramsMap;
		vector<vector<string>> answer;
		for (string value : strs)
		{
			string sortedValue = value;
			sort(sortedValue.begin(), sortedValue.end());

			anagramsMap[sortedValue].push_back(value);
		}

		for (auto a : anagramsMap)
		{
			answer.push_back(a.second);
		}

		return answer;
	}
};

PREVIOUS컨텐츠 브라우저 편집

NEXT알고리즘 스터디 2주차