230210 TIL (알고리즘, 프로젝트)

알고리즘

멀쩡한 사각형

코딩테스트 연습 - 멀쩡한 사각형

프로그래머스

나의 풀이

정말 쉽지 않은 문제였다. 가로와 세로 길이의 제한이 1억까지 였고, 사각형을 대각선 방향으로 2등분 할때의 직선이 가로지르는 직선이 지나가는 사각형 내의 가로 세로 길이가 1인 정사각형의 갯수를 구하는 문제였다.

문제에 주어진 예시 그림을 보고 사각형 내에 점선에 닿는 최소 크기의 사각형이 존재한다는 사실까지는 알아냈다. 최소 사각형은 주어진 사각형과 가로 길이와 세로 길이의 비율이 같아야 해서 가로 길이와 세로길이의 최대공약수가 사각형 내의 최소 사각형의 갯수가 되게 된다. 최소 사각형의 갯수와 가로세로 길이는 구할 수 있었지만, 대각선이 지나가는 정사각형의 갯수를 구하는 방법이 생각이 나지 않아서 문제를 해결하지 못하고 있었다.

동료 수강생과 같이 문제를 풀었는데, 대각선이 지나가는 정사각형의 갯수에 일정한 패턴이 존재한다는 것을 알게 되었다. 가로 세로 길이와 선이 지나가는 정사각형의 갯수를 몇가지 케이스를 가지고 생각을 해보았더니 (가로길이 + 세로길이 -1) = 정사각형 갯수 라는 패턴을 금방 알 수 있었다.

class Solution {
    public int GCD(int max, int min) {
    int i = max % min;
    if (i == 0) return min;
    return GCD(min, i);
  }

  public long solution(int w, int h) {
    int max = Math.max(w, h);
    int min = Math.min(w, h);
    int GCD = GCD(max, min);
    int minRectangleW = w / GCD;
    int minRectangleH = h / GCD;
    return (long) w * h - (long) (minRectangleW + minRectangleH - 1) * GCD;
  }
}

최대공약수는 재귀함수를 사용하여 유클리드 호제법으로 구하는 방법을 사용하였다.

다른 사람의 풀이

다른 사람의 풀이를 보다가 풀이 방식은 같지만, 최대공약수를 구하는 함수가 BigInteger라는 클래스에 있다는 사실을 알게 되어서 퍼오게 되었다.

import java.math.BigInteger;

public class Solution {

    public long solution(int w, int h) {
        long totalCount = (long) w * (long) h;
        long diagonalCount = w + h - BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).longValue();

        return totalCount - diagonalCount;
    }
}

math에 BigInteger라는 클래스가 있다는 사실을 처음 알게 되었다. 속도를 비교해보니 재귀함수로 직접 구현하는 것보다는 느린 것 같지만, BigInteger 클래스를 찾아보며 long 타입에 사용할 수 있는 유용한 함수가 있는지 한번 찾아 보아야겠다.

---

프로젝트

이번 프로젝트는 한 주마다 기술 멘토링 노트를 작성하고 튜터님에게 피드백을 받는 방식으로 진행 되는데, 피드백을 통해 지적받은 문제점들을 수정하였다.

어제 하다가 중단한 역할 분배에 대하여 심층적으로 논의해 보았다. 도메인별로 분류하기로 정했고, 어제 질문을 통해 알게된 Boundary Context를 통해 우리 서비스의 핵심 도메인을 분류해 보았다. 판매자의 음식점과 관련한 기능들이 있을 것이고, 판매자가 줄서기(웨이팅)을 하는 것과 관련된 줄서기 기능과 줄서기 후 작성하는 리뷰기능, 이벤트를 개최하여 쿠폰을 발급하는 기능, 유저의 회원가입이나 로그인 등 회원정보 관리 기능, 총 4가지(Restaurant, Lineup, Event, User) 로 분류를 하였다.

한눈에 보아도 Restaurant의 기능이 거대해 보여서 팀원이 5명이기에 Restaurant에 2명의 책임자를 배치하고 나머지 도메인 별로 1명의 책임자를 배치하기로 하였다. 그동안 해보지 않았고, 재미있을 것 같은 event와 lineup 도메인에 팀원들이 몰렸고, 나도 그 중 하나였지만 나머지 기능들도 재미있을 것 같아서 Restaurant의 책임자 중 한명을 하기로 하였다.

Service 단에서는 인터페이스를 사용하기로 하였고, 데이터 조회처럼 빈번히 이뤄지는 것은 메소드를 따로 작성하여 중복 코드를 방지하고, 하나의 서비스에서 다른 서비스의 데이터 조회를 사용하는 것에 대한 논의를 하였다. 여러 방법이 도마 위에 올랐지만, 데이터 조회하는 메소드들만 따로 인터페이스를 만들어서 하나의 ServiceImpl에 두개의 인터페이스를 다중 구현하는 방법을 채택하였다.

모든 회의를 마치고 드디어 본격적으로 코드를 작성하기 시작하였는데, 저녁늦게 시작하여 오늘은 각각 맡은 도메인에 필요한 entity와 repository만 작성하기로 하고 다음 주부터 본격적으로 시작하기로 하였다.

---