230113 TIL (소수찾기, 리팩토링)

알고리즘

소수 찾기

코딩테스트 연습 - 소수 찾기

프로그래머스

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

GitHub - jk891113/java-algorithm

오늘 제시된 문제는 소수 찾기였는데, 문제가 생각보다 간단한 것 같았는데 효율성 테스트가 추가되어 생각처럼 되지 않았다.

나의 풀이

소수는 1과 자기 자신으로만 나눠지는 수이고, 1은 소수가 아니며 일정한 규칙은 없는 듯 하였다. 그래서 2 이상의 숫자를 1부터 자기자신의 수까지 하나하나 나눠보고 나눠 떨어진 횟수를 카운트 해서 해당 카운트가 2가 되면 answer에 소수를 카운트하는 방식으로 코드를 구현하였다.

public int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) count++;
        }
        if (count == 2) answer++;
    }
    return answer;
}

굉장히 빠르게 작성하였고, 테스트 케이스 2개를 통과하였기 때문에 빠른 시간 안에 문제를 해결했다고 생각을 했지만, 제출하였더니 마지막 세개의 테스트에서 시간초과로 통과하지 못했고, 효율성 테스트에서 통과하지 못했다. 이중 반복문을 사용했고 n의 범위가 100만 이하이기 때문에 하나하나 일일이 나눠보는 방법은 효율이 좋지 않아 사용하지 못하는 듯 하다.

다른 방법을 고민하던 중 도저히 이중 반복문 이외의 방법이 떠오르지 않아서 질문하기에 다른 사람이 올려 놓은 글을 읽어 보았는데 불필요한 계산을 줄여 시간을 단축하는 ‘에라토스테네스의 체’ 라는 소수를 찾는 방법이 있다는 것을 알게 되었다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위키백과의 내용을 토대로 삼아 2의 배수부터 n의 배수까지 맨 처음 수만 소수로 골라내고 나머지는 고려 대상에서 제거하여 다음 반복문 부터는 연산해야 하는 양을 줄여나가는 방식으로 코드를 작성하였다.

public int solution(int n) {
    int answer = 0;
    int[] arr = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        arr[i] = i;
    }

    arr[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (arr[i] == 0) continue;
        for (int j = i * 2; j <= n; j += i) {
            arr[j] = 0;
        }
    }

    for (int a : arr) {
        if (a != 0) answer++;
    }
    return answer;
}

배열을 만들어서 0번 인덱스부터 n번 인덱스까지 인덱스와 n까지의 모든 숫자를 동일하게 넣어준 뒤, 1은 소수가 아니므로 값을 0으로 바꿔주고, 2부터 반복하면서 처음 나온 수는 소수로 남겨두고, 그 배수들은 소수가 될 수 없으므로 0으로 바꿔준다. 다음 반복문부터 0이 된 숫자는 고려하지 않고, 0이 아닌 수는 앞의 숫자의 배수에 해당하지 않으므로 소수가 되며 그 배수들은 소수가 아니므로 0으로 바꿔준다. 마지막엔 배열에서 0이 아닌 원소의 수만 카운트 해서 반환한다.

위의 방법은 이중 반복문을 사용하였지만, 연산할 양을 줄여서 효율성 테스트에서 통과하였다. 다른 사람의 풀이를 보았는데 예전에는 효율성 테스트가 없어서 처음 작성했던 코드도 정답 코드로 올라와 있는 것을 확인할 수 있었다. 위의 에라토스테네스의 체를 Boolean 리스트를 사용하여 구현한 코드도 있었고, 이중 반복문을 다르게 사용한 사람도 있었다.

다른 사람의 풀이

그 중 처음 시도했던 방식과 비슷하게 배열에 담지 않고 소수를 찾는 방식으로 보이는 코드를 가져와 보았다.

public int solution(int n) {
    int answer = 0;
    for(int i = 2; i <= n; i++){
        int j = 2;
        int cnt = 0;
        while(j <= (int)Math.sqrt(i)){
            if(i % j == 0){
                cnt += 1;
                break;
            }
            j += 1;
        }
        if(cnt == 0) answer += 1;
    }
    return answer;
}

내가 작성했던 방식과 다른 점은 이중 반복문 중 하나는 while문으로 작성을 하였는데 그 안에 Math.sqrt를 사용한 것이었다. 검색해보니 제곱근(루트)을 구하는 메소드라고 한다.

코드만 보고 도저히 이해가 되지 않아서 제곱근으로 소수를 구하는 방법을 찾아보았다.

소수인지 판별 할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나게 됩니다. 따라서 소수인지 판별할때는 그 자연수의 제곱근 이하의 수까지만 검사를 하면 됩니다. 검사할 데이터를 제곱근 개 이하로 줄일 수 있습니다.

출처 : 소수를 판별하는 방법, 제곱근 나누기 [JavaScript]

소수를 판별하는 방법, 제곱근 나누기 [JavaScript]

위의 글을 인용해 보아 소수를 구할 때 소수를 구할 대상 자연수의 제곱근 이하의 수들로만 나눠보고 나눠지면 소수가 아닌 것으로, 나눠지지 않으면 소수인 것으로 판별하고 제곱근 이상의 수들로는 고려하지 않아도 된다는 뜻인 것 같다.

