이코테 책 알고리즘 연습
큰 수의 법칙(92p)
내 코드
public class BigNumber {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
int K = s.nextInt();
s.nextLine();
Integer[] nums = new Integer[N];
for (int i = 0; i < nums.length; i++) {
nums[i] = s.nextInt();
}
Arrays.sort(nums, Collections.reverseOrder());
int result = 0;
for(int i = 0; i < M; i++){
for(int j = 0; j < K; j++){
result += nums[0];
}
result += nums[1];
M = M - K;
continue;
}
System.out.println(result);
}
}M이 10,000 이하이기 때문에 이 방식도 괜찮지만, M의 크기가 커지면 시간 초과 판정을 받을 것이다.
간단한 수학적 사고방식으로 더 효율적으로 풀 수 있다.
반복되는 수열에 대해 파악
- 반복되는 수열의 길이 : K + 1
- 수열이 반복되는 횟수 : M / (K+1)
수열이 반복되는 횟수에 K를 곱하면 가장 큰 수가 나타나는 횟수가 된다.
but, M이 K+1로 나누어떨어지지 않는 경우에는 그 나머지도 가장 큰 수 가 나타나는 횟수에 더해줘야 한다.
- 가장 큰 수가 나타나는 횟수 : M / (K+1) * K + M % (K + 1)
→ 나중에 이 문제를 풀때 과연 이게 내 머리속에서 떠오를 수 있을까 ㅋㅋㅋ
- 나동빈님 풀이
public class BigNumber2 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
int K = s.nextInt();
s.nextLine();
int[] nums = new int[N];
for (int i = 0; i < nums.length; i++) {
nums[i] = s.nextInt();
}
Arrays.sort(nums);
int first = nums[N - 1]; // 가장 큰 수
int second = nums[N - 2]; // 두번째로 큰 수
// 가장 큰 수가 더해지는 횟수 구하기
int count = M / (K + 1) * K;
count += M % (K + 1);
int result = 0;
result += first * count; // 가장 큰 수 더하기
result += second * (M - count); // 두번째로 큰 수 더하기
System.out.println(result);
}
}숫자 카드 게임(96p)
처음에 문제가 이해 안갔다가 곰곰히 생각해보니 문제가 이해갔다.
내 코드
public class NumCardGame1 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
int[][] arr = new int[N][M];
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
arr[i][j] = s.nextInt();
}
}
// 행 별로 가장 낮은 숫자를 담은 배열
int[] NArr = new int[N];
for(int i = 0; i < N; i++){
int[] newArr = new int[M];
for(int j = 0; j < M; j++){
// 각 행을 담은 배열
newArr[j] = arr[i][j];
}
// 가장 낮은 숫자를 담아준다.
Arrays.sort(newArr);
NArr[i] = newArr[0];
}
Arrays.sort(NArr);
System.out.println(NArr[NArr.length-1]);
}
}-
나동빈님 풀이
입력 조건에서 입력으로 들어오는 수는 모두 10,000이하 이다.
각 행에서 가장 작은수를 찾고, 그 수 중에서 가장 큰수를 찾기
Math.min()메서드 활용
public class NumCardGame2 { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); int result = 0; for(int i = 0; i < n; i++){ // 해당 행에서 가장 작은 수 찾기 int min_value = 1001; // 입력 조건에서 입력 범위 10,000이하 for(int j = 0; j < m; j++){ int x = s.nextInt(); min_value = Math.min(min_value,x); } // 가장 작은 수 들 중에서 가장 큰 수 찾기 result = Math.max(result, min_value); } } }-
result = Math.max(result, min_value);
- 이부분을 한참 생각했다.
- 처음에 행이 바뀔때마다 (i 값이 증가될 때마다) result 값도 바뀌는 것을 생각 못했다.
- 나중에 풀 때 내 머리로 이 코드가 과연 나올수 있을까 ㅋㅋㅋ
-
내가 짠 코드보다 훨씬 간결하다. 내 풀이처럼 굳이 여러 배열을 생성해서 담을 필요가 없다..
-
1이 될 때까지 (99p)
예시코드를 봤는데 내가 푼 방법도 나쁘지 않은것 같아서 예시코드는 정리 안함
public class Greedy4_1 {
// 내 풀이
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int k = s.nextInt();
int count = 0;
while(n > 1){
if(n % k == 0){
n = n / k;
} else n--;
count++;
}
System.out.println(count);
}
}자바의 정석 11장 컬렉션 프레임웍 학습
컬렉션 프레임웍(Collections Framework) (578p)
컬렉션(다수의 데이터)을 다루는데 필요한 클래스들을 제공
컬렉션 프레임웍의 핵심 인터페이스
- List
- 순서가 있음, 데이터 중복 허용
- ex) waiting list
- 구현 클래스 : ArrayList, LinkedList, Stack, Vector 등
- Set
- 순서가 없음, 데이터 중복 허용하지 않음
- ex) 집합(소수의 집합, 정수 집합 등)
- 구현 클래스 : HashSet, TreeSet 등
- Map
- 키(key)와 값(value)의 쌍으로 이루어짐
- 순서 없음, 키는 중복을 허용하지 않고, 값은 중복 허용
- ex) 지역번호(서울-02, 인천-032)
- 구현 클래스 : HashMap, TreeMap 등
Collection 인터페이스의 메서드(580p)
-
추가
-
boolean add(Object o)
-
boolean addAll(Collection c)
: 객체 o나 컬렉션 c의 객체들을 추가
-
-
삭제
-
void clear()
: Collection의 모든 객체 삭제
-
boolean remove(Object o)
-
boolean removeAll(Collection c)
: 지정된 객체 o나 컬렉션 c에 포함된 객체 삭제
-
-
검색
-
boolean contains(Object o)
-
boolean containsAll(Collection c)
: 지정된 객체 o나 컬렉션 c의 객체들이 Collection에 포함되어 있는지 확인
-
이외의 메서드들은 필요하면 580p에서 확인하기
-
List 인터페이스(581p)
중복 허용, 저장순서 유지
List 인터페이스의 메서드
-
추가
-
void add(int index, Object element)
: 지정된 위치에 객체 추가
-
boolean add(int index, Collection c)
: 지정된 위치에 컬렉션에 포함된 객체 추가
-
-
검색
-
int indexOf(Object o)
: 지정된 객체의 위치 반환
-
int lastIndexOf(Object o)
: 역순으로 탐색해서 위치 반환
-
-
삭제
-
Object remove(int index)
: 인덱스에 위치한 객체 삭제하고, 삭제된 객체 반환
-
-
정렬
-
void sort(Comparator c)
: List 정렬
-
-
일부추출
-
List subList(int fromIndex, int toIndex)
: 지정된 범위에 있는 객체 반환
-
-
반환
- Object get(int index)
-
저장
-
Object set(int index, Object element)
: index위치에 element 저장
-
Set 인터페이스
중복 허용 안함, 저장순서 유지 안됨
HashSet, TreeSet
Map 인터페이스 (582p)
순서 없음, 키 중복 허용 안함, 값 중복 허용
HashMap, LinkedHashMap(순서가 있는 HashMap), TreeMap
Map 인터페이스의 메서드
-
추가
- Object put(Object key, Object value)
- void putAll(Map t)
-
삭제
-
Object remove(Object key)
: key 와 일치하는 key-value 삭제
-
void clear()
: Map의 모든 객체 삭제
-
-
읽기
-
Set entrySet()
: key, value 읽기
-
Set keySet()
: key만 읽기
-
Collection values()
: value만 읽기
-
-
검색
- boolean containsKey(Object key)
- boolean containsValue(Object value)
- Object get(Object key)
-
크기
- int size()
-
비교
- boolean equals(Object o)
- boolean isEmpty()
ArrayList
List 인터페이스를 구현한 클래스
기존 Vector를 개선한 것, ArrayList와 달리 Vector는 자체적으로 동기화 처리가 되어있다.
데이터 저장공간으로 배열 사용
ArrayList의 소스코드를 보면 Object 배열을 멤버변수로 선언하고 있어서 모든 종류의 객체를 담을 수 있다. (객체만 가능)
→ ArrayList에 int 값을 넣을 때 list.add(3); 이라고 해도 되지만,
기본형인 int 3을 컴파일러가 자동으로 autoboxing 해주어 참조형으로 변환된다.
원래는 list.add(new Integer(3)); 이라고 해준다.
(ArrayList에 객체만 저장 가능)
- ArrayList의 생성자와 메서드는 584p
- 예제
public class ArrayListEx1 {
public static void main(String[] args) {
ArrayList list1 = new ArrayList(10);
list1.add(new Integer(5));
list1.add(new Integer(4));
list1.add(new Integer(2));
list1.add(new Integer(0));
list1.add(new Integer(1));
list1.add(new Integer(3));
// list1의 인덱스 1부터 4이전까지 요소 추출해서 새로운 ArrayList 생성
ArrayList list2 = new ArrayList(list1.subList(1, 4));
print(list1, list2);
Collections.sort(list1); // 오름차순 정렬
Collections.sort(list2);
System.out.println("sorted list");
print(list1, list2);
System.out.println("list1.containsAll(list2) : " + list1.containsAll(list2));
System.out.println();
list2.add("B");
list2.add("C");
list2.add(3, "A");
System.out.println("after adding elements");
print(list1,list2);
list2.set(3, "AA");
System.out.println("notice the difference by using set method");
print(list1,list2);
// list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제한다.
System.out.println("list1.retainAll(list2) : " + list1.retainAll(list2));
print(list1,list2);
// list2에서 list1에 포함된 객체들을 삭제한다.
for(int i = list2.size() -1; i >= 0; i--){
if(list1.contains(list2.get(i))) list2.remove(i);
}
System.out.println("after removing duplicate elements");
print(list1,list2);
}
static void print(ArrayList list1, ArrayList list2) {
System.out.println("list1 : " + list1);
System.out.println("list2 : " + list2);
System.out.println();
}
}- Collections.sort(list);
- 오름차순 정렬
- list1.retainAll(list2);
- list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제
- retain : 유지하다, 보유하다
- for문으로 list2에서 list1에 포함된 객체 삭제할 때
- i를 증가하면서 삭제하면 요소들의 자리이동이 나타나서 비효율적이고, 모든 요소를 삭제하지 못하는 올바르지 않은 결과가 나온다.
- 맨 뒤의 요소부터 시작해서 감소하는것이 더 빠르고 효율적
- list2.remove(i);
- Object remove(int index)를 호출한 것, 여기서 i는 index임
- 특정 숫자를 지우고 싶다면, 예를 들어 1을 지운다고 하면
- list.remove(new Integer(1));
- 이렇게 해야한다.
- boolean remove(Object obj)를 호출한 것
</> 실행 결과
list1 : [5, 4, 2, 0, 1, 3]
list2 : [4, 2, 0]
sorted list
list1 : [0, 1, 2, 3, 4, 5]
list2 : [0, 2, 4]
list1.containsAll(list2) : true
after adding elements
list1 : [0, 1, 2, 3, 4, 5]
list2 : [0, 2, 4, A, B, C]
notice the difference by using set method
list1 : [0, 1, 2, 3, 4, 5]
list2 : [0, 2, 4, AA, B, C]
list1.retainAll(list2) : true
list1 : [0, 2, 4]
list2 : [0, 2, 4, AA, B, C]
after removing duplicate elements
list1 : [0, 2, 4]
list2 : [AA, B, C]오늘 한 일
- 나동빈님의 이코테 책에서 그리디 알고리즘 연습문제들을 풀어보았다.
- 자바의 정석 컬렉션 프레임웍 시작
- 컬렉션 프레임웍의 인터페이스 종류? 각각 특징? 정의되어있는 메서드들? ArrayList란? ArrayList에 정의된 메서드들? 사용법?
Reminder
- 자바공부, 코딩 연습 많이 하자!!!
연! 저도 일요일부터 동빈북?! 따라갈게요!
오늘 피곤해서 조기 퇴근한게 아쉬워요ㅠㅠ