한 선이 만나는 다른 선의 수

123

456

789

암호 패턴.

이미 사용한 번호를 다시 사용할 수 없음.

사용되지 않은 번호를 건너뛰어 매길 수 없음.

(1-5-9-6-3-7은 가능하지만, 1-9-6-3처럼 1-9에서 사용하지 않은 5를 건너뛸 수 없음.)

각 직선(1-5,5-9,9-6,6-3,3-7)이 만나는 다른 직선의 수를 반환.

 

 

문제의 형태 때문에, getX와 getY에서 123456789를 쓰게 되는 것.

이와 상관없이 x, y 값만 주어져도 아래의 함수 계산은 항상 유효함.

 

 

1차 함수는 모두 y = a*x + b의 형태로 나타낼 수 있음.

y - yj = s(x - xj) 에서,

y = s*x -s*xj+yj 가 될 수 있기 때문.

 

 

class Line {
    boolean isLinearX;
    boolean isLinearY;
    int minx;
    int maxx;
    int miny;
    int maxy;
    float slope;
    int yj;
    int lx;
    int ly;
    Line(int dot1, int dot2) {
        int dot1x = getX(dot1);
        int dot1y = getY(dot1);
        int dot2x = getX(dot2);
        int dot2y = getY(dot2);
        this.minx = Math.min(dot1x, dot2x);
        this.maxx = Math.max(dot1x, dot2x);
        this.miny = Math.min(dot1y, dot2y);
        this.maxy = Math.max(dot1y, dot2y);
        this.slope = getSlope(dot1x, dot1y, dot2x, dot2y);
        if(this.slope==0) {
            if(dot1x==dot2x) {
                this.isLinearX = true;
                lx = dot1x;
            } else {
                this.isLinearY = true;
                ly = dot1y;
            }
        } else {
            this.yj = (int)(dot1y-slope*dot1x);
        }
    }
}

public int getX(int dot) {
    dot %= 3;
    if(dot==0) dot=3;
    return dot-1;
}

public int getY(int dot) {
    dot = (dot-1)/3;
    switch(dot) {
    case 0: return 2;
    case 1: return 1;
    case 2: return 0;
    default: return 0;
    }
}

public float getSlope(int dot1x, int dot1y, int dot2x, int dot2y) {
    if(dot1x==dot2x || dot1y==dot2y) return 0;
    else {
        return (dot2y*1.0f-dot1y)/(dot2x*1.0f-dot1x);
    }
}

해당 점의 x좌표를 구하는 getX, y좌표를 구하는 getY, 두 점간 기울기를 구하는 getSlope().

123

456

789 에서,

y축에 147을, x축에 789를 겹쳐서, x는 0,1,2, y는 0,1,2로 좌표값을 얻기도 한다.

 

Line 클래스는

y=상수 형태나 x=상수인지를 표시하는 boolean들, (x=상수 형태는 기울기가 0이 아니라 무한이니 boolean으로..)

두 점의 x, y들(x만 하면 y가 만나지 않는데도 x가 겹칠 수 있으므로 둘 다 기록. (1~2)와(8~9)는 서로 붕뜬 y에서 x만 만남))

기울기, y절편,

y=상수 이거나 x=상수일 때의 상수값을 기록한다.

 

 

int[] answer = new int[pattern.length-1];
Line[] lines = new Line[answer.length];
for(int i=0;i<lines.length;i++) {
    lines[i] = new Line(pattern[i],pattern[i+1]);
}

정답 배열은 점→선이니 1칸 작게.

양 끝 번호를 정보로 하여 Line들을 생성.

 

 

for(int i=0;i<answer.length;i++) {
    Line now = lines[i];
    int ans = 0;
    for(int j=0;j<answer.length;j++) {
        if(j!=i) {
            Line cmp = lines[j];
            if(now.isLinearX||now.isLinearY) {
                if(now.isLinearX) {
                    if(cmp.isLinearX) {
                        if(now.lx==cmp.lx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) ans++;
                    } else if(cmp.isLinearY) {
                        if(now.minx<=cmp.maxx&&now.maxx>=cmp.minx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) ans++;
                    } else {
                        float y = cmp.slope*now.lx+cmp.yj;
                        if(now.miny<=y&&now.maxy>=y) ans++;
                    }
                } else {
                    if(cmp.isLinearY) {
                        if(now.ly==cmp.ly&&now.minx<=cmp.maxx&&now.maxx>=cmp.minx) ans++;
                    } else if(cmp.isLinearX) {
                        if(now.minx<=cmp.maxx&&now.maxx>=cmp.minx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) ans++;
                    } else {
                        float x = (now.ly*1.0f-cmp.yj)/cmp.slope;
                        if(now.minx<=x&&now.maxx>=x) ans++;
                    }
                }
            } else if(cmp.isLinearX||cmp.isLinearY) {
                if(cmp.isLinearX) {
                    float y = now.slope*cmp.lx+now.yj;
                    if(cmp.miny<=y&&cmp.maxy>=y) ans++;
                } else {
                    float x = (cmp.ly*1.0f-now.yj)/now.slope;
                    if(cmp.minx<=x&&cmp.maxx>=x) ans++;
                }
            } else {
                if(now.slope==cmp.slope) {
                    if(now.minx<=cmp.maxx&&now.maxx>=cmp.minx) ans++;
                } else {
                    float x = (cmp.yj*1.0f-now.yj)/(now.slope-cmp.slope);
                    if(now.minx<=x&&now.maxx>=x) ans++;
                }
            }
        }
    }
    answer[i] = ans;
}

아래에서 다시 상세히.

