[프로그래머스] Level 2. 시소 짝꿍

 

https://school.programmers.co.kr/learn/courses/30/lessons/152996

프로그래머스

 

 

해결 방법(실패)

• 합이 N이 되는 무게들의 인덱스 정보를 ws에 저장한다. 예를들어 무게 360을 만들 수 있는 인덱스가 1,2 일경우, 360 : [1,2] 이런식으로 ws에 저장한다.
• 한 개 씩 정보를 저장하면서 페어를 맞출 수있는 개수를 찾는다.

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <algorithm>

using namespace std;

int pushItem(unordered_map<int,vector<int>>& ws, int i, int _weight){
    vector<int> ratios= {2,3,4};
    unordered_set<int> pairs;
    
    for(int r = 0; r< ratios.size(); r++){
        int w = _weight * ratios[r];
        
        if(ws.find(w) == ws.end()){
            ws.insert({w,vector<int>()});
            ws[w].push_back(i);
            continue;
        } 
        
        for(int idx =0 ; idx<ws[w].size(); idx++){
            pairs.insert(ws[w][idx]);
        }
        
        ws[w].push_back(i);
    }
    
    return pairs.size();
}

long long solution(vector<int> weights) {
  
    unordered_map<int,vector<int>> ws;
    vector<vector<int>> pairs(weights.size());
    long long answer = 0;
    
    //가능한 숫자들을 ws에 넣어줌. 180kg [0,1,2] 형식으로.
    for(int i=0; i<weights.size(); i++){
        answer += pushItem(ws,i, weights[i]);
    } 
    return answer;
}

 

 

이 방식은 4개 테스트에서 시간초과 발생하였다. 다른방법을 찾아야 했다. 간단한 문제인데 너무 어렵게 생각해서 돌아가는 느낌이 들었다.  정렬을 해보면 풀이가 간단해질까? 하는 생각이 들었다.

 

해결 방법(성공) 

정렬을 한 다음, 만약 100이 있고 페어를 찾고있다고 가정해보자. 그 뒤에있는 값이 200보다 크다면, 아무리 100짜리를 시소 뒤에 앉히고(100x4) 200짜리를 맨 앞에 앉혀도(201x2) 짝꿍이 맞을 수 없다는 것을 알 수 있다. 

이렇게 하여 , 값이 불필요하게 큰 경우는  아예 검사하지 않는 방법으로 문제를 해결했다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

long long solution(vector<int> weights) {
   long long answer = 0;
    sort(weights.begin(), weights.end()); //가벼운것부터 검사
    for(int i =0; i<weights.size();  i++){
        for(int j = i+1; j<weights.size(); j++){
            if(weights[i] *2 <weights[j]) break; //값의차이가 커서 맞을 수없음.
            int a= weights[i]; int b = weights[j];
            if(a == b || a*3 == b*2 || a*2 == b || a*4 == b*3)  answer++; //조건에 부합하는지
        }
    }
    return answer;
}

 

마무리 하며

간단한 문제인데도 풀이방법을 찾지 못하는 경우가 많다. 슬럼프인것 같기도 하다. 이 문제도 풀고나니 "도대체 왜 이렇게 간단한 방법을  생각하지못했을까?" 라는 생각이 들 정도로 허무했다. 너무 기발한 아이디어만을 찾고있는게 아닌가 싶다.