4회차 - 알고리즘 기록 : 전화번호

📌전화번호

 용돈이 필요해진 지수는 한 설문조사 기관에서 아르바이트를 하게 되었다.

지수는 수 많은 사람들에게 전화를 통해 설문조사를 하는 일을 맡게 되었는데, 어느 날 휴식시간에 문득 사람들이 전화번호 뒷자리로 가장 많이 사용하는 번호는 무엇인지 궁금해졌다.

하지만 지수는 보유한 전화번호가 너무 많고, 전화번호의 뒷자리는 0000~9999의 총 1만가지의 종류가 있기에 눈으로 세는 것은 도저히 불가능할 것이라는 판단을 내렸다.

지수를 위하여 사람들의 전화번호 뒷자리 중 가장 많이 사용되는 번호를 찾아주자.

 

 

입력 형식

 가장 첫 줄에 전화번호의 수 N이 1이상 10만 이하의 자연수로 주어진다.

그 후 총 N줄에 걸쳐서 공백없이 4개의 자연수로 구성 된 전화번호 뒷자리가 한 줄에 하나씩 주어진다.

전화번호 뒷자리는 0000~9999사이 중 하나이다.

 

출력 형식

 주어진 전화번호 뒷자리들 중 가장 많이 등장한 번호를 출력한다

0을 포함하여 공백없는 네 자리 숫자로 출력해야한다.

단, 등장한 횟수가 같은 번호가 두 개 이상인 경우 가장 사전순으로 빠른 숫자를 출력한다.

 

예시

- 입력

3

1234

4321

1234

 

 

- 출력

1234

 

생각 풀이

 

 

1차 코드 풀이

테스트는 통과인데, 제출에서 fail 와르르르 ~~~

다시풀어봐야지 ..

 

/**
 * num  : 찾아야 하는 수
 * data : 이 배열에서
 * 
 */
public static int fillFrequencyTable(int num, int[] data, int n) {
    for( int i = 0; i < n; i++ ) {
        if(data[i] == num) {
            return i;
        }
    }
    return -1;
}

public static int getFrequentNumber(int[] data, int n) {

    int maxFind = 0;

    int[] table = new int[n];

    for( int i = 0; i < n; i++ ) {
        int find = fillFrequencyTable(data[i], data, n);
        table[find] =  table[find] + 1;

        if(table[find] > maxFind) {
            maxFind = find;
        }else if(table[find] == maxFind) {
            maxFind = data[find] > data[maxFind] ? table[find] : maxFind;
        }
    }

    return data[maxFind];
}

 

2차 코드 풀이

테스트는 통과인데, 제출에서 fail 와르르르 ~~~

다시풀어봐야지 ..

public static int fillFrequencyTable(int num, int[] data, int n) {
    for( int i = 0; i < n; i++ ) {
        if(data[i] == num) {
            return i;
        }
    }
    return -1;
}


/**
 * data[0] ~ data[n-1]사이에서 가장 많이 등장한 번호를 반환하는 함수
 * @param data
 * @param n
 * @return  가장 많이 등장한 번호. 여러개인 경우 사전순으로 가장 빠른 번호.
 */
public static int getFrequentNumber(int[] data, int n) {

    // 제일 많이 등장한 수의 인덱스를 담아.
    int maxFind = 0;

    int[] table = new int[n];

    for( int i = 0; i < n; i++ ) {

        // data 에서 내가 보낸 데이터가 있다면 index 를 반환해
        int find = fillFrequencyTable(data[i], data, n);

        // find index 값을 하나 올려줘 ! 찾았으니깐 
        table[find] = table[find] + 1;

        // 내가 지금 찾은 값이 가지고 있던 대빵 인덱스보다 크다면 너가 대빵할 차례야.
        if(table[find] > maxFind) {
            maxFind = find;
        }
    }

    // 같은 것들 중에 제일 큰거
    int realsnMax = table[maxFind];

    for(int i = 0; i < n; i++) {
        if(table[i] == realsnMax) {
            if(data[i] > data[maxFind]) {
                maxFind = i;
            }
        }
    }

    return data[maxFind];
}