Ch03 - 배열
Last updated -
2024년 11월 21일
Edit Source
패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의를 정리한 내용
# 배열
- 순서(index)를 가진 데이터의 집합
- 가장 기본적인 자료구조
- 생성과 동시에 크기가 고정됨
- 전체 원소가 메모리 상에 일렬로 저장됨
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// 배열의 생성
int[] arr = new int[N];
// 배열의 저장
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
long sum = 0;
for (int i = 0; i < N; i++) {
// 배열의 탐색, 원소의 접근
sum += arr[i];
}
// 원하는 값으로 배열을 생성
int[] arr2 = {7, 9, 4, -1, 4, 10, 0, 2};
long sum2 = 0;
// 배열의 크기
int len = arr2.length;
for (int i = 0; i < len; i++) {
// 배열의 탐색, 원소의 접근
sum += arr2[i];
}
|
# 배열 시간복잡도
- 원소에 접근하거나 변경하는건 O(1)로 빠르지만, 중간에 뭘 빼거나 지우면 최대 O(N) 만큼 걸린다.
| method name | description |
|---|
get(int index) | index번째 원소 반환 |
change(int index, int val) | index번째 원소 val로 변경 |
append(int val) | 가장 뒤에 원소 삽입 |
insert(int index, int val) | 현재 index번째 원소의 앞에 원소 삽입 |
erase(int index) | index번째 원소 삭제 |
# get() 메서드
get(int index) : 시간 복잡도 O(1)
- 메모리가 연속적이기 때문에 배열의 시작 주소부터 index만큼 떨어진 원소의 주소를 바로 계산하고 접근할 수 있다.
- 예를 들어, 시작 주소가 1000번이라고 하자.
- 방 1개에 정수는 4byte이니까, 4번 원소에 접근 하려면
4 * 4로 계산해서 바로 1016번 주소로 갈 수 있다.
1
2
3
| public static int getElement(int[] arr, int index) {
return arr[index];
}
|
# change() 메서드
change(int index, int val) : 시간 복잡도 O(1)
- change(4, 100)이라고 하면 index 4번의 값을 100으로 바꾸는 것
- 마찬가지로
[] 연산자를 통해 index 번째 원소에 바로 접근하고 값을 변경할 수 있다.
1
2
3
| public static void changeElement(int[] arr, int index, int val) {
arr[index] = val;
}
|
# append() 메서드
append(int val) : 시간 복잡도 O(1)
- append(5)라고 하면 제일 뒤에 5라는 값을 추가
- 현재 배열에 담긴 원소의 개수를 알면 해당 인덱스에 요청받은 원소를 넣는다.
- 근데 만약, 배열의 크기가 10인데, 10칸에 값이 다 채워져있다고 하자. 여기에서 append로 추가하려고 하면 어떻게 될까?
- 추가되지 않는다. 배열의 크기는 고정적이기 때문이다.
- 배열이 꽉 찬 상태에서 값을 추가하려고 하면 더 큰 배열을 새로 생성하고 옮겨닮아야한다.
1
2
3
4
5
6
7
| public static boolean appendElement(int[] arr, int arrCount, int val) {
if (arrCount == arr.length)
return false;
arr[arrCount] = val;
return true;
}
|
- arrCount는 배열 안에 들어있는 원소의 개수
- 배열이 꽉 차있으면 false 반환
- 어차피 if 하나밖에 없어서 시간복잡도는 상수시간
# insert() 메서드
insert(int index, int val) : 시간 복잡도 O(N)
- insert(4, 5)라고 한다면 인덱스가 4인 원소 앞에다가 5를 추가하라는 것
- change(4, 5)는 인덱스가 4인 원소의 값을 5로 바꾸는 거라면 insert는 그 사이에 끼워넣는 것이다.
- 추가되는 원소의 뒷 원소들이 전부 한 칸씩 뒤로 밀림
1
2
3
4
5
6
7
8
| public static boolean insertElement(int[] arr, int arrCount, int index, int val) {
if (index > arrCount || arrCount >= arr.length)
return false;
for (int i = arrCount; i > index; i--)
arr[i] = arr[i - 1];
arr[index] = val;
return true;
}
|
index > arrCount는 (삽입하고자 하는 위치)가 (배열 안에 들어있는 원소의 개수)보다 큰 것을 말하는거다. 이는 연속적인 배열을 의미하는 것이 아니라 한 칸 이상 건너뛴 것을 의미- 앞에서부터 뒤로 차례대로 미는 것 말고 끝에서부터 한 칸씩 앞으로 땡기는 이유는?
- 원본값을 유지하지 못하기 때문 ! 추가된 값이 뒤로 쮸르륵 덮어씌워질거임
# erase() 메서드
erase(int index) : 시간 복잡도 O(N)
- erase(4)라고 한다면 인덱스가 4번째인 곳을 지우고 빈틈이 없게 연속적으로 뒤에서 한 칸씩 앞으로 땡겨와서 이동해야한다.
1
2
3
4
5
6
7
| public static boolean eraseElement(int[] arr, int arrCount, int index) {
if (index >= arrCount)
return false;
for (int i = index; i < arrCount; i++)
arr[i] = arr[i + 1];
return true;
}
|
# 1236번 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
char[][] input = new char[h][w];
for (int i = 0; i < h; i++)
input[i] = br.readLine().toCharArray();
int rowCount = 0;
for (int i = 0; i < h; i++) {
boolean exist = false;
for (int j = 0; j < w; j++) {
if (input[i][j] == 'X') {
exist = true;
break;
}
}
if (exist) rowCount++;
}
int colCount = 0;
for (int i = 0; i < w; i++) {
boolean exist = false;
for (int j = 0; j < h; j++) {
if (input[j][i] == 'X') {
exist = true;
break;
}
}
if (exist) colCount++;
}
int resultRow = h - rowCount;
int resultCol = w - colCount;
System.out.println(Math.max(resultRow, resultCol));
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
char[][] input = new char[r][c];
for (int i = 0; i < r; i++)
input[i] = br.readLine().toCharArray();
boolean[] existRow = new boolean[r];
boolean[] existCol = new boolean[c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (input[i][j] == 'X') {
existRow[i] = true;
existCol[j] = true;
}
}
}
int resultRowCount = r;
int resultColCount = c;
for (int i = 0; i < r; i++) {
if (existRow[i]) resultRowCount--;
}
for (int i = 0; i < c; i++) {
if (existCol[i]) resultColCount--;
}
System.out.println(Math.max(resultRowCount, resultColCount));
}
}
|
# 10431번 문제
- 일단 이 문제는 사실은 굉장히 비효율적인 정렬임. insert 하면 뒤로 하나씩 다 밀려야하니까
- 이 정렬은 삽입정렬 (insertion sort) 이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int[] input = new int[20];
for (int num = 0; num < t; num++) {
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken();
for (int i = 0; i < 20; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
int count = 0;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < i; j++) {
if (input[j] > input[i]) {
count++;
}
}
}
System.out.println((num + 1) + " " + count );
}
}
}
|
- 자신보다 먼저 줄을 선 학생 중 자신보다 키가 큰 학생이 있는지 찾음
- 자신보다 큰 학생 중 가장 앞에 있는 학생(A) 앞에 서기
- A 학생, A 뒤의 모든 학생은 한 발씩 뒤로 이동해야함
6 2 3 7 5 1 4 배열이 있다고 하자.
- 6은 그냥 서면 됨 -> count = 0
- 2보다 큰 애가 6 있네. -> count = 1
- 3보다 큰 애가 (2, 6)에서 6 있네. -> count = 1
- 7보다 큰 애가 없네. -> count = 0
- 이런식으로 0 + 1 + 1 + 0 + 2 + 5 + 3 = 12번 뒤로 가야겠네.
이런식으로 이 문제 푸는거에서 정렬은 딱히 안해도 되고 그냥 앞에서 자기보다 큰 애만 찾으면 되기는 함. 근데 정렬도 한번 해보자. 정렬 할거면 안전하게 크기의 배열 하나 만들어놓고 거기에다가 넣어보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int[] input = new int[20];
int[] sorted = new int[20];
for (int num = 0; num < t; num++) {
int count = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken();
for (int i = 0; i < 20; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < 20; i++) {
// 1. 줄 서있는 학생 중 자신보다 큰 학생 찾기
// 1-1. 찾지 못하면, 줄의 가장 뒤에 섬
boolean find = false;
for (int j = 0; j < i; j++) {
if (sorted[j] > input[i]) {
// 2. 찾았다면, 그 학생의 앞에 섬
// 3. 그 핵상과 그 뒤의 학생은 모두 1칸씩 뒤로
// 앞에서부터 값을 땡겨나가면 그 값만 복사하니까 뒤에서부터 동작하자
find = true;
for (int k = i - 1; k >= j; k--) {
sorted[k + 1] = sorted[k];
count++;
}
sorted[j] = input[i];
break;
}
}
if (!find) sorted[i] = input[i];
}
System.out.println((num + 1) + " " + count);
}
}
}
|
# 15552번 문제 (버퍼)
- Java의 경우 Scanner와 System.out.println은 매우 느린편이다.
- N의 개수가 1,000,000 정도만 넘어가더라도 입출력이 반복되는 경우가 발생할 수 있어서 느리다.
- 따라서, BufferedReader와 BufferedWriter를 사용하도록 하자.
백준 입력 속도 비교
BufferedReader, Integer.parseInt => 0.6585(s)Scanner => 4.8448(s)
백준 출력 속도 비교
BufferedWriter, bf.write(i + "\n"); => 0.9581(s)StringBuilder를 이용해 문자열 하나로 만든 다음, System.out.println(sb); => 1.1881(s)BufferedWriter, bf.write(Integer.toString(i)); bf.newLine(); => 1.2556(s)PrintWriter => 1.954(s)System.out.println(i); => 30.013(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int sum = a + b;
bw.write(sum + "\n");
}
bw.close();
}
}
|
bw.write()는 스트림에 쓰기만 할 뿐 출력이 되는 것이 아니다!- 출력하려면 반드시
bw.flush()로 내보내거나 bw.close()로 스트림을 닫아줘야한다. bw.write()로 버퍼에 작성할 때는 "\n"로 개행문자 넣어줘야함
# 10989번 문제
- 내가 푼 방법은
Arrays.sort() 이용 - 맞기는 맞았는데,
Arrays.sort()나 삽입정렬는 시간복잡도가 최악의 경우 O(n2)이다.- 문제에서 N(10,000,000)개의 자연수 [1, 10000]이라고 했기때문에 아마 통과한 것 같지만, 자연수 범위가 없었다면..? 틀렸을 것
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int num = Integer.parseInt(br.readLine());
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for (int i = 0; i < num; i++) {
bw.write(arr[i] + "\n");
}
bw.flush();
}
}
|
영단어 알파벳 문제에서 풀었던 것처럼 카운트 배열 이용
- 대신 이 방법은 한계가 있다.
- 만약 자연수가 10억까지 들어올 수 있다고 하면 10억 1칸 짜리 배열을 만들어놔야하잖아
1,000,000,000 * 4byte = 4,000MB = 4GB 공간복잡도 개높음!- 숫자의 범위가 커지면 카운트 배열이 힘들고, 숫자로 나타낼 수 없는 배열이면 나타내기 힘들잖아.
- 번외로 정수 범위가 [-100, 100]은 가능하다.
cnt[100 + x]로 기록하면 되니까.
1
2
3
4
5
6
7
8
9
10
11
12
| int[] cnt = new int[10001];
// O(N)
for (int i = 0; i < N; i++) {
cnt[sc.nextInt()]++;
}
// O(max(10000, N))
for (int i = 1; i <= 10000; i++) {
while(cnt[i]-- > 0) {
System.out.println(i);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));
int N = Integer.parseInt(br.readLine());
int[] cnt = new int[10001];
for (int i = 0; i < N; i++) {
cnt[Integer.parseInt(br.readLine())]++;
}
for (int i = 1; i <= 10000; i++) {
while (cnt[i]-- > 0) {
bw.write(i + "\n");
}
}
bw.flush();
}
}
|
# 3273번 문제
- 시간복잡도 생각해보면 이중반복문 안됨
- 카운트배열 써보자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(br.readLine());
int[] input = new int[n];
for (int i = 0; i < n; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
int[] cnt = new int[1000001];
for (int i = 0; i < n; i++) {
cnt[input[i]]++;
}
int ans = 0;
for (int i = 0; i < n; i++) {
int pair = x - input[i];
if (0 <= pair && pair <= 1000000)
if (cnt[pair] == 1) {
ans++;
}
}
bw.write(ans / 2 + "\n");
bw.flush();
}
}
|
반복문 도는 부분을 X 부분까지만 돌아보자. 두 수의 합이니까 X보다 큰거까진 돌 필요 없지
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(br.readLine());
int[] input = new int[n];
for (int i = 0; i < n; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
int[] cnt = new int[1000001];
for (int i = 0; i < n; i++) {
cnt[input[i]]++;
}
int ans = 0;
for (int i = 1; i <= (x - 1) / 2; i++) {
if (i <= 1000000 && x - i <= 1000000)
if (cnt[i] == 1 && cnt[x-i] == 1)
ans++;
}
bw.write(ans + "\n");
bw.flush();
}
}
|
- x에서 1을 빼준건, x가 홀수라면 딱 정 가운데지만 x가 짝수라면 정 가운데가 아니니까 -1 해줬음
- 여기서 2를 미리 나눠주면 밑에 ans는 2를 안나눠도 되겠네