프로그래머스 level 2 - 교점에 별 만들기 (Java)

• 문제 링크

1. 접근 방법

문제를 읽어 보면, 교점도 구해야 하고 그 교점을 모아두는 컬렉션도 필요할 듯 하다. 그래서 다른 코딩테스트 문제들처럼 한 메서드에 모든 코드를 넣어두기 보다는, 새로운 클래스들을 생성해서 문제를 푸는게 좋을 듯 하다.

한가지 유의할 점이 있는데, 데이터 타입을 잘 지정해야 한다. 직선의 계수가 int 타입이라고 교점 역시 int의 범위 내에 존재하진 않는다. 문제에 교점에 대한 범위 제한이 없으므로 long 타입으로 지정하는 것이 안전하다. 실제로 교점을 int로 여기고 문제를 풀면 오버플로우가 일어나 테스트 케이스 중 몇 개는 틀린다.

2. 전체 코드

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        PointSet points = new PointSet();
        
        for(int i=0; i<line.length; i++) {
            for(int j=i+1; j<line.length; j++) {
                Interpoint point = Interpoint.makeInterpoint(line[i],line[j]);
                if (point != null) points.addPoint(point);
            }
        }
        
        return points.makeGrid();
    }
}

//두 직선의 교점 클래스
class Interpoint {
	//교점 (x,y)의 데이터 타입은 long으로 설정
    private final long x;
    private final long y;

    Interpoint(long x, long y) {
        this.x = x;
        this.y = y;
    }

    long getX(){
        return x;
    }

    long getY(){
        return y;
    }
    
    //두 직선 line1, line2의 교점 반환
    static Interpoint makeInterpoint(int[] line1, int[] line2) {
        //line1, line2가 평행하거나 교점이 정수가 아니면 null 반환
        long denominator = (long)line1[0]*line2[1]-(long)line1[1]*line2[0];
        if (denominator == 0) return null;
        
        long moleculeX = (long)line1[1]*line2[2]-(long)line1[2]*line2[1];
        long moleculeY = (long)line1[2]*line2[0]-(long)line1[0]*line2[2];
        
        if (moleculeX%denominator != 0 || moleculeY%denominator != 0) return null;
        
        //교점이 정수면 Interpoint 인스턴스 반환
        return new Interpoint(moleculeX/denominator, moleculeY/denominator);
    }

	@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Interpoint that = (Interpoint) o;
        return x == that.x && y == that.y;
    }
    
	@Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

//교점들의 집합 클래스
class PointSet{
    private final Set<Interpoint> points;
    private long maxX, minX, maxY, minY;

    PointSet() {
        this.points = new HashSet<>();
    }

	//교점을 교점집합 안에 저장
    void addPoint(Interpoint point) {
        points.add(point);
        
        if (points.size()==1) {
            maxX=minX=point.getX();
            maxY=minY=point.getY();
        } else {
            maxX=Math.max(maxX,point.getX());
            minX=Math.min(minX,point.getX());
            maxY=Math.max(maxY,point.getY());
            minY=Math.min(minY,point.getY());
        }
    }

	//교점을 나타내는 격자판 생성
    String[] makeGrid() {
        String[] result = new String[(int)(maxY-minY+1)];
        int ind=0;
        
        for(long j=maxY; j>=minY; j--) {
            StringBuffer buffer = new StringBuffer();
            for(long i=minX; i<=maxX; i++) {
                if (points.contains(new Interpoint(i,j))) buffer.append('*');
                else buffer.append('.');
            }
            result[ind++] = new String(buffer);
        }

        return result;
    }
}

3. 코드 분석

중요한 부분들을 하나씩 살펴보자.

기본적으로 여러 직선들의 교점을 전부 살피려면 두 직선을 골라서 확인하면 된다.

for(int i=0; i<line.length; i++) {
            for(int j=i+1; j<line.length; j++) {
                ......
            }
        }

1) Interpoint 클래스

Interpoint 클래스의 두 필드 x, y는 오버플로우가 일어나지 않게 long으로 타입을 지정해줬고, 두 직선의 교점을 구하는 메서드를 다음과 같이 작성했다.

static Interpoint makeInterpoint(int[] line1, int[] line2) {
        //line1, line2가 평행하거나 교점이 정수가 아니면 null 반환
        long denominator = (long)line1[0]*line2[1]-(long)line1[1]*line2[0];
        if (denominator == 0) return null;
        
        long moleculeX = (long)line1[1]*line2[2]-(long)line1[2]*line2[1];
        long moleculeY = (long)line1[2]*line2[0]-(long)line1[0]*line2[2];
        
        if (moleculeX%denominator != 0 || moleculeY%denominator != 0) return null;
        
        //교점이 정수면 Interpoint 인스턴스 반환
        return new Interpoint(moleculeX/denominator, moleculeY/denominator);
    }

교점이 없거나 정수가 아니면 필요없는 것이므로 null을 반환하도록 했다.

또한 equals()와 hashCode()를 오버라이딩했는데, 이는 PointSet 클래스의 makeGrid()에서 쓰이는 contains()를 위해서다. contains()는 내부적으로 equals()와 hashCode()를 모두 사용해서 포함 여부를 확인하는데, 서로 다른 참조값을 가진 객체들은 이 두 메서드의 값이 다르기 때문이다. 따라서 서로 다른 객체라 하더라도 모든 필드값만 일치하면 contains()가 true를 반환하게끔 적절히 오버라이딩 해주었다.

	@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Interpoint that = (Interpoint) o;
        return x == that.x && y == that.y;
    }
    
	@Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

2) PointSet 클래스

	private final Set<Interpoint> points;
    private long maxX, minX, maxY, minY;

찾은 교점들은 PointSet 클래스의 points, 즉 교점 집합에 저장한다. 자료구조 타입이 Set인 이유는 두 쌍의 직선에서 교점을 찾았더니 그 교점이 같을 수도 있어서, 중복을 제거해주기 위함이다. maxX...minY는 교점이 존재하는 범위를 저장하기 위해 사용할 것이다.

	Interpoint point = Interpoint.makeInterpoint(line[i],line[j]);
    if (point != null) points.addPoint(point);

Interpoint.makeInterpoint()로 두 직선의 교점 객체를 만들고, 그 값이 null이 아니면 points에 저장한다. 이때 교점 집합의 최대, 최소 범위를 갱신한다.

	void addPoint(Interpoint point) {
        points.add(point);
        
        if (points.size()==1) {
            maxX=minX=point.getX();
            maxY=minY=point.getY();
        } else {
            maxX=Math.max(maxX,point.getX());
            minX=Math.min(minX,point.getX());
            maxY=Math.max(maxY,point.getY());
            minY=Math.min(minY,point.getY());
        }
    }

마지막으로 makeGrid()로 모든 교점이 존재하는 가장 작은 크기의 격자판을 생성한다.

	String[] makeGrid() {
        String[] result = new String[(int)(maxY-minY+1)];
        int ind=0;
        
        for(long j=maxY; j>=minY; j--) {
            StringBuffer buffer = new StringBuffer();
            for(long i=minX; i<=maxX; i++) {
                if (points.contains(new Interpoint(i,j))) buffer.append('*');
                else buffer.append('.');
            }
            result[ind++] = new String(buffer);
        }

        return result;
    }