[프로그래머스][Lv.2] - 연속 부분 수열 합의 개수

 

● 소감

- 오~ 이건 단방에 이해되진 않았지만, 좋은 문제였다

 

● 나의 풀이

1) 문제 이해

 

- 환형 배열이기 때문에 0번 인덱스에서 끝 인덱스에 접근할 땐 문제가 없지만, 3번 인덱스에서 시작한다면 끝 인덱스에서 돌아 첫 인덱스로 돌아가야 한다는걸 고려해야한다.

- 인덱스를 접근하면서 구했던 값을 계속 누적해가야 한다. 그래야 연속적인 수열의 합을 구하기 편해진다.

- 요구하는건 만들어지는 총 합의 개수이고, 구한 합이 중복될 수도 있다. 중복 값을 처리해줄 수 있는 set를 사용하면 편하다.

 

2) 조건 찾기

 

- 환형 배열을 접근하는 것부터 중요한데, 나는 갖을 수 있는 조건이 순서대로 elements에 접근할 i, i번째에서 elements.size() 만큼 증가하는 j, 그리고 elements.size() 3가지가 있다고 생각했다.

- i + j 가 element.size() 만큼 증가했다면, size만큼 빼면 다시 0으로 돌아가기 때문에, size를 기준으로 i + j 만큼 접근하는 인덱스와 i + j - size 만큼 접근하는 인덱스로 나눴다.

 

- 그리고 인덱스에 접근한 값은 우선 temp에 더하고, for문이 돌 때마다 temp에 더하면서 set에 넣으면 누적값을 쉽게 관리 할 수 있다.

 

for(int i = 0; i < elements.size(); i++)
{
	int temp = 0;
		
	for(int j = 0; j < elements.size(); j++)
	{
		if (i + j >= elements.size())
		{
			temp += elements[i + j - elements.size()];
			result.insert(temp);
			continue;
		}

		temp += elements[i + j];
		result.insert(temp);
	}
}

 

3) 엄청난 시간복잡도...?

 

- 위의 코드로 제출했을 때 일단 정답은 나왔다. 그런데 엄청난 시간복잡도나 나오는것이 아닌가.. 내가 접근한 방식이 좋지 않은 방법인가? 라고 생각했는데, 다른 풀이의 댓글에 unordered_set을 사용하면 시간복잡도가 좀 괜찮아진다는 것이다.

- unordered_set을 찾아보니 정렬되지 않는 set이라고 한다. 지금 문제에선 중복값만 관리하면 되지 이를 굳이 정렬까지 할 필요는 없으니 딱 좋은 set이구나 라는 생각이 들었다. (이후 시간복잡도가 1/3로 줄어듬)

- unordered_set은 set과는 별개의 라이브러리에 있다. ( #include <unordered_set>)

unordered_set<int> result;

 

4) 간략화

 

- 위의 방식이랑 동일했는데 나머지를 이용한 인덱스 접근이 신기해서 업어왔다!

// 간결화
int n = elements.size();

for (int i = 0; i < n; i++) {
	int sum = 0;
	for (int j = i; j < i + n; j++) {
		sum += elements[j % n];
		result.insert(sum);
	}
}

 

 

● 내가 작성한 답

int solution(vector<int> elements)
{
	unordered_set<int> result;

	for(int i = 0; i < elements.size(); i++)
	{
		int temp = 0;

		for(int j = 0; j < elements.size(); j++)
		{
			if (i + j >= elements.size())
			{
				temp += elements[i + j - elements.size()];
				result.insert(temp);
				continue;
			}

			temp += elements[i + j];
			result.insert(temp);
		}
	}

	// 간결화
	/*int n = elements.size();

	for (int i = 0; i < n; ++i) {
		int sum = 0;
		for (int j = i; j < i + n; ++j) {
			sum += elements[j % n];
			result.insert(sum);
		}
	}*/

	return result.size();
}