230111 TIL (대댓글 기능, 유클리드 호제법)

알고리즘

최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수

프로그래머스

java-algorithm/Solution.java at main · jk891113/java-algorithm

GitHub - jk891113/java-algorithm

오늘의 알고리즘 제시 문제는 최대공약수와 최소공배수였다. 예전에 한번 분수의 덧셈을 풀어보려다가 최소공배수가 필요할 것 같아서 최소공배수를 찾아본 결과 최대공약수가 있어야 최소공배수를 구할 수 있고 최대공약수는 유클리드 호제법으로 구하는 코드를 작성해야 한다는 것을 알게 되었었다.

유클리드 호제법 (최대공약수)

• 자연수 a, b가 있을 때, a를 b로 나눈 나머지 값이 r이라 하면 a와 b의 최대공약수와 b와 r의 최대공약수는 같다.
• a % b = r, b % r = r’, r % r’ = c 이런식으로 a와 b를 나눈 나머지 값으로 나누는데 사용한 수를 계속 나눈다.
• 나머지가 0이 되면 마지막 계산에서 나눈 수가 최대공약수가 된다
• 예시
  • 1112와 695의 최대공약수 계산

1112 % 695 = 417
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0

• 나머지가 0이 되는 계산에서 나눈 수 139가 최대공약수가 된다.

최소공배수

• 최대공약수만 있으면 간단하다 두 값을 곱한 값에 최대공약수로 나누면 최소공배수가 된다.
• a * b / 최대공약수 = 최소공배수
• 예시
  • 1112와 695의 최소공배수 계산

1112 * 695 / 139 = 5560

나의 풀이

반복해서 나눠줘야 하므로 for문 아니면 재귀를 사용해야 할 것 같았다. 처음에는 for문을 시도해 보았으나 for문으로 구현하기는 복잡하고 코드가 길어질 것 같아서 메소드를 정의하여 재귀로 구현해 보았다.

public static int gcd(int n, int m) {
    if (m % n == 0) return n;
    else return gcd(m % n, n);
}

주어진 정수 n과 m중에 테스트 코드에서는 m이 큰 수인 것 같아서 일단 비교하여 더 큰 수를 찾는 코드는 작성하지 않고 큰 수를 작은 수로 나눠 나머지 값이 0이면 나눈 수를 반환하고 0이 아닌 경우에는 나눈 수를 큰 수에 넣고 나눈 나머지 값을 작은 수에 넣어서 해당 메소드를 다시 호출하는 재귀를 구현하였다.

테스트 케이스에 주어진 수로 테스트 해 본 결과 최대공약수가 잘 출력되는 것을 확인하고 최소공배수도 구현해 보았다. 최대공약수 보다 훨씬 간단하다. 주어진 두개의 수를 곱하고 최대공약수로 나눠주었다.

public int[] solution(int n, int m) {
    int[] answer = new int[2];
    int gcd = gcd(n, m);
    int lcm = n * m / gcd;
    answer[0] = gcd;
    answer[1] = lcm;
    return answer;
}

최소공배수가 산식 자체는 간단하지만 최소공배수만 구하라는 문제가 나와도 최대공약수를 전처리 작업으로 구해야 하기 때문에 최소공배수가 간단한 문제 같지는 않다. 이번 기회에 저번에 찾아만 보고 구현해보지 않은 유클리드 호제법을 직접 구현해 보면서 확실하게 알게 되었다. for문으로 구현하는 것도 한번 시도해 봐야겠다.

다른 사람의 풀이

다른 사람의 풀이를 보다가 for문으로 직관적이고 간결하게 보이는 코드를 가져왔다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        for (int i = 1; i < n + m; i++) {
            if (n % i == 0 && m % i == 0) {
                answer[0] = i;
                answer[1] = n * m / answer[0];
            }
        }
        return answer;
    }
}

1부터 n + m까지의 수를 반복하는데 둘 중 더 작은 수인 n까지만 반복해도 될 것 같다. 아무튼 1부터 반복하며 n와 m에 나눠보고 둘다 0이되면 최대공약수 자리에 넣어주고 최소공배수도 계산하고 넣어준다. 이 방법은 계속 수가 올라가면서 최대공약수가 갱신되는 방법인 것 같다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        for (int i = n; i > 0; i--) {
            if (n % i == 0 && m % i == 0) {
                answer[0] = i;
                break;
        }
        answer[1] = n * m / answer[0];
        return answer;
    }
}

