[프로그래머스,Java] Level2: 시소짝궁

 

문제분석

 

문제는 매우 간단하다  서로다른 weights 2개를 골라서 그 경우가 

총 7개의 케이스 4:3 ,4:2,3:2, 1:1 ,2:3, 3:4, 2:4 인 경우를 판단하면된다.

 

 

FirstTry : 문제대로 풀기 

 

그냥 문제대로 풀었다.

 

2차 반복문으로 서로다른 사람의 몸무게를 2개 골라  case를 판별한다.

 

case의 부합한다면 answer++를 증가시키는 간단하게 구현했지만..

 

효율성에러

 

문제 풀고보니 제한사항이 사람의 몸무게 갯수가 10만까지 간다.

 

구글에 쳐보니 10만*10만이 100억이라고 한다.  당연히 걸릴만한 시간복잡도다..

 

 

Second Try: 1차 반복문으로 줄이기

 

1차 반복문으로 줄여서 구현해야한다.

 

여기서 생각난게  Arr또는 Map을 구현해서 정보를 저장해두는게 현명하다 보았다.

 

그 이유는, 어처피  각 몸무게는 확인해야할 몸무게는 총 7개의 케이스의 몸무게 뿐이다.

 

각 케이스마다 몸무게를 저장하고,  그 케이스의 7개의 케이스가 저장된 메모리를 검색해서 그 갯수만큼 커플수를 올린다.

 

 

첫번째 로직과는 다르게  이 두번째로직은  한정된 배열안에서 검색을 하는 행위기때문에,

 

소수점을 발생하는 경우와  배열의 범위를 넘어가는 경우를 철저하게 배제해줘야한다.

 

 

 

 

오늘의 교휸 : 제한사항 꼭 유의하자

문제풀이

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        int[] board = new int[1001];
        
        for(int weight : weights){
            if(board[weight]!=0){
                answer+=board[weight];           
            }
            if(weight*2<=1000&&board[weight*2]!=0){
                answer+=board[weight*2];  
            }
            if(weight%2==0&&weight/2>=100&&board[weight/2]!=0){
                answer+=board[weight/2];  
            }
            if(weight%2==0&&(weight/2)*3<=1000&&board[(weight/2)*3]!=0){
                answer+=board[(weight/2)*3];  
            }
            if(weight%3==0&&(weight/3)*2>=100&&board[(weight/3)*2]!=0){
                answer+=board[(weight/3)*2];  
            }
            if(weight%3==0&&(weight/3)*4<=1000&&board[(weight/3)*4]!=0){
                answer+=board[(weight/3)*4];  
            }        
            if(weight%4==0&&(weight/4)*3>=100&&board[(weight/4)*3]!=0){
                answer+=board[(weight/4)*3];  
            }
             
            board[weight]++;   
        }
        
        return answer;
    }
}