[집중 문제] it 취업을 위한 알고리즘 문제 풀이 입문 (With C/C++) 22. 온도의 최대값

[기억할 내용들]

1. 원래 내가 풀던 방식처럼 이중 for 문을 사용하면 시간 초과 에러가 난다.
2. 이 문제를 단일 for 문을 이용하여 해결할 수 있다.
3. 이 문제처럼 입력의 범위가 너무 클 때는 동적할당을 이용하는 것이 좋다(메모리 낭비 방지).

---

 

[나의 코드]

• 처음 코드
• 이중 for 문을 사용하여 문제를 해결했더니 시간 초과 에러가 났다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;
	vector<int> table;

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		table.push_back(temp);
	}

	int max = -2147000000;
	for (int i = 0; i < table.size() - k + 1; i++) {
		int sum = table[i];

		for (int j = i + 1; j < i + k; j++) {
			sum += table[j];
		}

		if (max < sum)
			max = sum;
	}

	cout << max << "\n";

	return 0;
}

 

• 강의 초반 보고 다시 푼 코드
• 단일 for 문으로 풀었다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

//for 문 한번 돌면서 해결할 수있는 방법
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> table(n);

	for (int i = 0; i < n; i++) {
		cin >> table[i];
	}

	int start = 0;
	int max = 0;
	for (int i = 0; i < k; i++)
		start += table[i];
	max = start;

	for (int i = k; i < n; i++) {
		int sum = start + table[i] - table[i - k];
		if (sum > max) max = sum;

		start = sum;
	}

	cout << max << "\n";

	return 0;
}

 

 

[강의 코드]

#include <iostream>
#include <stdio.h>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

// 이 문제는 동적할당이 필요함. 안그러면 입력의 크기가 작을 때 메모리의 낭비가 심하거덩..
int main() {
	int n, k, i, sum = 0, max;
	scanf_s("%d %d", &n, &k);
	
	vector<int> a(n);
	for (i = 0; i < n; i++)
		scanf_s("%d", &a[i]);

	for (i = 0; i < k; i++)
		sum += a[i];
	max = sum;

	for (i = k; i < n; i++) {
		sum = sum + (a[i] - a[i - k]);
		if (sum > max) max = sum;
	}

	printf("%d\n", max);

	return 0;
}

 

 

[의견]

맨 처음 k 만큼의 수를 먼저 더해놓은 다음에 단일 for 문을 돌면서 값을 하나 더하고 하나 빼고 하는 과정으로 문제를 해결할 수 있다는 사실을 처음 알게 되었다. 이 문제는 진짜 기억해두면 두고두고 잘 사용할 것 같다. 좋은 풀이 방법을 얻은 것 같다. 열심히 해보자!!!!! 

 

 

 

---

 

[참고자료]

투 포인터, 슬라이딩 윈도우 기법 (tistory.com)

투 포인터, 슬라이딩 윈도우 기법