[프로그래머스/C++] 교점에 별 만들기

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 정수로 이루어진 교점에 별을 찍는 문제다.

 

먼저 교점을 찾는 방법은 쉽다.

연립 방정식을 풀듯이 x의 계수를 일치시켜 y값을 구하고, y의 계수를 일치시켜 x값을 구하면 된다.

 

여기서 두 계수를 일치시키는 방법은 곱셈으로 해결했다.

(곱셈을 사용하므로 변수형을 long long 으로 해주어야 한다.)

 

1번 함수의 x계수를 2번 함수의 x, y계수와 d값에 곱한다.

2번 함수의 x계수를 1번 함수의 x, y계수와 d값에 곱한다. 

 

이후 두 식을 빼주면 x항은 사라지고 y계수와 d값만 남게 된다.

 

여기서 y항이나 x항이 사라져 상수만 남게 되는 경우는 두 함수가 평행인 경우 밖에 없다.

 

그러므로 평행인 경우는 계산을 하지 않도록 제외해주면 쉽게 x값과 y값을 구해 문제를 해결할 수 있다.

 

여기서 정수가 아닌 교점은 제거해야하므로 % 연산자를 이용해 정수가 아닌 교점은 제거해주었다.

 

그리고 교점의 범위를 나타낼 때 별을 표현할 수 있는 가장 작은 사각형으로 표현하기로 했으므로, x값과 y값의 min, max값을 각각 구했다.

 

그러면 max값과 min 값의 차를 이용해 교점을 표현하기 위한 y와 x의 길이를 구할 수 있다.

 

+ 교점의 크기를 구한 뒤 주의해야할 점은 vector<string>V 에서 V[0]은 교점의 maxY를 나타낸다. 

Y축 값이 높을 수록 vector에서 0에 가까워 진다는 뜻이다. 

 

 

​

[아이디어 정리]

1. 교점을 구하기 위해 계수를 곱해 하나의 항을 없애고 y값과 x값을 구한다.
2. 이때, 평행한 경우에는 교점이 없으므로 기울기가 같은 경우는 제외한다.
3. 마찬가지로 교점의 y값이나, x값이 정수가 아닌 경우는 제외한다.
4. Y와 X의 min, max값을 이용해 교점을 표현할 직사각형의 변의 길이를 구한다.
5. 교점은 크기가 [maxY-minY+1][maxX-minX+1]로 선언된 2차원 벡터에 [maxY-y][x-minX]에 위치한다.

 

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

const long long INF=1000000000000;
vector<string> solution(vector<vector<int>> line) {
    vector<pair<long long,long long>> answer;
    // y를 먼저 구하고 x구하기
    long long minY=INF,minX=INF,maxY=-INF,maxX=-INF;
    long long aXY,a,bXY,b,y,x;
    long long nums, xy;
    for (int i=0; i<line.size()-1; i++)
    {
        for (int j=i+1; j<line.size(); j++)
        {
            
            aXY=(long long)line[i][1]*(long long)line[j][0], a=(long long)line[i][2]*(long long)line[j][0];
            bXY=(long long)line[j][1]*(long long)line[i][0], b=(long long)line[j][2]*(long long)line[i][0];
            
            if (aXY==bXY)
            { //평행제거
                continue;
            }
            
            xy=aXY-bXY;
            nums=b-a;
            
            if (abs(nums)%abs(xy)!=0)
            {
                continue;
            }
            y=nums/xy;
            a=(long long)line[i][2]*(long long)line[j][1], b=(long long)line[j][2]*(long long)line[i][1];
            
            xy=bXY-aXY;
            nums=b-a;
            if (abs(nums)%abs(xy)!=0)
            {
                continue;
            }
            x=nums/xy;
            minX=min(minX,x), minY=min(minY,y),maxX=max(maxX,x),maxY=max(maxY,y);
            answer.push_back(make_pair(y,x));
        }
    }
    
    vector<string>retA(maxY-minY+1,string(maxX-minX+1, '.'));
    
    for (int i=0; i<answer.size(); i++)
    {
        retA[maxY-answer[i].first][answer[i].second-minX]='*';
    }
    return retA;
}

 

---

처음에 x값을 구하면 구한 x값으로 y값을 빠르게 구하려고 했는데, 예외처리해야할 것들이 많아졌다.

그래서 그냥 x값과 y값을 각각 구하도록 코드를 구현했다.

중간에 long long으로 선언한 변수가 int형의 곱셈 때문에 제대로 계산이 되지 않는 문제가 있었다.

이 과정에서 시간이 좀 걸렸다 ㅠㅠㅠ

풀기 전에는 까다로운 문제였는데 풀고나니 쉽게 느껴지는 문제였다...

 

프로그래머스