↓

 

 

if(now.isLinearX||now.isLinearY) {
    if(now.isLinearX) {
        if(cmp.isLinearX) {
            if(now.lx==cmp.lx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) ans++;
        } else if(cmp.isLinearY) {
            if(now.minx<=cmp.maxx&&now.maxx>=cmp.minx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) ans++;
        } else {
            float y = cmp.slope*now.lx+cmp.yj;
            if(now.miny<=y&&now.maxy>=y) ans++;
        }
    } else {
        if(cmp.isLinearY) {
            if(now.ly==cmp.ly&&now.minx<=cmp.maxx&&now.maxx>=cmp.minx) ans++;
        } else if(cmp.isLinearX) {
            if(now.minx<=cmp.maxx&&now.maxx>=cmp.minx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) ans++;
        } else {
            float x = (now.ly*1.0f-cmp.yj)/cmp.slope;
            if(now.minx<=x&&now.maxx>=x) ans++;
        }
    }
}

(상수형태가 존재할 때 - 내가 상수일 때)

현재대상이 x=상수 일 때,

 

비교대상도 x=상수라면, 둘 의 x값이 같고(같지 않으면 평행으로 영영 못만남)

y가 겹쳐야 함(무한한 직선이 아니라 구간이 존재해서).

(now.miny>cmp.maxy||now.maxy<cmp.miny) 이면 서로 붕 떠서 y 구간이 겹치지 않음. 이걸 반대로 하면

(now.miny<=cmp.maxy&&now.maxy>=cmp.miny) 는 겹친다는 것임.

 

비교대상이 y=상수라면, 그래프상으로는 어떻게든 직교하겠으나,

x와 y가 각각 겹쳐야 함.

위의 통합판인

(now.minx<=cmp.maxx&&now.maxx>=cmp.minx&&now.miny<=cmp.maxy&&now.maxy>=cmp.miny) 로 검사.

 

비교대상이 y=ax+b의 형태라면, x에 현재대상의 상수인 lx를 넣어,

y = a*(lx)+b 를 구할 수 있음.

이 y는 비교대상 함수에서 구한 것이므로, 현재대상의 y구간에도 포함되어 있어야 만나는 것.

(now.miny<=y&&now.maxy>=y) 로 검사.

 

 

현재대상이 y=상수 일 때,

 

비교대상도 y=상수라면, 위와 같으나 lx대신 ly, y구간 대신 x구간 겹침검사.

 

비교대상이 x=상수라면, 위와 같이 x, y 통합 구간검사.

 

비교대상이 y=ax+b의 형태라면, y에 현재대상의 상수인 ly를 넣어,

ly = ax +b로,

x=(ly-b)/a 를 구할 수 있음.

이 x는 비교대상 함수에서 구한 것이므로, 현재대상의 x구간에도 포함되어 있어야 만나는 것.

(now.minx<=x&&now.maxx>=x) 로 검사.

 

 

else if(cmp.isLinearX||cmp.isLinearY) {
    if(cmp.isLinearX) {
        float y = now.slope*cmp.lx+now.yj;
        if(cmp.miny<=y&&cmp.maxy>=y) ans++;
    } else {
        float x = (cmp.ly*1.0f-now.yj)/now.slope;
        if(cmp.minx<=x&&cmp.maxx>=x) ans++;
    }
}

(상수형태가 존재할 때 - 나는 함수고 상대만만 상수일 때)

위에서 이미 둘 다 상수형태인 검사는 해봤으니,

현재대상이 함수형태이고, 비교대상이 상수형태인 것만 비교하면 됨.

 

비교대상이 x=상수 형태라면,

현재대상의 함수에 비교대상의 상수인 lx를 넣어,

y = a*(lx)+b 를 구할 수 있음.

이 y는 현재대상 함수에서 구한 것이므로, 비교대상의 y구간에도 포함되어 있어야 만나는 것.

(cmp.miny<=y&&cmp.maxy>=y) 로 검사.

 

비교대상이 y=상수 형태라면,

현재대상의 함수에 비교대상의 상수인 ly를 넣어,

ly = ax +b로,

x=(ly-b)/a 를 구할 수 있음.

이 x는 현재대상 함수에서 구한 것이므로, 비교대상의 x구간에도 포함되어 있어야 만나는 것.

(cmp.minx<=x&&cmp.maxx>=x) 로 검사.

 

 

else {
    if(now.slope==cmp.slope&&now.yj==cmp.yj) {
        if(now.minx<=cmp.maxx&&now.maxx>=cmp.minx) ans++;
    } else {
        float x = (cmp.yj*1.0f-now.yj)/(now.slope-cmp.slope);
        if(now.minx<=x&&now.maxx>=x) ans++;
    }
}

(함수형태-함수형태끼리일 때)

 

둘 다 함수형태일 때,

y = ax + b 와 y = a'x + b' 가 만나는 점,

ax + b = a'x + b',

0 = (a'-a)x + b'-b,

x= (b-b')/(a'-a) 를 구할 수 있다.

이 x가 현재 직선의 x구간 안에 있다면 직선 안에서 교점하는 것.

(now.minx<=x&&now.maxx>=x) 로 검사한다.

 

기울기가 같다면 0으로 나누는 예외가 발생할 수 있다.

기울기가 같을 때, y절편이 다르다면 평행하여 만나지 못하는 선이 된다.

기울기가 같다면 y절편도 같아야 만날 가능성이 생긴다.

기울기도 같고 y절편도 같을 때(함수 형태가 동일할 때), x구간이든 y구간이든 어느 구간이라도 겹치면 만난다.