둘 중 작은 수는 그 작은 수까지로만 나눌 수 있으므로 n + m을 n으로 바꾸었고, 최대공약수는 작은 수부터 반복해서 갱신하는 것 보다 큰 수부터 반대로 반복하며 성공하면 break로 빠져 나가는 것이 효율적으로 보여서 바꿔보았다.

for문 vs 재귀

제시된 수의 크기가 작으면 for문이 직관적이고 간결하여 좀 더 나은 것 같은데 위의 유클리드 호제법 예시처럼 큰 수나 문제에서 제시되는 수는 100만 이하이므로 100만에 육박하는 수를 일일이 반복하는 것은 비효율적이고 유클리드 호제법을 재귀 방식으로 푸는 것이 조금 더 시간을 줄일 수 있을 것 같다.

예를 들어 998765와 676915의 최대공약수를 구한다고 하면 for문 방식으로는 작은 수인 676915에서 최대공약수인 5까지 약 676910번을 반복해야 하지만 유클리드 호제법의 재귀함수는 아래와 같이 12번만 반복하면 결과를 찾을 수 있다.

998765 % 676915 = 321850
676915 % 321850 = 33215
321850 % 33215 = 22915
33215 % 22915 = 10300
22915 % 10300 = 2315
10300 % 2315 = 1040
2315 % 1040 = 235
1040 % 235 = 100
235 % 100 = 35
100 % 35 = 30
35 % 30 = 5
30 % 5 = 0

---

개인과제 리팩토링

개인과제 리팩토링을 진행하며 팀프로젝트에서 내가 맡았던 카테고리 기능을 추가하였고, 다른 팀원이 맡았던 대댓글 기능을 추가해 보았다.

대댓글 기능 구현

대댓글 기능을 추가하면서 고민한 점은 팀프로젝트에서 다른 팀원이 진행한 방식대로 대댓글 엔티티를 따로 만들고 컨트롤러와 서비스도 따로 분리하여야 하는지 여부를 고민하였다. 저번에 구현했던 카테고리 기능과 비슷해 보였는데 카테고리 기능은 상위 카테고리와 하위 카테고리 엔티티를 따로 분리하지 않았기 때문에 댓글도 최상위 댓글과 대댓글들을 분리하지 않고 하나의 엔티티에서 parentId 값을 주어 대댓글 자신의 부모 댓글을 구분지어 주었다.

@Id
@GeneratedValue(strategy = GenerationType.AUTO)
private Long id;

@Column(name = "username", nullable = false)
private String username;

@Column(nullable = false)
private String comment;

private Long parentId = 0L;

@Column(name = "POST_ID", nullable = false)
private Long postId;

기존에 있던 CommentController 클래스에 createChildrenComment 메소드를 추가하였다.

@PostMapping("/posts/{postId}/comments/{parentId}")
public CommentResponseDto createChildrenComment(@PathVariable Long postId,
                                                @PathVariable Long parentId,
                                                @RequestBody CommentRequestDto requestDto,
                                                @AuthenticationPrincipal UserDetails userDetails) {
    return commentService.createChildrenComment(postId, parentId, requestDto, userDetails.getUsername());
}

기존에 있던 CommentService 클래스에도 createChildrenComment 메소드를 추가해준다.

public CommentResponseDto createChildrenComment(Long postId, Long parentId, CommentRequestDto requestDto, String username) {
    Comment parentComment = commentRepository.findById(parentId).orElseThrow(
            () -> new IllegalArgumentException("해당 댓글이 존재하지 않습니다.")
    );
    Comment comment = new Comment(requestDto, username, postId, parentId);
    commentRepository.save(comment);
    return new CommentResponseDto(comment);
}

기존 댓글 작성 메소드에서 엔티티를 생성할 때는 requestDto, username, postId만 넣었었는데, 대댓글에는 parentId를 추가해주고, 그 값으로 해당 대댓글이 따라 다니는 댓글의 Id 값을 넣어준다.

대댓글 조회에 대하여 고민하였는데, 기존 게시글 조회에 댓글이 따라오는 것처럼 댓글 아래에 대댓글들도 따라와서 조회가 가능하게 할까 생각해 보았지만 그렇게 하면 기본적으로 삼중 반복문이 필요하고 대댓글 아래 대대댓글을 구현하면 사중 반복문, 그 이상의 대댓글들의 계층이 생긴다면 n중 반복문이 되어 시간복잡도가 기하급수적으로 늘어날 수 있을 거 같아서 게시글 조회시에는 최상위 댓글들만 조회하고 그 댓글들의 대댓글 조회를 선택했을 때 대댓글들을 조회하는 방식으로 작성해 보았다.

