1. Subject : 시간복잡도…

1. What I learn?

알고리즘을 풀다보면 시간문제를 당연히 고려해야한다. 이번 문제도 그렇다.

완전 탐색 방법의 단점

완전 탐색은 데이터를 모두 검사해 확실한 값을 얻을 수 있지만 완전 탐색이라는 이름에 따라서 시간이 오래걸린다. for문을 두 개 돌리는 순간 O(n^2)의 결과가 나온다는 뜻이다.

2. What I did?

import java.util.*;
import java.io.*;

/*
[IDEA]
W = brown + yellow (넓이)
2차원 배열A에 경우의 수 담기
담는 조건 - [a,b] a>=b;인 경우에만 담는다.[가로,세로]

for(A의 수 만큼 )
A의 (가로 -2)*(세로-2) == yello -> [가로,세로] 리턴
 */
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        int w = brown+ yellow;
        
        List<int[]> A = new ArrayList<>();
        for(int i=1; i<=w; i++){//세로
            for(int j=i; j<=w; j++){//가로
                if(i*j == w){
                    int[] temp = new int[2];
                    temp[0] =j;
                    temp[1] =i;
                    
                    A.add(temp);
                }
            }
        }
        
       for(int[] temp : A){
           int tempy = (temp[0]-2)*(temp[1]-2);
           if(tempy == yellow)return temp;
       }

        return answer;
    }
}

이것도 맞는 풀이이다. 대신 시간초과가 나는 풀이이다.

해당 풀이는 10^12 풀이를 갖게 되는데 이는 1초를 넘는 시간이다.

3. How did I solve?

import java.util.*;
import java.io.*;

/*
[IDEA]
W = brown + yellow (넓이)
2차원 배열A에 경우의 수 담기
담는 조건 - [a,b] a>=b;인 경우에만 담는다.[가로,세로]

for(A의 수 만큼 )
A의 (가로 -2)*(세로-2) == yello -> [가로,세로] 리턴

--- n2으로 10^12나와서 시간초과 나오는 방법

가로-2 * 세로-2 == yellow의 값이다.

가로세로의 경우의 수를 고르는 것이 아니라
가로 세로를 탐색하는 방안은?

w>=3
h>=3

w의 길이의 최대 = brown+yellow(세로1 가로 n인 경우)

w<=n만큼

for(int w=1; w<=n; w++){
    h = n/w;
    if(n%w ==0) //가로 세로는 n의 약수여야 함
    if(h>=3 && w>=h) 가로가 세로보다 길고h>=3이상인경우
    if(h-2 * w-2==yellow)
    w,h리턴하기
}

 */
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int n = brown+yellow;
        for(int w=3; w<=n; w++){
            int h = n/w;
            
            if(n%w ==0){
                if(h>=3 && w>=h){
                    if((h-2)*(w-2) == yellow){
                        answer[0] = w;
                        answer[1] =h;
                        return answer;
                    }
                }
            }
        }
        
     

        return answer;
    }
}

가로-2 * 세로-2 == yellow가 되는 걸 집중했다.

여기서 w의 최대값은 brown과 yellow를 합친 수와 같다.

1*카펫의 최대길이 = brown+yellow이다.

h≥3이상인 경우는 그래야만 테두리가 brown으로 감싸진 모양의 조건이 성립하게 된다.

마지막으로 가로세로의 곱셈이 yellow와 같은지 판별하고 return하면 된다.

4. Review

프로그래머스에서 문제를 풀 때에는 시간복잡도에대해 전혀 신경을 쓰지 않게 되어버린듯 하다. 하지만 시간복잡도는 꼭 필요한 개념이니까 잊지말고 계산해보도록 하자.

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL