프로그래머스 2023.09.13 (2Lv 시소 짝꿍)

프로그래머스

문제

---

문제 설명
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

제한 사항
  ◈ 2 ≤ weights의 길이 ≤ 100,000
  ◈ 100 ≤ weights[i] ≤ 1,000
        ◈ 몸무게 단위는 N(뉴턴)으로 주어집니다.
        ◈ 몸무게는 모두 정수입니다.

입출력 예

weights	result
[100, 180, 360, 100, 270]	4

입출력 예 설명
{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

코딩

---

#include <string>
#include <vector>
#include <map>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    vector<vector<bool>> vecPiar(weights.size(), vector<bool>(weights.size(), false));
    map<int, vector<int>> map_wight;

    for (size_t i = 0; i < weights.size(); ++i)
    {

        for (int c = 2; c < 5; ++c)
        {
            int iWeight = weights[i] * c;

            map<int, vector<int>>::iterator iter = map_wight.find(iWeight);
            if (iter == map_wight.end())
            {
                map_wight.insert(make_pair(iWeight, vector<int>(1, i)));
            }
            else
            {
                for (size_t j = 0; j < iter->second.size(); ++j)
                {
                    if (vecPiar[i][iter->second[j]] || vecPiar[iter->second[j]][i])
                        continue;

                    int imin = min((int)i, iter->second[j]);
                    int imax = max((int)i, iter->second[j]);

                    vecPiar[imin][imax] = true;
                    answer++;
                }
                iter->second.push_back(i);
            }
        }
    }

    return answer;
}

<위 코드는 틀린 코드입니다.>

map을 하나 만들어서 인자로 주어지는 몸무게 배열을 순회하면서 각 거리별 몸무게 계산 결과를 Key값으로 몸무게 배열의 인덱스를 Value로 저장해 주었다. 뿐만 아니라 각 거리에 따른 몸무게를 계산할 때, Map에 존재하는지 확인해 평행이 되는 조합이 있다면, answer를 증가해 평행이 되는 조합을 구해주었다.

이때, 이미 있는 조합을 검사할 필요가 없기 때문에 예외처리를 해주어 풀었다.

 

이렇게 풀면 모든 경우를 확인해 평행을 이루는 조합을 찾을 수 있다.

 

하지만, 4가지 테스트 항목에서 시간초과가 걸렸다. (위 코드의 경우 answer 반환을 단순히 증가연산자로 1씩 증가하기 때문에 자료형을 벗어나 틀리는 경우(11~14번 테스트 항목)는 발생하지 않는다. 단지 시간 초과문제)

 

생각해 보니 동일한 몸무게가 존재한다면, 검사하지 않아도 되지만 계속 검사하고 있기 때문에 불필요한 연산이 발생해 연산 시간이 오래 걸린다 판단했다.

 

때문에 동일한 몸무게가 인자로 주어지는 몸무게 배열에 존재한다면, 하나로 묶어서 검사를 진행하면 시간이 획기적으로 덜 걸릴 것이라 생각했다.

 

#include <string>
#include <vector>
#include <map>

using namespace std;

long long calcul(int _i)
{
    long long ireturn = 0;
    for (int i = 0; i < _i; ++i)
    {
        ireturn += i;
    }
    return ireturn;
}