publicList<CommentResponseDto> getChildrenCommentList(Long commentId) {
    Comment parentComment = commentRepository.findById(commentId).orElseThrow(
            () -> new IllegalArgumentException("해당 댓글이 존재하지 않습니다.")
    );
List<Comment> childrenCommentList = commentRepository.getAllByParentIdOrderByModifiedAtDesc(commentId);
List<CommentResponseDto> responseDtoList = childrenCommentList.stream()
            .map(comment -> new CommentResponseDto(comment))
            .collect(Collectors.toList());
    return responseDtoList;
}

게시글 조회시 대댓글이 댓글 리스트에 보여지는 문제

게시글을 조회했을 때 댓글, 대댓글 구분없이 모든 댓글이 해당 게시글 아래 댓글 리스트에 보여지는 문제가 발생하였다. 이유는 대댓글도 게시글의 PostId 값을 가지고 있어서였다.

해당 문제의 해결 방법은 두가지가 있을 것을 보여진다.

• 대댓글을 생성할 때 PostId의 값을 넣어주지 않는 방법
• 카테고리처럼 댓글과 대댓글의 layer 값을 주어 계층을 나누어서 게시글 조회시에 layer 값이 0인 댓글들만 조회하는 방법

두가지 방법을 고민한 결과 게시글 조회시에 댓글들의 계층을 나누어서 전체 댓글을 조회하지 않을 것이기 때문에 계층을 나눌 필요가 없다고 판단을 하고, 게시글 조회시 해당 게시글의 PostId 값을 가진 댓글들이 함께 조회되므로, 대댓글을 생성할 때 PostId의 값을 넣어주지 않는 방법을 선택하여 게시글 조회시에 해당 게시글에 대댓글이 딸려오지 않는 방법으로 진행하려고 하였으나,

튜터님에게 질문하여 피드백을 받고 대댓글에도 PostId를 필수적으로 가지고 있어야 한다는 의견을 듣고 생각해보니 게시글 삭제할 때 대댓글도 함께 삭제가 되어야 하기 때문에 위의 방법으로 하지 않고 아래의 방법을 고려해보고 아래의 방법대로 진행하였다.

• 게시글을 조회할 때 댓글의 PostId 값과 게시글의 Id 값을 비교하는 조건문에 ParentId가 0인지 확인하는 조건 추가하는 방법

PostResponseDto 클래스에 게시글 조회시 같이 조회되는 댓글의 리스트를 만드는 생성자 내의 조건문에 ParentId를 확인하는 조건을 추가해준다.

public PostResponseDto(Post post, List<Comment> commentList) {
    this.createdAt = post.getCreatedAt();
    this.modifiedAt = post.getModifiedAt();
    this.id = post.getId();
    this.categoryId = post.getCategoryId();
    this.title = post.getTitle();
    this.username = post.getUser().getUsername();
    this.contents = post.getContents();
List<CommentResponseDto> commentResponseDtoList = new ArrayList<>();
    for (Comment comment : commentList) {
        if (Objects.equals(comment.getPostId(), post.getId()) && comment.getParentId() == 0)
            commentResponseDtoList.add(new CommentResponseDto(comment));
    }
    this.commentList = commentResponseDtoList;
}

 

게시글을 조회할 때 대댓글이 같이 조회되는 문제가 해결 되었다.

댓글과 대댓글의 엔티티를 하나로 구현해도 되는지 여부의 고민

댓글 객체에서는 id, username, comment, postId의 필드를 사용하고, 대댓글 객체에서는 id, username, comment, postId, parentId 필드를 사용하므로, 댓글 객체에서는 parentId가 필요하지 않은 필드의 데이터가 된다. 이 때문에 댓글 엔티티와 대댓글 엔티티를 따로 구현해야 되는지를 튜터님께 질문해 보았는데, 만약 댓글과 대댓글의 기능의 차이가 있다면 따로 구현하여야 하는게 타당해 보이고, 기능의 차이가 없다면 지금처럼 구현하는 것이 타당하고 미사용 필드의 유무는 크게 상관이 없는 듯 했다.

대댓글을 댓글의 엔티티를 상속받아서 자식 엔티티로 구현 해보는 것도 좋은 경험이 될 것 같지만, 지금은 머릿속으로만 생각해보고 나중에 꼭 필요한 시점에 상속하여 엔티티를 구현해보자.

---