프로그래머스 Level 2 : 교점에 별 만들기 C언어

▶문제 : 코딩테스트 연습 - 교점에 별 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

long long point[1000000][2];//교점 위치 [0] : x , [1] : y
int len;

char **solution(int **line, size_t line_rows, size_t line_cols) {
    long long left, right, top, bottom;//구한 좌표 중 가장자리의 좌표
    left = bottom = 10000000000;//비교를 위해 큰 값 대입
    right = top = -10000000000;//비교를 위해 작은 값 대입
    long long num, tmp;
    double numX, numY;
    for (int i = 0; i < line_rows - 1; i++) {
        for (int j = i + 1; j < line_rows; j++) {
            num = (long long)line[i][0] * line[j][1] - (long long)line[i][1] * line[j][0];//분모
            if (num == 0) continue;//분모가 0이면 교점이 없음
            else {
                tmp = (long long)line[i][1] * line[j][2] - (long long)line[i][2] * line[j][1];
                numX = (double)tmp / num;//x좌표
                tmp = (long long)line[i][2] * line[j][0] - (long long)line[i][0] * line[j][2];
                numY = (double)tmp / num;//y좌표
                if (numX == (long long)numX && numY == (long long)numY) {//정수일 때
                    point[len][0] = numX;
                    point[len++][1] = numY;
                    if (left > point[len - 1][0]) left = point[len - 1][0];//가장 왼쪽의 좌표
                    if (right < point[len - 1][0]) right = point[len - 1][0];//가장 오른쪽의 좌표
                    if (top < point[len - 1][1]) top = point[len - 1][1];//가장 위쪽의 좌표
                    if (bottom > point[len - 1][1]) bottom = point[len - 1][1];//가장 아래쪽의 좌표
                }
            }
        }
    }

    int height, width;//별을 그리는 범위 : 세로, 가로
    height = top - bottom + 1;
    width = right - left + 1;

    char **answer = (char **)malloc(sizeof(char *) * height);
    char *ch;
    for (int i = 0; i < height; i++) {//모든 맵에 '.'대입
        ch = (char *)malloc(width + 1);
        for (int j = 0; j < width; j++) ch[j] = '.';
        ch[width] = '\0';
        answer[i] = ch;
    }

    int x, y;
    for (int i = 0; i < len; i++) {//point배열의 좌표에 따라 별 그리기
        x = point[i][0] - left;
        y = top - point[i][1];
        answer[y][x] = '*';
    }

    return answer;
}

 

▶해석

구하는 단계는 총 6단계가 있다.

1단계 : 모든 직선의 교점을 확인할 수 있도록 for문 작성

2단계 : 분모가 0인지 확인하여 교점의 유무 확인

3단계 : 구한 x좌표와 y좌표가 정수인지 확인하여 point배열에 대입

4단계 : 각 가장자리의 left, right, top, bottom 좌표를 구하기

5단계 : 별을 그리는 범위를 구하여 문자열 포인터 answer를 선언하고 '.'으로 채우기

6단계 : point배열에 담은 좌표들을 answer크기에 맞춰 계산하여 '*'대입

 

테스트 케이스 27번, 28번과 29번을 번갈아가며 틀렸었다.

29번은 line배열의 값들을 이용해 교점 좌표를 구하는데 line [i][0]*line [j][1] 이런 식으로 A, B, C, D, E, F값을 곱하여 구할 때 int형으로 하면 범위를 초과하여 실패하게 된다. 따라서 long long으로 형 변환시켜 (long long) line [i][0]*line [j][1] 작성하면 된다.

27번, 28번은 구한 좌표가 int형의 범위를 넘어가는 경우가 발생한다. 따라서 좌표를 저장하는 point배열과 가장자리의 좌표를 구하는 left, right, top, bottom변수를 long long으로 선언하여야 한다.