https://blog.encrypted.gg/927 을 보고
https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x03.md 의 문제들을 풀어봤습니다
배열
자료구조로서의 배열
: 메모리 상에 원소를 연속하게 배치한 구조. 자료구조로서의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다.
배열의 성질
- O(1)으로 원소 접근, 변경 가능 → O(n)으로 전체를 탐색하던 부분을 줄이는데 활용
- 연결리스트처럼 추가적으로 소모되는 부분 없이, 그냥 데이터만 저장
- 연속된 구조 → 히트 높음
- 연속된 구조 → 할당에 제약
배열의 기능, 구현
- 임의의 원소 접근 / 마지막에 삽입, 제거 = O(1)
- 임의의 위치에 원소 삽입, 제거 = O(N)
- 뒤에 있는 원소들 전부 움직여야 하기 때문
배열 전체 초기화 방식
- for문 사용 : 정직하게 for로 하나하나 직접 값 넣어주기
- Arrays.fill 사용
- 전체 초기화
- 일부분만 초기화 : 인덱스 지정
Vector
- 배열과 비슷하지만 크기를 바꿀 수 있는 구조
- 접근, 마지막 원소 삽입, 삭제는 동일하게 O(1)
벡터 : 삽입
- 특정 위치에 삽입 : 뒤쪽의 원소들 한 칸씩 미루고 삽입 → O(n)
- 맨 뒤에 삽입 : O(1)
- 삽입이 아니라 set : O(1) : 특정 위치의 원소를 set(덮어씀)
벡터 : 삭제
- 특정 위치의 원소 삭제 : 뒤쪽의 원소들 한 칸씩 당김 → O(n)
- 특정 원소 삭제 : 위치기반X, 일치하는 원소를 삭제한다. 가장 첫 번째로 나타나는 거 (낮은 idx)부터
벡터 : =
- 깊은복사 : 참조값을 넘기는게 아니라, 값을 복사하는 deep copy가 발생하므로 O(n)임을 주의
0x01 - 연습문제2
- 기존의 풀이 : 배열의 각 원소마다 다른 위치에 합이 100이 되는 원소 있는지 확인 : 이중for문 → O(n^2)
- int[100] arr을 활용 : 배열에 접근해 값을 바꾸는 건 O(1)임을 활용
- int[100]을 배열에 해당 값이 존재했음을 표시하는데 사용
- 배열의 각 원소 x, arr[x] - arr[100-x] 가 둘 다 존재하면 1 반환
우와 짱이다
BOJ 10808
https://www.acmicpc.net/problem/10808
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P10808 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int[] alphabet = new int[26];
int idx=0;
for(int i=0;i<s.length();i++) {
idx = s.charAt(i)-'a';
alphabet[idx]++;
}
for(int i : alphabet) {
System.out.print(i+" ");
}
}
}- 각 알파벳 포함 개수를 저장할 배열 "int[26] alphabet"을 사용
알아야 하는 점
- 아스키코드
0 : 48 / A : 65 / a : 97 정도만 알고있기
- a - 0 / b - 1 / c - 2 / ... 로 인덱스로 저장하므로 char - 'a' 활용한 점
BOJ 2577
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P2577 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int result = Integer.parseInt(br.readLine())*Integer.parseInt(br.readLine())*Integer.parseInt(br.readLine());
String resultStr = String.valueOf(result);
int[] numbers = new int[10];
for(int i=0;i<resultStr.length();i++) {
numbers[resultStr.charAt(i)-'0']++;
}
for(int i : numbers) {
System.out.println(i);
}
}
}- 위 문제와 매우 유사
- 각 숫자 포함 개수를 저장할 배열 int[10] numbers 사용
- 아스키 코드 : 마찬가지 맥락으로 char 형태의 숫자 -> int 숫자로 바꿀 땐 : char -'0'
BOJ 1475 : 방번호
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P1475 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int result=0; int max=0; double hap=0;
String num = br.readLine();
int[] arr = new int[10];
for(int i=0;i<num.length();i++) {
arr[num.charAt(i)-'0']++;
}
for(int i =0 ; i<10 ; i++) {
if(max<arr[i] && i!=6 && i!=9 ) {max = arr[i];}
if(i==6 || i==9) {hap+=arr[i];}
}
hap = (Math.ceil(hap/2.0));
if(hap<max) {System.out.println(max);}
else {System.out.println((int)hap);}
}
}- 숫자 포함 개수를 저장하는 int[10] arr 사용
- arr에서 최대값이 답
- 6, 9는 공용 : 6, 9는 평균의 올림 값을 최대값 비교대상으로
알아야 하는 점
- 올림 : Math.ceil(실수형)
BOJ 3273 : 두 수의 합
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class P3273 {
public static void main(String[] args) throws IOException {
int cnt=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strArr = br.readLine().split(" "); int[] arr = new int[n];
int x = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++) {
arr[i] = Integer.parseInt(strArr[i]);
}
Arrays.sort(arr);
int start = 0; int end = n-1;
while(start<end) {
int sum = arr[start]+arr[end];
if(sum==x) {cnt++; start++;}
else if(sum<x) {start++;}
else if(sum>x) {end--;}
}
System.out.println(cnt);
}
}
- 틀린 풀이1
: 연습문제 2번의 첫 시도와 같이 이중for문을 활용한 경우 : O(n^2)라서 시간초과
: 그냥 해 봤음ㅎㅎ
- 틀린 풀이2
: 연습문제 2번에서 활용했던 방식을 똑같이 적용해서import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class P3273 { public static void main(String[] args) throws IOException { int cnt=0; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int[] arr = new int[n]; int x = Integer.parseInt(br.readLine()); for(int i=0;i<n;i++) { arr[i] = Integer.parseInt(strArr[i]); } int[] arrs = new int[1000000]; for(int i=0;i<n;i++) { arrs[arr[i]]++; if(arr[i]>=x) {continue;} if(arrs[x-arr[i]]==1) {cnt++;} } System.out.println(cnt); } }
- 1000000짜리 배열에 숫자 등장여부 표시
- x-arr[i] 가 존재하면 cnt++
하는 방식으로 시도해봤지만 반례가 있었다- 데이터 추가한 사람의 이름이 익숙해서 봤더니 이 시리즈 집필하신 분이다. 함정에 걸렸나보다 ㅋㅋ
1 1 2 / 1 2 4 와 같이
arr[i]*2 = x이며 원소가 1개인 경우가 반례이다
" arrs[x-arr[i]]==1 " 이 부분에서 자기 자신이므로 걸려버림
- 맞은 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class P3273 {
public static void main(String[] args) throws IOException {
int cnt=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strArr = br.readLine().split(" "); int[] arr = new int[n];
int x = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++) {
arr[i] = Integer.parseInt(strArr[i]);
}
Arrays.sort(arr);
int start = 0; int end = n-1;
while(start<end) {
int sum = arr[start]+arr[end];
if(sum==x) {cnt++; start++;}
else if(sum<x) {start++;}
else if(sum>x) {end--;}
}
System.out.println(cnt);
}
}-
몰랐던 점들
1. 투 포인터 알고리즘 활용
- 배열에서 각자 다른 위치를 가리키는 2 개의 포인터를 조작해가며 탐색하는 방식
- "정렬된 리스트"를 두 개의 포인터를 이용해 순차적으로 접근 : 두 포인터 값의 조작 - 타겟값 같아질 때까지 포인터 이동시켜 가며 탐색
-
예시
- start + end = target : count++, start++
- start + end < target : start++
- start + end > target : end--
매 루프마다 두 포인터 중 한 번씩 움직임, start, end는 N까지 증가
-
연속된 두 값 - target을 찾을 경우 : start - end를 같은 곳에서 시작, 둘 다 증가시키는 방식, start<=end
-
연속될 필요 없이, 배열에서 특정 두 원소의 조작 - target을 찾는 경우 : 위와 같이 start - end를 따로, while(start<end) 동안
-
!!! 정렬된 배열 !!!
2. 배열의 정렬 : Array.sort() : O(nlogn) ~ O(n^2)
https://laugh4mile.tistory.com/175
BOJ 10807 : 개수 세기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P10807 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int cnt=0;
String[] strArr = br.readLine().split(" ");
int v = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++) {
arr[i] = Integer.parseInt(strArr[i]);
}
for(int i=0;i<n;i++) {
if(arr[i]==v) {cnt++;}
}
System.out.println(cnt);
}
}BOJ 13300 : 방배정
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Vector;
public class P13300 {
public static void main(String[] args) throws IOException {
int rooms=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
String[] stdStr = new String[2];
int n = Integer.parseInt(str[0]); int k = Integer.parseInt(str[1]);
int[] students = new int[12];
for(int i=0;i<n;i++) {
stdStr = br.readLine().split(" ");
if(stdStr[0].equals("0")) {
students[Integer.parseInt(stdStr[1])*2-2]++; }
else {students[Integer.parseInt(stdStr[1])*2-1]++;}
}
for(int i=0;i<12;i++) {
if(students[i]==0) {continue;}
rooms+=(int)Math.ceil((double)students[i]/(double)k);
}
System.out.println(rooms);
}
}- 방을 따로 써야 하는 요인 : 학년+성별
- 학년-성별에 따른 인원수를 저장하는 배열 students 사용
: 1학년 여자(0,1) : idx 0 (12-2) / 1학년 남자(1,1) : idx 1 (1*2-1) / 2학년 여자(0,2) : idx 2 (21-2) / ... - 각 학년-성별에 따른 (인원수/수용인원)의 올림(Math.ceil)값들을 더함
BOJ 11328 : strfry
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Vector;
public class P11328 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] alphabet1 = new int[26];
int[] alphabet2 = new int[26];
String[] result = new String[n];
Vector<String> str = new Vector<>();
for(int i=0;i<n;i++) {
String[] inStr = br.readLine().split(" ");
str.add(inStr[0]); str.add(inStr[1]);
}
for(int i=1;i<=n;i++) {
String s1 = str.get(i*2-2); String s2 = str.get(i*2-1);
for(int j=0;j<s1.length();j++) {
alphabet1[s1.charAt(j)-'a']++;
}
for(int j=0;j<s2.length();j++) {
alphabet2[s2.charAt(j)-'a']++;
}
if(Arrays.equals(alphabet1,alphabet2)) {
result[i-1]="Possible";
} else {
result[i-1]="Impossible";
}
alphabet1=new int[26]; alphabet2 = new int[26];
}
for(String resStr : result) {
System.out.println(resStr);
}
}
}- 한 벡터에 입력받은 문자열 전부 저장
- 한 줄 입력마다 벡터에 두 개씩 저장되므로 str.get(i2-2)은 원본문자열 / str.get(i2-1)은 비교문자열
- 원본문자열, 비교문자열의 알파벳 사용현황을 저장하는 배열 alphabet1, 2에 각각 루프돌며 저장
- alphabet1 - alphabet2 : 동일하면 Possible
알아야 했던 점
- 배열의 비교
- Arrays.equals(arr1, arr2) : arr의 값들을 비교
- arr1.equals(arr2) : 값의 비교가 아닌, 정말 동일한 객체인지 비교
