배열

현시기얌·2021년 12월 13일

목록 보기

2/12

배열

배열은 연속된 메모리 영역에 저장된 데이터로, 조회가 O(1), 추가 및 삭제가 O(n) 복잡도를 가지고 있다.
즉 조회는 빠르고 추가 및 삭제는 느리다.

자바에서 배열은 만들 때 크기를 정해야 하며, 추가 및 삭제 기능은 없다.

다른 자료구조를 구현하는데 사용하는 가장 기본적인 데이터 구조다.

문제 1. 중복 숫자 확인

숫자로 구성된 배열이 주어졌을 때 그 배열에 중복된 숫자가 있는지 확인하는 함수를 작성하라. 중복된 숫자가 있다면 true 없다면 false
ex) 1 2 3 4 5 6 ==> false
1 1 2 2 3 1 ==> true

솔루션1 : 가장 간단한 방법

    public boolean solution1(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] == numbers[j]) {
                    return true;
                }
            }
        }
        return false;
    }

시간복잡도 : O(n2)
공간복잡도 : O(1)

솔루션2 : 정렬 이후에 순회

 public boolean solution2(int[] numbers) {
        Arrays.sort(numbers); // O(NlogN), O(logN)
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] == numbers[i + 1]) {
                return true;
            }
        }
        return false;
    }

시간 복잡도 : O(NlogN)
공간 복잡도 : O(logN)

솔루션3 : Set을 활용하기

    public boolean solution3(int[] numbers) {
        final HashSet<Integer> numberSet = new HashSet<>();
        for (int number : numbers) {
            if (numberSet.contains(number)) {
                return true;
            }
            numberSet.add(number);
        }
        return false;
    }

시간복잡도 : O(N)
공간복잡도 : O(N)

배열 문제 2. 거꾸로 뒤집은 문자열

주어진 문자열을 거꾸로 뒤집은 문자열을 만드는 함수를 작성하라.
ex) hello = olleh
happy new year = reay wen yppah

솔루션 1. 가장 단순한 방법

    public char[] solution1(char[] message) {
        final char[] reversedMessage = new char[message.length];

        for (int i = message.length - 1; i >= 0; i--) {
            reversedMessage[message.length - 1 - i] = message[i];
        }
        
        return reversedMessage;
    }

시간복잡도 : O(N)
공간복잡도 : O(N)

솔루션 2. 공간 복잡도를 줄이는 방법

    public char[] solution2(char[] message) {
        for (int i = 0; i < message.length / 2; i++) {
            char temp = message[i];
            message[i] = message[message.length - 1 - i];
            message[message.length -1 - i] = temp;
        }
        return message;
    }

시간복잡도 : O(N)
공간복잡도 : O(1)

배열 문제 3. 인덱스 찾기

숫자로 구성된 배열 numbers와 target 숫자 하나가 주어졌을 때 numbers 배열에 들어있는 두 수를 더해 target 숫자를 만들 수 있는 인덱스 두개를 찾는 함수를 작성해라.
ex) numbers = [2,3,5,7] target = 8, 8을 만들 수 있는 인덱스인 1, 2를 리턴해야 한다.
ex) numbers = [1,2,6,8] target = 9, 9를 만들 수 있는 인덱스 0, 3을 리턴해야 한다.

솔루션 1. 가장 단순한 방법

    public int[] solution1(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

시간복잡도 : O(n2)
공간복잡도 : O(1)

솔루션 2. HashMap을 사용하는 방법

    public int[] solution2(int[] numbers, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            hashMap.put(numbers[i], i);
        }

        for (Integer key : hashMap.keySet()) {
            final int findKey = target - key;
            if (hashMap.containsKey(findKey) && !hashMap.get(findKey).equals(hashMap.get(key))) {
                return new int[]{hashMap.get(key), hashMap.get(findKey)};
            }
        }
        return null;
    }

시간복잡도 : O(N)
공간복잡도 : O(N)

배열 문제 4. 랜덤 배열 정렬

1부터 100까지의 숫자중에 50개의 랜덤한 숫자가 들어있는 배열이 있다.
이 배열을 O(N)의 시간복잡도로 정렬해라.

    public int[] solution(int[] numbers) {
        final boolean[] booleans = new boolean[100];
        for (int number : numbers) {
            booleans[number] = true;
        }

        int index = 0;
        for (int i = 0; i < booleans.length; i++) {
            if (booleans[i]) {
                numbers[index++] = i;
            }
        }
        return numbers;
    }