이 방법을 사용하면 처음 내가 작성한 대상 수까지의 모든 수를 연산하는 방법보다 제곱근 이하의 수만 연산하므로 확실히 연산량은 줄어드는 것 같다.

제곱근과 비교하는 수 j를 2로 설정한 이유는 제곱근이 2보다 작으면 1로만 나눠보면 된다는 뜻이고, 이는 1과 나 자신으로만 나눠진다는 뜻과 같으므로 소수이다. 따라서 i가 2인 경우 j가 i의 제곱근보다 크므로 while문으로 진입하지 않고 cnt가 0이므로 소수 카운트 answer를 하나 올린다. i가 3인 경우도 같다.

i가 4인 경우에는 j와 i의 제곱근이 같으므로 while문으로 진입하고 4는 2로 나누어 떨어지므로 cnt를 1 올리고 j도 1이 올라가 3이되고 while문 탈출, answer는 올라가지 않게 된다. 여기서 j를 올려주는 것은 while문 탈출 용도로 사용한다는 것을 알 수 있다.

이렇게 n까지의 모든 수를 2부터 n의 제곱근까지의 수로 n을 나눠보며 나누어 떨어지면 cnt가 1이 되어 answer를 올리지 않고, 나누어 떨어지지 않으면 cnt가 0이 되어 answer에 소수 카운트가 올라가게 된다.

 

오늘은 그저 다 나눠봐야 알 수 있다고 생각했던 소수를 찾는 두가지 방법에 대해 알 수 있었다. 코드를 작성할 때 소수를 찾는 일이 있을지는 모르겠지만, 여태까지는 그저 이중 반복문을 사용하더라도 원하는 결과만 도출할 수 있으면 된다는 생각을 했었지만, 오늘을 계기로 효율성에 대한 고찰과 효율성을 높이기 위해 연산량을 최대한 줄이는 방안을 생각할 수 있는 계기가 되었던 것 같다.

---

개인과제 리팩토링

게시글 삭제시 해당 게시글의 댓글 삭제 기능 추가

Post와 Comment의 연관관계를 설정하지 않는 방식으로 리팩토링을 했었기 때문에 게시글을 삭제할 때 연관관계가 있을 때는 @OneToMany에 CascadeType.DELETE로 해당 게시글에 Join 되어있는 댓글들을 자동으로 삭제해 주었는데 @OneToMany 연관관계는 정말 필요하지 않은 이상 맺지 말라는 튜터님의 말을 듣고 연관관계를 설정하지 않고, 해당 게시글을 삭제하는 메소드에 댓글을 삭제하는 코드를 추가하여 직접 삭제해 주었다.

@Transactional
public void deletePostingAdmin(Long postId) {
    postRepository.findById(postId).orElseThrow(
            () -> new IllegalArgumentException("존재하지 않는 포스팅입니다.")
    );
    postRepository.deleteById(postId);
    commentRepository.deleteByPostId(postId);
}

게시글 삭제시 해당 게시글의 댓글 수만큼 쿼리가 날라가는 문제

게시글 삭제시 해당 게시글의 댓글들이 잘 삭제되는지 테스트를 해보는데 게시글의 댓글의 수만큼의 쿼리가 날라가는 것을 확인 할 수 있었다.

내가 예상했던 것은 comment가 가지고 있는 postId의 값을 사용해서 delete 쿼리를 날리기 때문에 쿼리는 하나만 날라가고 DB에서 해당 PostId 값을 가진 comment 데이터를 삭제하는 것을 예상했지만, 쿼리가 댓글 갯수 만큼 날라가는 것을 보고 이러면 @OneToMany 대신에 사용할 이유가 없는 것 같아서 튜터님한테 질문하고 In 절을 사용한 Delete도 시도해보고 하였지만, 댓글 갯수만큼 쿼리를 날리는 것을 해결하지 못하였다.

그러던 중 동료 수강생이 @ManyToOne의 연관관계에도 @OnDelete 어노테이션을 사용하여 연관관계에 있는 데이터를 삭제할 수 있다는 얘기를 듣고 해당 어노테이션은 JPA Level이 아닌 DB Level에서 데이터를 삭제하기 때문에 쿼리가 날라가지 않을 것 같다는 말에 한번 테스트를 해보았다.

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

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

@Column(nullable = false)
private String comment;

@Column(name = "PARENT_ID", nullable = false)
private Long parentId = 0L;

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

@ManyToOne
@JoinColumn(name = "POST_ID", nullable = false)
@OnDelete(action = OnDeleteAction.CASCADE)
private Post post;

Comment 엔티티에서 postId를 없애주고 @ManyToOne으로 Post와 연관관계를 맺어주고 @OnDelete를 사용해 Post가 삭제되면 해당 Comment도 삭제되는 코드를 추가해주었다. 이후 PostId와 관련이 있는 에러가 뜨는 코드들을 조금씩 수정해주고 테스트를 진행해 보았다.

댓글을 삭제하기 위한 Delete 쿼리가 comment에는 아예 안 날라가는 것을 확인할 수 있었다.

데이터베이스에도 Comment가 남아있지 않고 삭제된 것을 확인할 수 있었다.

아직 이해가 확실히 되지 않았기 때문에 OnDelete를 검색해보고 공부하면서 JPA Level과 DB Level에서의 데이터 핸들링의 차이점에 대해 공부 해보도록 해야겠다.

---