DEVGRAPHY

문제 포인트

map 자료구조 

최대 결과값 크기 고려한 타입(long long)

=> 2^30까지 고려해야 함

=> 2^31 = 2,147,483,648

경우의 수

해설 코드와 내 코드 비교

최대 결과값 크기 고려한 타입(long long)

테스트 케이스 for 보다 while로 간단 표현

테스트 케이스별 자료구조 초기화를 위해 해설 코드는 변수 재정의를 하고, 내 코드는 map.clear() 함수를 이용해 모든 원소를 지운다.

해설 코드

#include <bits/stdc++.h>
using namespace std;
int t, n;
string a, b;
int main(){
    cin >> t;
    while(t--){
        map<string, int> _map;
        cin >> n;
         for(int i = 0; i < n; i++){
            cin >> a >> b;
            _map[b]++;
        }
        long long ret = 1;
        for(auto c : _map){
            ret *= ((long long)c.second + 1);
        }
        ret--;
        cout << ret << "\n";
    }
    return 0;
}

내 코드

#include <iostream>
#include <map>
using namespace std;

map<string, int> m;
int main(){
	int t, n;
	int ret = 1;
	string a, b;
	cin >> t;
	for(int i = 0; i < t; i++){
		ret = 1;
		m.clear();
		cin >> n;
		for(int j = 0; j < n; j++){
			cin >> a >> b;
			m[b]++;
		}
		for(auto row : m){
		ret *= (row.second+1);
		}
		cout << ret - 1 << endl;
	}
	
}

문제 포인트

누적합

해설 코드와 내 코드 비교

해설 코드는 최솟값을 고려하여 최댓값 비교

=> 최댓값을 구하라 -> 최솟값부터 최댓값 , 최솟값을 구하라 -> 최댓값부터 최솟값

해설 코드는 누적합(prefix sum)을 저장한 배열을 이용하여 구간합을 구함

=> K가 바뀔 때마다 입력값 배열을 다시 순회하여 구할 필요가 없음

내 코드는 슬라이딩 알고리즘을 이용하여 구간합을 구함

해설 코드

#include<bits/stdc++.h> 
using namespace std;  
typedef long long ll;  
int n, k, temp, psum[100001], ret = -1000000; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin >> n >> k; 
	for(int i = 1; i <= n; i++){
		cin >> temp; psum[i] = psum[i - 1] + temp; 
	} 
	for(int i = k; i <= n; i++){
		ret = max(ret, psum[i] - psum[i - k]);
	}
	cout << ret << "\n";
    return 0;
}

내 코드 1차

개선 필요

// 연속 K개 합 중 가장 큰 값
// 슬라이딩 

#include <iostream>
using namespace std;
int temper[100005];
int ret, mx;
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> temper[i];
        if(i < k)
            ret +=temper[i];
        
    }
    mx = ret;
    for(int i = k; i < n; i++){
        if(mx < ret + temper[i]-temper[i-k])
            mx = ret + temper[i]-temper[i-k];
        ret+=temper[i]-temper[i-k];
    }
    cout << mx << endl;
}

내 코드 2차

잘한점

- typedef 로 타입명 간소화

- max 라이브러리 사용하여 코드 간소화 (별도 라이브러리 import 필요 없음)

개선점

- 변수 네이밍: 구간합(Prefix sum) 배열 이름 ->psum

#include <iostream>
typedef long long ll;
using namespace std;

ll t[100005];
ll mx = -10000005;
int main(){
    int n, k, temp;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> temp;
        t[i] = t[i-1] + temp;
    }
    for(int i = k; i <= n; i++){
        mx = max(mx, t[i] - t[i-k]);
    }
    cout << mx << endl;
}