230112 TIL (n진법 변환, H-Index)

알고리즘

3진법 뒤집기

코딩테스트 연습 - 3진법 뒤집기

프로그래머스

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

GitHub - jk891113/java-algorithm

해당 문제는 3진법으로 변환하는 것을 몰라 처음부터 막혔다. 3진법 변환을 모르면 풀지 못하는 문제기 때문에 구글로 검색을 먼저 해보았다.

10진수 → n진수 변환

int num = 10;
Integer.toBinaryString(num); // 2진수 변환
Integer.toString(num, n); // n진수 변환

toString의 두번째 파라미터를 변환하고 싶은 진법 수로 입력하면 10진수인 num을 변환하고 싶은 진수로 변환해 준다.

n진수 → 10진수 변환

String num = 1111;
Integer.parseInt(num, n); // 10진수 변환

parseInt의 두번째 파라미터를 10진수로 변환하고 싶은 진법을 입력하면 10진수의 int 값으로 변환해 준다.

나의 풀이

위에서 알아본 10진수를 n진수로 변환하는 코드를 사용하여 3진수로 변환하고 해당 String 값을 저번에 사용한 subString을 사용하여 뒤에서 부터 한 글자씩 잘라서 넣어주려 하였으나 이번에는 다른 방법인 charAt을 사용하여 뒤에서 부터 반복문을 돌려 맨 뒤의 문자를 하나씩 flip에 넣어주는 작업을 진행하고 다시 10진수로 변환하는 코드를 사용해 10진수로 변환해 주었다.

public int solution(int n) {
    int answer = 0;
    String ter = Integer.toString(n, 3);
    String flip = "";
    for (int i = ter.length() - 1; i >= 0; i--) {
        flip += ter.charAt(i);
    }
    answer = Integer.parseInt(flip, 3);
    return answer;
}

이번 문제는 3진수로 변환하고 다시 10진수로 변환하는 것이 주 목적이었는데, 변환하는 방법을 몰라 혼자 풀었다고 생각이 들지 않는다. 다만, 그동안 2진수로 변환하는 tobinaryString만 알고 있었지만, toString을 사용하여 파라미터 값으로 다양한 진수로 변환할 수 있다는 것을 알게 되었다.

다른 사람의 풀이

public int solution(int n) {
    String a = "";

    while(n > 0){
        a = (n % 3) + a;
        n /= 3;
    }
    a = new StringBuilder(a).reverse().toString();

    return Integer.parseInt(a,3);
}

다른 사람의 풀이를 보았는데 해당 반복문을 정수 값을 Integer.toString을 사용하지 않고 String 타입으로 변환할 때 3이 아닌 10을 사용해서 작성했던 코드를 본 적 있고, 위의 코드에서 배울게 많은 듯 하여 가져와 보았다.

또 문자열을 뒤집는 방법으로 StringBuilder를 사용하여 reverse 메소드로 뒤집는 방법을 사용한 것을 처음 보았기에 다음에 사용할 수 있도록 배워 놓는 것이 좋을듯 하다.

위의 코드에서 n % 3을 하면 맨 뒤의 글자가 추출이 되는데 위의 코드에서는 맨뒤의 숫자를 추출하고 넣어준 a를 뒤에 붙임으로써 while문이 끝나고 나면 올바른 순서로 String a가 완성이 되는데 (n % 3) + a의 순서를 바꿔서 a + (n % 3)으로 작성을 해주면 while문이 끝나면 뒤집어진 순서로 String a가 완성이 되므로 아래의 한줄을 작성하지 않을 수 있다.

public int solution(int n) {
    String a = "";

    while(n > 0){
        a = a + (n % 3);
        n /= 3;
    }

    return Integer.parseInt(a,3);
}

이번 기회에 10진수에만 적용할 수 있을 줄 알았던 방법을 다양한 진수에 적용할 수 있다는 것을 알았고, StringBuilder를 사용해 문자열을 뒤집을 수 있다는 것도 알았다.

---

H-Index

코딩테스트 연습 - H-Index

프로그래머스

이번 문제는 동료 수강생이 풀다가 헤매서 한번 풀어보라고 알려주어서 풀어보게 되었다. 문제설명을 이해하기 어려웠고, 실제로 H-Index를 과학계에서는 사용하는 것 같았다. 해당 문제 아래에 H-Index에 관한 위키백과 링크도 있어서 문제 설명을 이해하기 어려우면 들어가서 읽어보라는 조언이 있었기에 들어가 보았더니 ‘출판물의 생산성과 인용 영향력을 모두 측정하는 저자수준의 지표’ 라고 한다.

나의 풀이

일단 문제 설명만 보고는 ‘h번 이상 인용’된 논문이 ‘h편 이상’ 이라는 문구와 테스트 케이스의 3번 이상 인용, 3편 이상 이라는 결과에서 논문 수와 인용 수가 같아야 하는 구나 라고 생각이 들어서 for문을 이중으로 돌리고 i는 논문 수, j는 인용 수로 하여 둘이 비교해서 인용 수와 논문 수가 같은 수를 구해서 answer로 리턴 해주었다.

public int solution(int[] citations) {
    int answer = 0;
    for (int i = 0; i < citations.length + 1; i++) {
        int count = 0;
        for (int j = 0; j < citations.length; j++) {
            if (i <= citations[j]) count++;
        }
        if (i == count) answer = i;
    }
    return answer;
}

하지만, 두개의 테스트를 통과하지 못했고, 위키 백과의 정보를 읽어보는데 계산하는 방법은 복잡한 산식 때문에 이해하기 힘들었고, 그래프를 보니 정확히 일치하지 않고, 논문 수보다 인용된 수가 더 많아도 된다는 사실을 알게 되었다.

public int solution(int[] citations) {
    int answer = 0;
    for (int i = 0; i < citations.length + 1; i++) {
        int count = 0;
        for (int j = 0; j < citations.length; j++) {
            if (i <= citations[j]) count++;
        }
        if (i <= count) answer = i;
    }
    return answer;
}

등호를 부등호로 바꾸어주니 해결이 되었다. 고득점을 받기는 하였지만, 문제에서 원하는 방식으로 풀었다는 생각이 들지 않아서 다른 사람의 코드를 찾아보았다.

다른 사람의 풀이

문제가 정렬 카테고리에 있는 만큼 정렬을 사용한 코드를 가져와 보았다.

public int solution(int[] citations) {
    int answer = 0;
    Arrays.sort(citations);
    for (int i = 0; i < citations.length; i++) {
        int smaller = Math.min(citations[i], citations.length - i);
        answer = Math.max(answer, smaller);
    }
    return answer;
}

해당 코드는 citations 배열을 정렬하여 [6, 5, 3, 1, 0] 으로 만들고 citations.length - i 로 5, 4, 3, 2, 1을 각각 반복하며 비교하여 작은 값을 smaller에 넣어주고 answer를 큰 값으로 갱신하는 작업을 하는 것으로 보여진다.

위의 방법이 ‘h개의 논문이 각각 적어도 h개의 인용을 갖도록 하는 가장 큰 숫자 h’ 라는 위키 백과의 H-Index 정의와 맞는 것 같다.

---