0x03강
Last updated -
2025년 06월 19일
Edit Source
3강에서는 프로그래밍 언어의 관점이 아닌 자료구조의 관점으로 배열을 학습한다.
# 배열 기본
- 그냥 끝자리에 값 쓰고 길이 1 증가시키면 되니까
- 추가된 자리 뒤의 원소들을 전부 한칸씩 밀어야해서 $O(N)$ 필요
- 지운거 뒤에것 다 땡겨와야해서 $O(N)$ 필요
# 0x01강 연습문제 O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Main {
public static int[] countArray = new int[101];
public static void main(String[] args) {
int a = func2(new int[]{1, 52, 48}, 3);
int b = func2(new int[]{50, 42}, 2);
int c = func2(new int[]{4, 13, 63, 87}, 4);
System.out.println(a + " " + b + " " + c);
}
public static int func2(int[] arr, int n) {
for (int i = 0; i < n; i++) {
if (countArray[100 - arr[i]] == 1) {
return 1;
}
countArray[arr[i]] = 1;
}
return 0;
}
}
|
# BOJ 10808 (sol)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String word = br.readLine();
char[] alphabets = word.toCharArray();
int[] countArray = new int[26];
for (int i = 0; i < alphabets.length; i++) {
countArray[alphabets[i] - 'a']++;
}
for (int i = 0; i < countArray.length; i++) {
System.out.print(countArray[i] + " ");
}
}
}
|
- 배열은 데이터를 자주 바꾸지 않고, 그냥 쌓아두고 싶을 때 활용 가능
- 인덱스에 해당하는 원소를 빠르게 접근하는 목적으로 배열을 사용하면 효과적인 문제
# BOJ 1475 (sol)
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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] countArray = new int[10];
for (char number : String.valueOf(n).toCharArray()) {
countArray[number - '0']++;
}
int maxCount = 0;
for (int i = 0; i < countArray.length; i++) {
if (i == 6 || i == 9) {
continue;
}
maxCount = Math.max(maxCount, countArray[i]);
}
int sixNineCount = (countArray[6] + countArray[9] + 1) / 2;
System.out.println(Math.max(maxCount, sixNineCount));
}
}
|
- 6이 2개, 9가 1개인 경우에는 2세트가 필요하겠지
- 단순히
(countArray[6] + countArray[9]) / 2 라고 하면 3 / 2이니까 정수라서 1이 되어버림- 그렇다고 1을 더하자니 2개, 2개인 경우 2세트면 되는데 3세트가 되어버림
- 먼저 1을 더하고 2를 나누는 아이디어
- 정수형이라서 나누면 몫만 남으니까 먼저 더하고 나누는 것도 생각 ~
# BOJ 2577 (sol)
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] countArray = new int[10];
int input = 1;
for (int i = 0; i < 3; i++) {
input *= Integer.parseInt(br.readLine());
}
char[] inputToChaArray = String.valueOf(input).toCharArray();
for (char num : inputToChaArray) {
countArray[num - '0']++;
}
for (int result : countArray) {
System.out.println(result);
}
}
}
|
# BOJ 3273 (re)
풀이
내가 틀렸던 코드
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
int x = Integer.parseInt(br.readLine());
int[] countArray = new int[x];
int result = 0;
for (int i = 0; i < n; i++) {
if (countArray[x - nums[i]] == 1) {
result++;
continue;
}
countArray[nums[i]] = 1;
}
System.out.println(result);
}
}
|
- 범위 체크 잘해야함. 안그러면 ArrayIndexOutOfBoundsException 런타임 예외 발생
- 최대 x의 크기가 하더라도 그 사이가 존재할 수 있잖아
- 예를 들어, n이 1000이고 x가 500이라 해보자.
- 그럼 countArray[음수] 형태가 되어버림!
1번 풀이 (카운트 배열)
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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1) n 입력
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
// 2) 수열 입력
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
// 3) x 입력
int x = Integer.parseInt(br.readLine());
// x 범위만큼 체크 배열 생성
boolean[] checkArray = new boolean[x + 1];
// 쌍의 개수
int count = 0;
for (int i = 0; i < n; i++) {
// x - num 이 유효 범위 내이고, 이미 등장했다면 카운트
int needed = x - nums[i];
if (needed > 0 && needed < checkArray.length && checkArray[needed]) {
count++;
}
// 현재 숫자가 등장했는지 체크
if (nums[i] < checkArray.length) {
checkArray[nums[i]] = true;
}
}
System.out.println(count);
}
}
|
2번 풀이 (투포인터)
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
43
44
45
46
47
48
49
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1) n 입력
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
// 2) 수열 입력
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
// 3) x 입력
int x = Integer.parseInt(br.readLine());
// 4) 수열 정렬
Arrays.sort(nums);
// 5) 투 포인터 설정
int left = 0;
int right = n - 1;
int count = 0; // 쌍의 개수
// 6) 투 포인터 알고리즘 수행
while (left <= right) {
int sum = nums[left] + nums[right];
if (sum == x) {
count++;
left++;
right--;
} else if (sum < x) {
left++;
} else {
right--;
}
}
System.out.println(count);
}
}
|
3번 풀이 (자료구조)
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1) n 입력
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
// 2) 수열 입력
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
// 3) x 입력
int x = Integer.parseInt(br.readLine());
// 4) HashSet 자료구조 생성
HashSet<Integer> seen = new HashSet<>();
int count = 0;
for (int num : nums) {
int needed = x - num;
// HashSet 에서 needed 이미 등장했다면 쌍 생성
if (seen.contains(needed)) {
count++;
}
// 현재 수를 seen 에 추가
seen.add(num);
}
System.out.println(count);
}
}
|
# BOJ 11328 (sol)
내 풀이
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
| public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] firstString = new String[n];
String[] secondString = new String[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
firstString[i] = st.nextToken();
secondString[i] = st.nextToken();
}
for (int i = 0; i < n; i++) {
String answer = strfry(firstString[i], secondString[i]);
System.out.println(answer);
}
}
private static String strfry(String firstString, String secondString) {
if (firstString.length() != secondString.length()) {
return "Impossible";
}
int[] appearedFirstString = new int[26];
int[] appearedSecondString = new int[26];
for (int i = 0; i < firstString.length(); i++) {
appearedFirstString[firstString.charAt(i) - 'a']++;
appearedSecondString[secondString.charAt(i) - 'a']++;
}
for (int i = 0; i < firstString.length(); i++) {
if (appearedFirstString[i] != appearedSecondString[i]) {
return "Impossible";
}
}
return "Possible";
}
}
|
등장한 횟수가 같다는건, 더하고 뺐을 때 0이라는 의미
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
43
44
45
46
| public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] firstString = new String[n];
String[] secondString = new String[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
firstString[i] = st.nextToken();
secondString[i] = st.nextToken();
}
for (int i = 0; i < n; i++) {
boolean isPossible = strfry(firstString[i], secondString[i]);
if (isPossible) {
System.out.println("Possible");
} else {
System.out.println("Impossible");
}
}
}
private static boolean strfry(String firstString, String secondString) {
int[] appearedString = new int[26];
for (int i = 0; i < firstString.length(); i++) {
appearedString[firstString.charAt(i) - 'a']++;
}
for (int i = 0; i < secondString.length(); i++) {
appearedString[secondString.charAt(i) - 'a']--;
}
boolean isPossible = true;
for (int i = 0; i < appearedString.length; i++) {
if (appearedString[i] != 0) {
isPossible = false;
}
}
return isPossible;
}
}
|
# 추가 팁
