배열 개념
인덱스와 값을 일대일 대응해 관리하는 자료구조.
데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다.
※ 임의 접근(random access) : 집합 내의 요소의 수에 관계 없이 주소 할당이 가능 요소들로부터 임의의 시점에 임의의 데이터에 접근하는 기능
배열 선언
int[] arr = {0, 0, 0, 0, 0, 0};
int[] arr = new int[6];배열은 인덱스가 0부터 시작하므로 3번째 데이터에 접근하려면 arr[2]와 같이 접근하면 된다.
자바에는 배열과 유사한 기능을 가진 ArrayList 자료구조가 있다.
배열과 ArrayList의 차이점
배열은 처음 선언할 때 배열의 크기가 결정되고, ArrayList는 크기가 동적이다. 따라서 정확한 데이터의 개수를 알 수 있다면 코드가 더 간결하고 속도가 빠른 배열을 사용해면 되고, 저장해야 할 데이터의 개수를 정확히 알 수 없다면 ArrayList를 사용하면 된다.
배열과 차원
배열은 다차원 배열 선언이 가능하고 배열은 차원과는 무관하게 메모리에 연속 할당된다.
ArrayList 사용법
ArrayList에 데이터 추가
맨 끝 데이터를 추가하려면 add() 메서드를 사용하면 된다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
다른 컬렉션의 데이터로부터 초기화
ArrayList의 생성자의 매개변수로 컬렉션을 넘기면 매개변수로 넘긴 컬렉션에 담긴 데이터로 초기화할 수 있다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1);
list.add(2);
list.add(3);
ArrayList<Integer> list2 = new ArrayList<>(list);
System.out.println(list2); // [1, 2, 3]
get() 메서드로 인덱스를 통해 데이터에 접근
특정 인덱스에 있는 데이터에 접근하기 위해서는 get() 메서드를 사용하면 된다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1);
list.add(2);
list.add(3);
System.out.println(list.get(1)); // 2
remove() 메서드로 데이터 삭제
remove() 메서드를 사용하면 특정 위치의 데이터를 삭제할 수 있다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1);
list.add(2);
list.add(3);
list.remove(list.size() - 1); //끝에 있는 데이터 삭제
System.out.println(list); // [1, 2]다만 remove() 메서드는 데이터를 삭제하는 위치에 따라 데이터를 복사하는 연산이 필요하므로 시간 복잡도가 O(N)까지 증가할 수 있기 때문에 주의해야 한다.
배열
length 변수, Arrays 클래스의 sort() 메서드, Arrays 클래스의 toString() 메서드
ArrayList
size() 메서드(list.size()), isEmpty() 메서드(list.isEmpty()), Collections 클래스의 sort()메서드(Collections.sort(list))
배열의 시간 복잡도
임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 한번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다.
맨 뒤에 삽입하는 경우
다른 데이터 위치에 영향을 주지 않으므로, O(1)
맨 앞에 삽입하는 경우
기존 데이터들을 한 칸씩 밀어야 하므로 미는 연산이 필요하다, 데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)
중간에 삽입하는 경우
현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 한다. 따라서 O(N)
배열을 선택할 때 고려할 점
1. 할당할 수 있는 메모리 크기를 확인해야 한다. 보통 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각한다.
2. 중간에 데이터 삽입이 많은지 확인해야 한다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다.
몸풀기 문제
배열 정렬하기
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
System.out.println(Arrays.toString(solution(new int[]{1, -5, 2, 4, 3})));
System.out.println(Arrays.toString(solution(new int[]{2, 1, 1, 3, 2, 5, 4})));
System.out.println(Arrays.toString(solution(new int[]{6, 1, 7})));
}
// 이 부분을 변경해서 실행해 보기
private static int[] solution(int[] arr) {
}
}
내가 푼 코드
import java.util.Arrays;
public class ArraySortEx1 {
public static void main(String[] args) {
System.out.println(Arrays.toString(solution(new int[]{1, -5, 2, 4, 3})));
System.out.println(Arrays.toString(solution(new int[]{2, 1, 1, 3, 2, 5, 4})));
System.out.println(Arrays.toString(solution(new int[]{6, 1, 7})));
}
// 이 부분을 변경해서 실행해 보기
private static int[] solution(int[] arr) {
Arrays.sort(arr);
return arr;
}
}시간 복잡도 O(N)
배열 제어하기
package algorithm;
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public static void main(String[] args) {
System.out.println(Arrays.toString(solution(new int[]{4, 2, 2, 1, 3, 4})));
System.out.println(Arrays.toString(solution(new int[]{2, 1, 1, 3, 2, 5, 4})));
}
// 이 부분을 변경해서 실행해 보기
private static int[] solution(int[] arr) {
}
}
내가 푼 코드
import java.util.Arrays;
import java.util.Collections;
public class ArraySortEx2 {
public static void main(String[] args) {
System.out.println(Arrays.toString(solution(new int[]{4, 2, 2, 1, 3, 4})));
System.out.println(Arrays.toString(solution(new int[]{2, 1, 1, 3, 2, 5, 4})));
}
// 이 부분을 변경해서 실행해 보기
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();
}
}
이제는 프로그래머스에 있는 문제를 풀어려고 한다.
두 개 뽑아서 더하기
문제 설명
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers의 길이는 2 이상 100 이하입니다.
- numbers의 모든 수는 0 이상 100 이하입니다.
입출력 예
numbersresult[2,1,3,4,1][2,3,4,5,6,7][5,0,2,7][2,5,7,9,12]
입출력 예 설명
입출력 예 #1
- 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
- 3 = 2 + 1 입니다.
- 4 = 1 + 3 입니다.
- 5 = 1 + 4 = 2 + 3 입니다.
- 6 = 2 + 4 입니다.
- 7 = 3 + 4 입니다.
- 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.
입출력 예 #2
- 2 = 0 + 2 입니다.
- 5 = 5 + 0 입니다.
- 7 = 0 + 7 = 5 + 2 입니다.
- 9 = 2 + 7 입니다.
- 12 = 5 + 7 입니다.
- 따라서 [2,5,7,9,12] 를 return 해야 합니다.
문제 코드
class Solution {
public int[] solution(int[] numbers) {
int[] answer = {};
return answer;
}
}
문제를 읽어보면 중복된 값은 한 번만 나오도록하여 더한 값들을 오름차순으로 정렬해 return하는 것이다.
그리고 numbers의 최대 데이터 개수는 100이므로 시간 복잡도는 고려하지 않아도 된다.
이 문제는 아래와 같은 과정으로 풀 수 있다.
1. 배열에서 두 수를 선택하는 모든 경우의 수를 구한다.
2. 1번에서 구한 수를 새로운 배열에 저장하고 중복값을 제거한다.
3. 배열을 오름차순으로 정렬하고 반환한다.
자료구조 중에 Set은 중복값을 갖지 않는다는 특성을 이용해 HashSet을 이용하면 중복값을 없앨 수 있다는생각이 들어서 HashSet에 대해 찾아보았다.
Set의 특성
- Set은 비선형 구조이기 때문에 순서가 없고, 인덱스도 존재하지 않는다. 따라서 추가하거나 삭제할 때는 Set 내부에 값이 있는지 검색한 뒤, 추가 하거나 삭제해야 하므로 속도가 List에 비해 느리다.
Set은 HashSet, TreeSet 등이 있다.
HashSet과 TreeSet의 차이점을 간단히 말하자면 HashSet은 자동 정렬이 안되고 TreeSet은 자동 정렬이 된다.
Set에는 인덱스가 없기 때문에 get(index) 메서드가 없다. 따라서 Iterator를 이용해 전체 객체를 대상으로 한 번씩 반복해서 가져오기만 하면된다. ex) Iterator it = set.iterator();
HashSet을 이용해 푼 코드
import java.util.Set;
import java.util.HashSet;
class Solution {
public int[] solution(int[] numbers) {
HashSet<Integer> sumSet = new HashSet<>();
for(int i = 0; i < numbers.length - 1; i++) {
for(int j = i + 1; j < numbers.length; j++) {
sumSet.add(numbers[i] + numbers[j]);
}
}
return sumSet.stream().sorted().mapToInt(Integer::intValue).toArray();
}
}
시간 복잡도 분석
N은 numbers의 길이고 이중 반복문을 통해 모든 원소들에 대한 두 수의 합을 구했으므로 O(N²)이다.
이후 Set으로 만들 때도 마찬가지로 O(N²)이고, N²개의 데이터를 정렬하는 데는 O(N²log(N²))이므로 최종 시간 복잡도는 O(N²log(N²))이다.
List를 이용해 푼 코드
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int[] solution(int[] numbers) {
List<Integer> list = new ArrayList<>();
for(int i = 0; i < numbers.length - 1; i++) {
for(int j = i + 1; j < numbers.length; j++) {
int sum = numbers[i] + numbers[j];
if(!list.contains(sum))
list.add(numbers[i] + numbers[j]);
}
}
Collections.sort(list);
return list.stream().mapToInt(Integer::new).toArray();
}
}
- 이중 반복문: O(n²)
- List.contains(): O(k) (k는 현재 리스트 크기)
- 전체: O(n² × k)
따라서 Set을 이용하는게 List를 사용하는 것보다 시간 복잡도가 낮으므로 Set을 이용해서 푸는 게 좋은 것 같다.
모의고사
문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한 조건
- 시험은 최대 10,000 문제로 구성되어있습니다.
- 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
- 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.
입출력 예
answersreturn
| [1,2,3,4,5] | [1] |
| [1,3,2,4,2] | [1,2,3] |
입출력 예 설명
입출력 예 #1
- 수포자 1은 모든 문제를 맞혔습니다.
- 수포자 2는 모든 문제를 틀렸습니다.
- 수포자 3은 모든 문제를 틀렸습니다.
따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.
입출력 예 #2
- 모든 사람이 2문제씩을 맞췄습니다.
문제에서 가장 먼저 해야할 일
수포자들의 문제를 찍는 패턴 파악하기
이런식으로 반복되는 패턴을 찾을 수 있다.
이제 패턴을 파악했으니 각 패턴으로 문제를 풀 경우 몇 개를 맞출 수 있는지 체크하면 된다. 문제 번호에 대해 수포자의 답과 실제 답이 일치할 때마다 점수를 흭득하고, 이 점수가 가장 큰 수포자를 찾으면 된다.
만약 답이 [1, 4, 2, 4, 2]인 경우 수포자 1은 2문제, 수포자 2는 2문제, 수포자 3은 1문제를 맞추므로 가장 많이 맞춘 수포자는 1과 2이다.
만약 답안이 수포자 정답 패턴보다 길 경우, [1, 3, 5, 7, 9, 2, 4, 5]일 때 수포자 1의 정답 패턴은 [1, 2, 3, 4, 5]이므로 수포자 1의 패턴을 넘어서는 2, 4, 5는 수포자 1의 답 패턴 첫 번째부터 다시 매치해주면 된다.
가장 높은 점수를 흭득한 수포자의 번호를 반환할 때 주의할 점은 동점 조건인데, 수포자들이 얻은 점수의 최댓값을 먼저 구하고 이 점수와 일치하는 수포자의 번호를 오름차순으로 반환하면 동점 조건을 해결할 수 있다.
원래는 하드코딩은 지양하는 게 좋지만 이렇게 반복되는 패턴이 존재하는 경우에는 패턴이 변경될 가능성이 없고, 입력으로 주어지는 것이 아니라 문제의 조건이므로 하드코딩이 맞는 조건이라고 볼 수 있다.
그렇다면 언제 하드코딩을 피해야 할까?
바로 패턴이 입력으로 주어지는 경우, 패턴의 개수나 길이가 가변적인 경우, 패턴 생성 규칙이 복잡하고 일반화 가능한 경우이다.
그럼 먼저 각 수포자들의 패턴을 2차원 배열로 나열 해보겠다.
// 수포자들의 패턴
int[][] pattern = {
{1, 2, 3, 4, 5},
{2, 1, 2, 3, 2, 4, 2, 5}
{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}};
// 수포자들의 점수를 저장할 배열
int[] scores = new int[3];
이제 각 수포자들의 패턴들도 찾았으니 각 수포자의 패턴과 정답이 얼마나 일치하는지 확인하는 코드를 작성하면 된다.
// 점수 계산
for(int i = 0; i < answers.length; i++) {
for(int j = 0; j < pattern.length; j++) { // 조건문 수정
if(answers[i] == pattern[j][i % pattern[j].length]) {
scores[j]++; // j번째 수포자 점수 증가
}
}
}
그 다음 가장 높은 점수를 저장한 후 가장 높은 점수를 가진 수포자들의 번호를 찾아 리스트에 담으면 된다.
이때 Math.max() 메서드를 이용해서 가장 높은 점수를 구할 수 있다.
최종 코드
import java.util.List;
import java.util.ArrayList;
class Solution {
public int[] solution(int[] answers) {
int[][] pattern = {
{1, 2, 3, 4, 5},
{2, 1, 2, 3, 2, 4, 2, 5},
{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
};
int[] scores = new int[3];
// 점수 계산
for(int i = 0; i < answers.length; i++) {
for(int j = 0; j < pattern.length; j++) { // 조건문 수정
if(answers[i] == pattern[j][i % pattern[j].length]) {
scores[j]++; // j번째 수포자 점수 증가
}
}
}
// 최고점수 찾기
int maxScore = Math.max(Math.max(scores[0], scores[1]), scores[2]);
// 최고점수를 받은 사람들 찾기 (ArrayList 활용)
List<Integer> result = new ArrayList<>();
for(int i = 0; i < scores.length; i++) {
if(scores[i] == maxScore) {
result.add(i + 1); // 수포자 번호는 1부터 시작
}
}
// List를 배열로 변환
return result.stream().mapToInt(i -> i).toArray();
}
}
시간 복잡도
점수 계산 부분 : 외부 루프 N번, 내부 루프 항상 3번이므로 O(N x 3) = O(N)이다.
최고 점수 찾기 : O(1)
결과 리스트 생성 : 항상 3번만 반복하므로 O(3) = O(1)
배열 변환 : O(1)
최종 시간복잡도 : O(N), 정답 배열의 길이에 선형적으로 비례하기 때문.
'코딩 테스트 준비 > 개념' 카테고리의 다른 글
| 6. 해시 (4) | 2025.07.12 |
|---|---|
| 5. 큐의 개념 (0) | 2025.07.07 |
| 4. 스택 (1) | 2025.07.04 |
| 2. 알고리즘의 효율 분석 (0) | 2025.06.27 |
| 1. 코딩 테스트 준비하기 (0) | 2025.06.24 |