long long solution(vector<int> weights) {
    long long answer = 0;
    vector<int> vecNewweight = {};
    map<int, int> map_wights;

    // 중복되는 몸무게 합치기
    for (size_t i = 0; i < weights.size(); ++i)
    {
        map<int, int>::iterator iter = map_wights.find(weights[i]);
        if (iter == map_wights.end())
        {
            map_wights.insert(make_pair(weights[i], 1));
            vecNewweight.push_back(weights[i]);
        }
        else
        {
            iter->second++;
        }
    }

    map<int, int>::iterator iter = map_wights.begin();
    for (; iter != map_wights.end(); ++iter)
    {
        if (iter->second != 1)
        {
            answer += calcul(iter->second);
        }
    }

    map<int, vector<int>> map_wight;
    vector<vector<bool>> vecPiar(vecNewweight.size(), vector<bool>(vecNewweight.size(), false));

    for (size_t i = 0; i < vecNewweight.size(); ++i)
    {
        for (int c = 2; c < 5; ++c)
        {
            int iWeight = vecNewweight[i] * c;

            map<int, vector<int>>::iterator iter = map_wight.find(iWeight);
            if (iter == map_wight.end())
            {
                map_wight.insert(make_pair(iWeight, vector<int>(1, i)));
            }
            else
            {
                for (size_t j = 0; j < iter->second.size(); ++j)
                {
                    if (vecPiar[i][iter->second[j]] || vecPiar[iter->second[j]][i])
                        continue;

                    int imin = min((int)i, iter->second[j]);
                    int imax = max((int)i, iter->second[j]);

                    vecPiar[imin][imax] = true;
                    answer += (long long)(map_wights.find(vecNewweight[i])->second * map_wights.find(vecNewweight[iter->second[j]])->second);
                }
                iter->second.push_back(i);
            }
        }
    }

    return answer;
}

<위의 코드는 테스트에 성공한 코드이다.>

그러기 위해서 규칙을 생각해 보게 되었다.

 

몸무게 배열이 { 100, 100, 100, 100, 200, 300, 200 }으로 주어질 경우를 생각해 보자.

그러면 100이 총 4개, 200이 2개, 300이 1개가 나온다.

이때, 각 조합의 수는 0부터 n(해당 몸무게의 개수)까지 더하는 것이다.

0 + 1 + 2 + 3 +... (n-1) = 해당 몸무게의 조합 경우의 수

따라서 몸무게 100은 보라색의 결과를 가지고, 200은 초록색의 결과를 갖는다.

이런 경우의 수들을 모두 더하면 겹치는 몸무게로 발생할 수 있는 조합의 수가 나온다.

(즉, 위 배열에서는 7가지가 나온다.)

 

이제 100, 200, 300이라는 배열을 가지고 발생할 수 있는 조합 경우의 수를 생각해 보면,

100이 4개, 200이 2개이므로 4 * 2를 하면, 해당 몸무게 조합으로 발생할 수 있는 모든 조합의 수가 나온다. (분홍색)

마찬가지로 200과 300의 조합은 200이 2개 300이 1개이기 때문에 2 * 1을 하면, 2가지가 나온다. (노란색)

따라서 모든 경우의 수를 더하면, 6(보라) + 1(초록) + 8(분홍) + 2(노랑) = 17

즉, 직접 만들어본 조합의 수와 동일하게 나오는 것을 확인할 수 있다.

 

때문에 중복되는 몸무게의 개수를 map으로 정리해 두고, 새로운 배열을 만들어 겹치지 않는 몸무게들을 저장해 두었다. (map_Wights 만들기, vecNewWieght 만들기)

이후 map을 순회하면서 겹치는 수로 만들 수 있는 조합 경우의 수를 계산해 주었다. (calcul() 함수 부분) 

 

다음으로 동일하지 않은 몸무게끼리 조합 경우의 수를 구하기 위해 vecNewWeight를 순회하면서, 계산하지 않은 나머지 조합 경우의 수를 계산해 주었다.

이때, 동일한 조합을 또 계산할 수 있기 때문에 방문 처리를 해줄 2차 행렬(vecPiar)을 만들어 발생하지 않도록 예외처리 해주었다.

 

이렇게 하면, 첫 번째 코드보다 훨씬 더 빠르게 모든 조합을 체크해 볼 수 있다.

 

하지만 처음에 조합 경우의 수를 계산할 때 자료형을 int로 하는 바람에 int가 넘어갈 수 있는 서로 동일하지 않은 몸무게끼리의 조합 경우의 수를 계산할 때, int자료형 사이즈를 넘어가 실패가 떴었다.

때문에 long long 자료형으로 형변환을 해준 뒤, answer와 더해주었다.

실행 결과

---

<시간 초과로 실패한 1번째 코드 결과>

<테스트 성공한 2번째 코드 결괴>