자료 구조의 대한 배열
순서(indx)를 가진 데이터의 집합
- 가장 기본적인 자료구조
- 생성과 동시에 크기가 고정됨
- 전체 원소가 메모리상에 일렬로 저장됨
배열에 대한 아래 기능들의 시간복잡도는?
- get(int indx) : idx번재 원소 반환
메모리가 연속적이기 때문에 arr의 시작 주소로부터 idx만큼 떨어진 원소의 주소를 바로 계산하고, 접근할 수 있다. 시간 복잡도 : O(1)
- change(int idx int val) : idx번째 원소를 val로 변경
[] 연산자를 통해 idx번 원소에 바로 접근하고, 값을 변경할 수 있다.
시간 복잡도: O(1)
-append(int val) : 가장 뒤에 원소 삽입
현재 배열에 담긴 원소의 개수를 알면 해당 인덱스에 요청받은 원소를 넣는다.
그러나 배열이 꽉 차 있다면? -> 한번 생성된 배열은 고정 길이이다. 그래서 삽입 불가 남은 자리가 있어야 추가가 가능
시간 복잡도 O(1)
-
insert(int idx, int val) : 현재 idx번째 원소의 앞에 원소 삽입
배열의 중간에 원소를 추가 한칸 씩 뒤로 이동 시간복잡도 : O(N) N은 원소의 개수
-
erase(ind idx) : idx번째 원소 삭제
해당 원소의 뒷 원소들이 모두 한칸씩 앞으로 이동 시간 복잡도 : O(N)
원소에 접근하고 변경하는 것은 빠르나,
중간 원소를 추가/ 삭제하는 것은 최대 원소의 개수까지 시간이 걸린다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N]; // 배열의 생성
int[] array = {7, 9, 4, -1, 4, 5, 10, 0, 2, 5, 6}; //원하는 값으로 배열 생성
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt(); // 배열의 저장
}
long sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[i]; // 배열의 탐색, 원소의 접근근 }
}문제 : [1236] 성 지키기
- 각 행/열에 대해 경비원이 있는지 확인한다.
- 보호받지 못하는 행/열의 개수를 구한다.
- 둘 중 큰 값을 출력한다.
import java.util.*;
class Main {
// 성 지키기 직사각형 모양의 성을 가지고 있다
// 모든 행과 모든 열에 한명 이상의 경비원이 있으면 좋겠다.
// 성의 크기와 경비원이 어디있는지 주어졌을때, 몇명의 경비원을 최소로 추가
// 컬럼이랑 로우가 겹치지 않게
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
char[][] map = new char[N][M];
for (int i = 0; i < N; i++)
map[i] = sc.next().toCharArray();
// 1. 각 행/열에 대해 경비원이 있는지 확인한다.
boolean[] existRow = new boolean[N];
boolean[] existCol = new boolean[M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(map[i][j] == 'X'){
existRow[i] = true;
existCol[j] = true;
}
}
}
// 2. 보호받지 못하는 행/열의 개수를 구한다.
int needRowCount = N;
int needColCount = M;
for (int i = 0; i < N; i++) {
if(existRow[i]) needRowCount--;
}
for (int i = 0; i < M; i++) {
if(existCol[i]) needColCount--;
}
// 3. 둘 중 큰 값을 출력한다.
System.out.println(Math.max(needRowCount, needColCount));
}
}문제 : [10431] 줄세우기
입력으로 주어진 순서대로 규칙에 따라 줄을 설 때 각 학생들이 뒤로 물러난 걸음 수의 총합
- 자신보다 먼저 줄을 선 학생 중 자신보다 키가 큰 학생이 있는지 찾는다.
1-1. 자신보다 큰 학생이 없다면 줄의 가장 뒤로 가서 선다.- 자신보다 큰 학생 중 가장 앞에 있는 학생 (A) 앞에 선다.
- A와 A 뒤의 모든 학생들은 공간을 만들기 위해 한 발 씩 뒤로 물러난다
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int P = sc.nextInt();
while (P-- > 0){
int T = sc.nextInt();
int[] h = new int[20];
for (int i = 0; i < 20; i++)
h[i] = sc.nextInt();
int cnt = 0;
int[] sorted = new int[20];
for (int i = 0; i < 20; i++) {
//1. 줄 서있는 학생 중 자신보다 큰 학생을 찾는다.
//1-1. 찾지 못했다면, 줄의 가장 뒤에 선다.
boolean find = false;
for (int j = 0; j < i; j++)
if(sorted[j] > h[i]){
//2. 찾았다면, 그 학생 앞에 선다.
//3. 그 학생과 그 뒤의 학생 모두 한칸씩 뒤로 물러난다.
find = true;
for (int k = i - 1; k >= j ; k--) {
sorted[k + 1] = sorted[k];
cnt++;
}
sorted[j] = h[i];
break;
}
if(!find) sorted[i] = h[i];
}
System.out.println(T + " " + cnt);
}
}
}문제3 : [10989] 수 정렬하기 3
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] cnt = new int[10001];
for (int i = 0; i <N ; i++) {
cnt[sc.nextInt()]++;
}
for (int i = 0; i < 10000; i++) {
while (cnt[i] -- > 0){
System.out.println(i);
}
}
}
}백만 단위 이상은 버퍼 함수로 사용하는 것이 낫다.
import java.io.*;
import java.util.*;
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] 두 수의 합
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++)
a[i] = sc.nextInt();
int X = sc.nextInt();
boolean[] exist =new boolean[1000001];
for (int i = 0; i < N; i++)
exist[a[i]] = true;
int ans = 0;
for (int i = 1; i <= ( X - 1) /2 ; i++) {
if(i <= 1000000 && X - i <=1000000)
ans += (exist[i] && exist[X-i]) ? 1 : 0;
}
// for (int i = 0; i < N; i++) {
// int pairValue = X - a[i];
// if(0 <= pairValue && pairValue <=1000000)
// ans += exist[pairValue] ? 1 : 0;
// }
System.out.println(ans);
}
}
짧고 강력하게!