OddOccurrencesInArray

HashMap을 이용한 문제 풀이

블로그를 만들어놨는데 한동안 포스팅이 없었다.

뭘 포스팅할지 결정하는걸 자체를 미루기도 했었지만

포스팅을 하다가도 애초에 블로그를 만들었던 목적과는 다른 포스팅이 되는것 같아

글을 쓰다가 접어버린 경우도 꽤 있었다.

알고리즘 공부를 하면서 Codility라는 사이트를 알게 됐는데

내가 작성한 문제, 코드를 다시보는 기능이 없는것 같아

앞으로 잘 안풀려서 참고했던 코드나, 풀었는데 점수가 낮았던 경우들을 포스팅할려고 한다.

OddOccurrencesInArray 는 Array lesson2에 있는 문제인데

요약해서 이해해보자면,

int []A로 된 배열에 원소들중 짝을 이루지않고있는 원소를 찾는것이다.

내 풀이 과정은 이랬다.

1.  A배열의 원소들을 비교해 같은 값을 가진 원소의 갯수를 B배열에 따로 만든다.

 - ex)  A={1,2,3,4,4,5} 이면 B배열에 원소마다 A배열의 원소가 가진 같은 원소의 갯수를 채워넣는 것이다.

2. B배열을 통해 짝이 없는 A배열의 원소 인덱스를 파악하고, 같은 인덱스의 A배열 인덱스를 반환한다.

풀이과정을 쓰려고 하니까 설명이 굉장히 어렵다 :(

import java.util.*;
 
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int[] B = new int[A.length];
        
        int count=0;
        int even = 0;
        
        for(int i =0 ; i<=A.length-1; i++)
        {
            count = 0;
            
            for(int j = 0 ; j<=B.length-1; j++)
            {
                if(A[i] == A[j] && i!=j)
                {
                    count++;
                }
            }
            B[i] = count+1; 	//A[]배열에서 A[i]와 같은 값을 가진 원소의 갯수
            
            if(B[i] == 1)
            {
                even = A[i];
            }
 
        }
        return even;
    }
}

문제를 풀어보고 다른분이 푼 풀이도 봤는데 (by speedpak)

HaspMap을 쓴 풀이 과정이 제일 깔끔하게 풀수있었던 방법이었던것 같다.

import java.util.HashMap;
import java.util.Map;
 
/**
 * @author Deepak
 *
 */
public class OddOccurrencesInArray {
 
    public static int solution(int[] A) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            if (map.containsKey(A[i])) {
                map.put(A[i], map.get(A[i]) + 1);
            } else {
                map.put(A[i], 1);
            }
        }
        Integer v = null;
        for (Map.Entry<Integer, Integer> m : map.entrySet()) {
            if (m.getValue() % 2 != 0) {
                v = m.getKey();
                break;
            }
        }
        return v;
    }
 
    public static void main(String[] args) {
        int[] ar = new int[] { 9, 3, 9, 3, 9, 7, 9 };
        System.out.println(solution(ar));
    }
}

HaspMap에 각 원소에 해당하는 갯수를 같이 put시켜놓으면 key와 value의 형태가

원소 : 갯수 이런형태로 만들어져 나머지 연산을 통해 짝이 없는 원소를 판별할수 있다.