Lv 0. 순서쌍의 개수 - 처음으로 시간초과 발생한 문제.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i*j==n) answer++;
        }
    }
    return answer;
}

그동안 Lv 0. 문제들을 풀면서 시간제한이나 공간제한이 명시되어있는 부분이 없어서 그냥 이렇게 이중for문으로 짜서 제출하니까, 

이런 결과물을 얻을 수 있었다. 

테스트 1 〉	통과 (0.01ms, 4.01MB)
테스트 2 〉	통과 (0.01ms, 3.59MB)
테스트 3 〉	통과 (3056.71ms, 4.21MB)
테스트 4 〉	통과 (0.01ms, 4.21MB)
테스트 5 〉	실패 (2850.53ms, 4.13MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	통과 (0.01ms, 3.68MB)
테스트 8 〉	통과 (0.01ms, 4.14MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)

 

그래서 시간복잡도를 줄이기 위해서 두번째로 작성한 풀이는, 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for(int i=1; i<=n; i++){
        if(n%i==0) answer++;
    }
    return answer;
}

이와 같다. 

테스트 1 〉	통과 (0.01ms, 4.13MB)
테스트 2 〉	통과 (0.01ms, 4.16MB)
테스트 3 〉	통과 (0.37ms, 4.18MB)
테스트 4 〉	통과 (0.01ms, 4.15MB)
테스트 5 〉	통과 (0.24ms, 4.23MB)
테스트 6 〉	통과 (2.39ms, 4.14MB)
테스트 7 〉	통과 (0.01ms, 4.22MB)
테스트 8 〉	통과 (0.01ms, 4.02MB)
테스트 9 〉	통과 (2.30ms, 4.19MB)
테스트 10 〉	통과 (2.49ms, 3.63MB)

 

그리고 이런 문제의 경우는 두 수의 곱으로 값을 나타낼때, 대칭을 이루는 형태로 수들이 나타나니까, 그걸 이용해서 더욱 줄일 수 있다는 생각이 들었고, 다른 사람의 풀이를 보다보니 내가 생각한 것처럼 대칭성을 이용해서 풀이한 풀이를 찾을 수 있었고, 그 풀이의 경우는, 

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    int answer = 0;
    for(int i = 1; i <= sqrt(n); i++)
    {
        if(n % i == 0) answer += 2;
        if(i * i == n) answer--;
    }
    return answer;
}

이와 같았다. 

만약 내가 이런 형태로 푼다면 여기서 sqrt(n); 을 사용해서 for문의 범위를 나타내었고, 그러기 위해 <cmath> 헤더까지 붙였는데, 

그렇게 하기보다는 

for(int i=1; i*i<=n; i++) 로 작성하는것이 더 좋을것 같다는 생각이 들었다. 그렇게 해보면, 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for(int i = 1; i*i<=n; i++)
    {
        if(n % i == 0) answer += 2;
        if(i * i == n) answer--;
    }
    return answer;
}

이렇게 작성할 수 있을 것이다. 

이 코드를 제출해보면, 

테스트 1 〉	통과 (0.01ms, 4.16MB)
테스트 2 〉	통과 (0.01ms, 4.15MB)
테스트 3 〉	통과 (0.01ms, 4.16MB)
테스트 4 〉	통과 (0.01ms, 4.23MB)
테스트 5 〉	통과 (0.02ms, 3.63MB)
테스트 6 〉	통과 (0.01ms, 4.04MB)
테스트 7 〉	통과 (0.01ms, 4.03MB)
테스트 8 〉	통과 (0.01ms, 4.15MB)
테스트 9 〉	통과 (0.01ms, 4.16MB)
테스트 10 〉	통과 (0.01ms, 4.17MB)

이와 같은 결과를 얻을 수 있고, 가장 처음에 작성한 풀이와 비교를 해본다면, 

 

이렇게 아주 큰 차이를 만들어내는걸 볼 수 있다. 

얼핏보면 간단하게 풀이하고 넘길만한 문제겠지만,

for(int i = 1; i*i<=n; i++)
    {
        if(n % i == 0) answer += 2;
        if(i * i == n) answer--;
    }

와 같은 형태의 코드를 통해서 아주아주 커다란 차이를 만들어낼 수 있는 형태의 문제였다. 이런 생각이 나중에 소수판별할때, 에라토스테네스의 체를 활용할때 등에서 다시 사용될것이고, 그 차이가 아주아주 큰 차이를 만들어내니까 이런 사고를 할 수 있는 습관을 들이도록 하자. 

그리고 위의 풀이를 잘 기억해놓고 다음에는 처음으로 이런식의 풀이로 바로 진입할 수 있도록 만들자.