[ 코테 준비 PGS ] 코딩 테스트 합격자 되기(자바 편) - Ch 5 문제 편

Ch 05. 배열

배열 제어하기

[ 문제 ]
정수 배열을 하나 받는다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution() 함수를 구현하세요.

제약 조건
- 배열 길이는 2이상 1,000 이하이다.
- 각 배열의 데이터 값은 -100,000 이상 100,000 이하이다.

 

• 입출력 예

입력	출력
[ 4, 2, 2, 1, 3, 4 ]	[ 4, 3, 2, 1 ]
[ 2, 1, 1, 3, 2, 5, 4 ]	[ 5, 4, 3, 2, 1 ]

 

• 해당 문제는 구현된 메서드를 사용하는 것이 좋다.
  • stream() 메서드를 통해 stream으로 변환한다.
  • 해당 stream의 프리미티브 타입인 IntStream의 데이터를 boxed()를 통해 레퍼런스 타입인 Integer로 변환한다.
  • distinct() 메서드를 통해 중복을 제거한다.
    • distinct() 메서드는 시간 복잡도 O(N)를 보장한다.
  • Integer형 배열로 중복 제거된 데이터를 반환한다.
• Arrays.sort() 메서드를 활용할 때 내림차순 정렬을 위해 Collections.reverseOrder()를 인수로 넘긴다.
• 인수가 없다면 기본 값은 오름차순이다.
• 마지막으로 Integer[] 형태의 배열을 int[] 형태로 변환하여 반환한다.

 

• 내가 푼 풀이

import java.util.*;

class Solution {
    public static void main(String[] args){
        // 정수 배열을 하나 받아서
        // 배열의 중복값을 제거하고 데이터를 내림차순으로 정렬해서 반환하는 solution() 함수를 구현
        // 조건 : 2이상 1000 이하
        // 데이터는 -100,000 ~ 100,000

        // ArrayList 쓰기
        // HashSet 쓰기 - 불가 sort를 하려면 새로 구현을 해야 한다.
        int[] test1 = {4, 2, 2, 1, 3, 4};
        int[] test2 = {2, 1, 1, 3, 2, 5, 4};

        System.out.println(Arrays.toString(solution(test1)));
        System.out.println(Arrays.toString(solution(test2)));
    }

    public static int[] solution(int[] arr){
        ArrayList<Integer> list = new ArrayList<>();

        for(int i = 0; i < arr.length; i++){
            if(!list.contains(arr[i])){
                list.add(arr[i]);
            }
        }

        list.sort(Comparator.reverseOrder());

        int[] answer = new int[list.size()];

        int cnt = 0;

        for(int n : list){
            answer[cnt++] = n;
        }

        return answer;
    }

}

 

• 책의 풀이

import java.util.Arrays;
import java.util.Collections;

class Solution {
    private static int[] solution(int[] arr) {
        Integer[] result = Arrays.stream(arr).boxed().distinct().toArray(Integer[]::new);
        Arrays.sort(result, Collections.reverseOrder());
        return Arrays.stream(result).mapToInt(Integer::intValue).toArray();
    }
}

 

---

🎨 자바의 스트림

• 자바에서 스트림은 데이터의 흐름이다.
• 스트림은 데이터의 소스를 추상화하고 데이터를 다루는데 유용한 메서드를 정의해 놓은 것이다.
• 다시 말해 배열 또는 컬렉션을 스트림으로 변환하면 for문 등의 반복문을 사용하지 않고도 컬렉션의 데이터를 배열에 담아서 반환하거나 특정 조건에 따라 필터링하는 등 코드의 양을 줄이고 가독성을 향상시킬 수 있다.
• 코딩 테스트 관점에서는 시간 복잡도 측면에서 for문 등의 반복문과 스트림은 성능에 큰 차이가 없다.
• 다시 말해 스트림을 쓰나 for문과 같은 반복문을 쓰나 코드의 수행 시간이 향상되지는 않는다. 따라서 스트림 사용이 익숙하지 않다면 for문과 같은 반복문을 사용해도 된다.
• 다만 앞에서 언급했듯이 효율성이 떨어지는 상황에는 가급적 표준 API를 사용해서 시간 초과가 발생하지 않도록 하는 것이 중요하다.
• 스트림을 사용해서 O(N)에 해결할 수 있는 문제를 for문과 같은 반복문으로 (O(N)으로) 해결하는 건 큰 문제가 되지 않지만 distinct() 메서드를 사용하지 않고 반복문 등을 이용하여 직접 구현한 O(N²)으로 풀면 시간 초과가 발생할 수도 있다는 뜻이다.
• disctinct() 메서드의 기능을 컬렉션 프레임워크의 Set으로 구현하는 건 코딩 테스트 관점에서 시간 복잡도가 O(N)이므로 문제가 되지 않는다.
• 만약 스트림 없이 앞에서 본 코드를 다시 구현한다면 다음과 같이 정렬과 중복 제거를 동시에 할 수 있는 TreeSet을 사용해 O(NlogN)으로 구현할 수 있다.

import java.util.Collections;
import java.util.TreeSet;

public class Solution{
    private static int[] solution(int[] arr) {
        TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
        for(int num : arr) {
        	set.add(num);
    	}

        int[] result = new int[set.size()];
        for(int i = 0; i < result.length; i++){
        	result[i] = set.pollFirst();
        }
        return result;
    }
}

 

---

두 개 뽑아서 더하기

[ 문제 ]
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution() 함수를 완성하세요.

[ 제약 조건 ]
- numbers의 길이는 2 이상 100 이하입니다.
- numbers의 모든 수는 0 이상 100 이하입니다.

 

• 입출력의 예

numbers	result
[ 2, 1, 3, 4, 1 ]	[ 2, 3, 4, 5, 6, 7 ]
[ 5, 0, 2, 7 ]	[ 2, 5, 7, 9, 12 ]

 

 

 

---

모의고사

[ 문제 ]
수포자는 수학을 포기한 사람을 줄인 표현입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.
- 1번 수포자가 찍는 방식 : 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
- 2번 수포자가 찍는 방식 : 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
- 3번 수포자가 찍는 방식 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5,...
1번 문제부터 마지막 문제까지의 정답이 순서대로 저장된 배열 answers가 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 반환하도록 solution() 함수를 작성하세요.

[ 제약 조건 ]
- 시험은 최대 10,000 문제로 구성되어 있습니다.
- 문제의 정답은 1, 2, 3, 4, 5 중 하나입니다.
- 가장 높은 점수를 받는 사람이 여럿이라면 반환하는 값을 오름차순으로 정렬하세요.

• 입출력의 예

answers	return
[ 1, 2, 3, 4, 5 ]	[ 1 ]
[1, 3, 2, 4, 2 ]	[1, 2, 3 ]

 

 

---

행렬의 곱셈

[ 문제 ]
2차원 행렬 arr1과 arr2를 입력받아 arr1에 arr2를 곱한 결과를 반환하는 solution() 함수를 완성하세요.

[ 제약 조건 ]
- 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
- 행렬 arr1, arr2의 데이터는 -10 이상 20 이하인 자연수입니다.
- 곱할 수 있는 배열만 주어집니다.

 

• 입출력의 예

arr1	arr2	return
[ [ 1, 4 ], [ 3, 2 ], [ 4, 1 ] ]	[ [ 3, 3 ], [ 3, 3 ] ]	[ [ 15, 15 ], [ 15, 15 ], [ 15, 15 ] ]
[ [ 2, 3, 2 ], [ 4, 2, 4 ], [ 3, 1, 4 ] ]	[ [ 5, 4, 3 ], [ 2, 4, 1 ], [ 3, 1, 1 ] ]	[ [ 22, 22, 11 ], [ 36, 28, 18 ], [ 29, 20, 14 ] ]

 

 

 

~ 계속 추가 예정