public class PccpTest1_2 {
// PCCP 모의고사 1회 2번 체육대회
static int answer = 0; // 최대값 담을 answer 변수
static boolean[] selectStudentNumArr; // 대표로 뽑힌 학생인지 확인을 위한 boolean 배열
static int studentCnt = 0; // 총 학생 수
static int sportsCnt = 0; // 총 종목 수
public static void dfs(int depth, int sum, int[][] ability) { // 종목 index, 합계 점수, 학생별 능력치가 담긴 배열
if (depth == sportsCnt) { // 세 번째 종목 점수까지 합산된 후라면
answer = Math.max(answer, sum); // 세 번째 종목 점수까지 합산된 결과 중 최대값을 answer 변수에 넣기
} else { // depth가 0, 1, 2인 경우
for (int i = 0; i < studentCnt; i++) { // 0 ~ 4
if (selectStudentNumArr[i] == false) { // 아직 선택되지 않은 학생이라면
selectStudentNumArr[i] = true; // 해당 학생 선택
dfs(depth + 1, sum + ability[i][depth], ability); // 해당 학생의 종목 중 index가 depth인 종목의 점수를 합계에 더하고, 다음 종목 확인을 위해 dfs
selectStudentNumArr[i] = false; // dfs 빠져나온 이후 해당 학생은 다시 선택 전 상태로
}
}
}
}
public static int solution(int[][] ability) {
selectStudentNumArr = new boolean[ability.length]; // {false, false, false, false, false}
studentCnt = ability.length; // 5
sportsCnt = ability[0].length; // 3
dfs(0, 0, ability); // 종목 index 0, 합계 점수 0, 학생별 능력치가 담긴 배열
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] ability = {{40, 10, 10}, {20, 5, 0}, {30, 30, 30}, {70, 0, 70}, {100, 100, 100}}; // 5명의 학생, 3개의 종목
System.out.println(solution(ability)); // 40(0, 0) + 100(4, 1) + 70(3, 2) // 210
}
}
import java.util.*;
public class PccpTest1_1 {
// PCCP 모의고사 1회 1번 외톨이 알파벳
public static String solution(String input_string) {
String answer = "";
char tempChar;
int tempCnt = 0;
int repeatCnt = 0;
Queue<Character> q = new LinkedList<>();
HashMap<Character, Integer> originHm = new HashMap<>();
HashMap<Character, Integer> repeatChkHm = new HashMap<>();
ArrayList<Character> list = new ArrayList<>();
for (int i = 0; i < input_string.length(); i++) {
q.offer(input_string.charAt(i)); // e d e a a a b b c c d
}
while (!q.isEmpty()) {
tempChar = q.poll();
if (originHm.get(tempChar) == null) { // originHm에는 key값으로 알파벳이, value값으로 해당 알파벳의 총 카운트가 들어갈 것이다.
originHm.put(tempChar, 1);
repeatChkHm.put(tempChar, 1);
} else {
tempCnt = originHm.get(tempChar) + 1;
originHm.put(tempChar, tempCnt);
}
if (!q.isEmpty()) { // AABBAA일 경우 // originHm A : 4, B : 2 // repeatChkHm A : 3, B : 2
if (tempChar == q.peek()) { // 연속되는 알파벳이라면
repeatCnt = repeatChkHm.get(tempChar) + 1;
repeatChkHm.put(tempChar, repeatCnt);
}
}
}
for (char key : originHm.keySet()) {
if (originHm.get(key) != repeatChkHm.get(key) && originHm.get(key) > 1) {
list.add(key);
}
}
if (list.size() == 0) {
answer = "N";
} else {
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
}
answer = sb.toString();
}
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String input_string = "edeaaabbccd";
System.out.println(solution(input_string));
}
}
public class Solution {
// 땅따먹기
public static int solution(int[][] land) {
int answer = 0;
int[][] sumArr = new int[land.length][land[0].length];
sumArr = land;
for (int i = 1; i < land.length; i++) { // 행
for (int j = 0; j < 4; j++) { // 열
int max = sumArr[i][j]; // 비교 대상 행의 열 값을 max로 지정
for (int z = 0; z < 4; z++) { // 비교 열
if (j == z) { // 같은 행에선 비교x
continue;
}
if (max < sumArr[i - 1][z] + land[i][j]) {
max = sumArr[i - 1][z] + land[i][j]; // 더 큰 값이 존재한다면 max값 변경
}
}
sumArr[i][j] = max; // 비교가 끝났다면 이번 행, 이번 열이 가질 수 있는 최대값 갱신
}
}
// for (int i = 0; i < land.length; i++) {
//
// for (int j = 0; j < 4; j++) {
// System.out.print(sumArr[i][j] + " ");
// }
// System.out.println();
// }
int sumMax = sumArr[sumArr.length - 1][0];
for (int i = 1; i < 4; i++) {
if (sumMax < sumArr[sumArr.length - 1][i]) {
sumMax = sumArr[sumArr.length - 1][i];
}
}
answer = sumMax;
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] land = {{1,2,3,5},{5,6,7,8},{4,3,2,1}};
System.out.println(solution(land)); // 16
}
}
hashCode() : 객체의 메모리 번지를 이용해서 해시코드를 만들고 그 값을 리턴(객체마다 다른 값을 가지고 있다.)
hashCode()를 사용하는 이유 중 하나는, 객체를 비교할 때 드는 비용을 낮추기 위함이다.
자바에서 2개의 객체가 같은지 비교할 때 equals()를 사용하는데, 여러 객체를 비교할 때 equals()를 사용하면 Integer를 비교하는 것에 비해 많은 시간이 소요된다.
hashCode() 메소드를 실행하여 리턴된 해시코드 값이 다르면 다른 객체로 판단하고, 해시코드 값이 같으면 equals() 메소드로 두 객체를 다시 비교한다.
즉, 여러 객체의 동등성 비교를 할 때 hashCode() 메소드를 실행해 값이 같을 경우에만 equals() 메소드로 동등성을 비교하면 되는 것이다. hashCode() 값이 다르면 애초에 비교할 필요가 없게 된다.
hashCode가 다르면, 두개의 객체가 같지 않다.
hashCode가 같으면, 두개의 객체가 같거나 다를 수 있다.
<equals()와 hashCode()를 같이 재정의해야 하는 이유>
1. hashCode()를 재정의 하지 않으면 같은 값 객체라도 해시값이 다를 수 있다. 따라서 HashTable에서 해당 객체가 저장된 버킷을 찾을 수 없다.
2. equals()를 재정의하지 않으면 hashCode()가 만든 해시값을 이용해 객체가 저장된 버킷을 찾을 수는 있지만 해당 객체가 자신과 같은 객체인지 값을 비교할 수 없기 때문에 null을 리턴하게 된다.
<equals()만 재정의>
public class Test {
String name;
public Test(String name) {
this.name = name;
}
@Override
public boolean equals(Object obj) {
Test otherTest = (Test) obj;
return (this.name.equals(otherTest.name));
}
}
import java.util.HashMap;
public class EqualsAndHashCode {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "Z@S.ME";
String str2 = "Z@RN.E";
HashMap<String, Integer> hm1 = new HashMap<>();
hm1.put(str1, 30);
hm1.put(str2, 40);
System.out.println(str1.equals(str2)); // false
System.out.println(str1.hashCode()); // -1656719047
System.out.println(str2.hashCode()); // -1656719047
System.out.println(hm1.size()); // 2
System.out.println(hm1.get(str1)); // 30
System.out.println(hm1.get(str2)); // 40
Test test1 = new Test("abcd");
Test test2 = new Test(new String("abcd"));
HashMap<Test, Integer> hm2 = new HashMap<>();
hm2.put(test1, 10);
hm2.put(test2, 20);
System.out.println(test1.equals(test2)); // true
System.out.println(test1.hashCode()); // 474675244
System.out.println(test2.hashCode()); // 932583850
System.out.println(hm2.size()); // 2
System.out.println(hm2.get(test1)); // 10
System.out.println(hm2.get(test2)); // 20
}
}
<hashcode()만 재정의>
public class Test {
String name;
public Test(String name) {
this.name = name;
}
@Override
public int hashCode() {
int hashCode = 0;
hashCode = 31 * hashCode + ((name == null) ? 0 : name.hashCode());
return hashCode;
}
}
import java.util.HashMap;
public class EqualsAndHashCode {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "Z@S.ME";
String str2 = "Z@RN.E";
HashMap<String, Integer> hm1 = new HashMap<>();
hm1.put(str1, 30);
hm1.put(str2, 40);
System.out.println(str1.equals(str2)); // false
System.out.println(str1.hashCode()); // -1656719047
System.out.println(str2.hashCode()); // -1656719047
System.out.println(hm1.size()); // 2
System.out.println(hm1.get(str1)); // 30
System.out.println(hm1.get(str2)); // 40
Test test1 = new Test("abcd");
Test test2 = new Test(new String("abcd"));
HashMap<Test, Integer> hm2 = new HashMap<>();
hm2.put(test1, 10);
hm2.put(test2, 20);
System.out.println(test1.equals(test2)); // false
System.out.println(test1.hashCode()); // 2987074
System.out.println(test2.hashCode()); // 2987074
System.out.println(hm2.size()); // 2
System.out.println(hm2.get(test1)); // 10
System.out.println(hm2.get(test2)); // 20
}
}
<equals()와 hashcode() 모두 재정의>
public class Test {
String name;
public Test(String name) {
this.name = name;
}
@Override
public boolean equals(Object obj) {
Test otherTest = (Test) obj;
return (this.name.equals(otherTest.name));
}
@Override
public int hashCode() {
int hashCode = 0;
hashCode = 31 * hashCode + ((name == null) ? 0 : name.hashCode());
return hashCode;
}
}
import java.util.HashMap;
public class EqualsAndHashCode {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "Z@S.ME";
String str2 = "Z@RN.E";
HashMap<String, Integer> hm1 = new HashMap<>();
hm1.put(str1, 30);
hm1.put(str2, 40);
System.out.println(str1.equals(str2)); // false
System.out.println(str1.hashCode()); // -1656719047
System.out.println(str2.hashCode()); // -1656719047
System.out.println(hm1.size()); // 2
System.out.println(hm1.get(str1)); // 30
System.out.println(hm1.get(str2)); // 40
Test test1 = new Test("abcd");
Test test2 = new Test(new String("abcd"));
HashMap<Test, Integer> hm2 = new HashMap<>();
hm2.put(test1, 10);
hm2.put(test2, 20);
System.out.println(test1.equals(test2)); // true
System.out.println(test1.hashCode()); // 2987074
System.out.println(test2.hashCode()); // 2987074
System.out.println(hm2.size()); // 1
System.out.println(hm2.get(test1)); // 20
System.out.println(hm2.get(test2)); // 20
}
}
equals()만 재정의 : equals()가 true이고, hashCode()가 다른 경우 => HashMap에서 다른 key로 인식
hashCode()만 재정의 : equals()가 false이고, hashCode()가 같은 경우 => HashMap에서 다른 key로 인식
equals()와 hashCode() 모두 재정의 : equals()가 true이고, hashCode()가 같은 경우 => HashMap에서 같은 key로 처리
public class ExceptionOccurred {
// Checked Exception : RuntimeException을 상속받지 않은 클래스
// Unchecked Exception : RuntimeException을 상속받은 클래스
// throw : 강제로 예외를 발생시킬 수 있음 단, 발생시킨 예외를 catch문에서 잡을 수 있는 처리가 되어있지 않으면 오류 발생(catch문의 Exception은 모든 예외를 잡을 수 있음)
// throws : 예외 발생 시 자신을 호출한 상위 메소드로 예외를 던짐(특정 상위 메소드에서 예외를 한 번에 처리하는 경우가 있을 수 있음, 계속 throws로 던질 경우 최종적으로 JVM이 처리를 하게 되지만, 권장하지 않음)
// 중요 : RuntimeException을 상속받은 Unchecked Exception의 경우 throws는 아무 의미 없음, throws는 Checked Exception의 처리 방법 중 하나
public void method1() throws Exception {
// 이 메소드를 호출한 부분의 catch문에 Exception에 대한 에외 처리가 있어야 함
throw new Exception("강제로 예외 발생"); // 모든 예외를 잡을 수 있는 Exception의 경우 throws Exception 필수
}
// RuntimeException을 상속받은 NullPointerException
public void method2() {
// 이 메소드를 호출한 부분의 catch문에 Exception 또는 NullPointerException에 대한 예외 처리가 있어야 함
throw new NullPointerException("강제로 NullPointerException 발생"); // NullPointerException 발생
}
// RuntimeException을 상속받은 ArithmeticException
public void method3() {
// 이 메소드를 호출한 부분의 catch문에 Exception 또는 ArithmeticException에 대한 예외 처리가 있어야 함
System.out.println(3 / 0); // ArithmeticException 발생
}
// RuntimeException을 상속받은 NullPointerException 발생이므로 throws는 아무 의미 없음
public void method4() throws ArithmeticException {
throw new NullPointerException("강제로 NullPointerException 발생"); // NullPointerException 발생
}
// RuntimeException을 상속받은 NullPointerException 발생이므로 throws는 아무 의미 없음
public void method5() throws ArithmeticException {
String name = null;
System.out.println(name.length());
}
// ArithmeticException : 어떤 수를 0으로 나눌 때 발생(RuntimeException 상속)
// NullPointerException : NULL 객체를 참조할 때 발생(RuntimeException 상속)
// ClassCastException : 적절하지 못하게 클래스를 형 변환하는 경우 발생(RuntimeException 상속)
// NegativeArraySizeException : 배열의 크기가 음수 값인 경우 발생(RuntimeException 상속)
// IndexOutOfBoundsException : 리스트형 객체에서 선언되지 않은 요소를 가져오려고 할 때 발생(RuntimeException 상속)
}
public class ExceptionTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
String name = null;
ExceptionOccurred exceptionOccurred = new ExceptionOccurred();
try {
int nameLength = name.length(); // 1. NullPointerException에 걸리고 finally 실행
int num = 3 / 0; // 2. 코드 1이 없다면 ArithmeticException에 걸리고 finally 실행
exceptionOccurred.method2(); // 3. 코드 1, 2가 없다면 NullPointerException에 걸리고 finally 실행
exceptionOccurred.method3(); // 4. 코드 1, 2, 3이 없다면 ArithmeticException에 걸리고 finally 실행
} catch (NullPointerException e) {
System.out.println("NullPointerException : " + e.getMessage());
} catch (ArithmeticException e1) {
System.out.println("ArithmeticException : " + e1.getMessage());
} catch (Exception e) { // try문 실행에서 발생하는 예외 중 NullPointerException, ArithmeticException 외의 예외는 이곳에 걸림
System.out.println("Exception : 모든 예외를 잡을 수 있음");
} finally { // 무조건 실행시킬 코드를 적는 부분
System.out.println("무조건 실행되는 부분");
}
try {
int nameLength = name.length(); // 1. Exception에 걸리고 finally 실행
int num = 3 / 0; // 2. 코드 1이 없다면 Exception에 걸리고 finally 실행
exceptionOccurred.method1(); // 3. 코드 1, 2가 없다면 Exception에 걸리고 finally 실행
throw new Exception("강제 예외 발생"); // 4. 코드 1, 2, 3이 없다면 Exception에 걸리고 finally 실행
// exceptionOccurred.method2(); // 5. 코드 1, 2, 3, 4가 없다면 Exception에 걸리고 finally 실행
// exceptionOccurred.method3(); // 6. 코드 1, 2, 3, 4, 5가 없다면 Exception에 걸리고 finally 실행
} catch (Exception e) { // try문 실행에서 발생하는 모든 예외를 잡을 수 있지만, 어떤 문제로 발생하는 예외인지 확인이 불가하다는 단점이 있다.
System.out.println("Exception : 모든 예외를 잡을 수 있음");
} finally { // 무조건 실행시킬 코드를 적는 부분
System.out.println("무조건 실행되는 부분");
}
}
}
Checked Exception : RuntimeException을 상속받지 않은 클래스
Unchecked Exception : RuntimeException을 상속받은 클래스
throw : 강제로 예외를 발생시킬 수 있음 단, 발생시킨 예외를 catch문에서 잡을 수 있는 처리가 되어있지 않으면 오류 발생(catch문의 Exception은 모든 예외를 잡을 수 있음)
throws : 예외 발생 시 자신을 호출한 상위 메소드로 예외를 던짐(특정 상위 메소드에서 예외를 한 번에 처리하는 경우가 있을 수 있음, 계속 throws로 던질 경우 최종적으로 JVM이 처리를 하게 되지만, 권장하지 않음)
중요 : RuntimeException을 상속받은 Unchecked Exception의 경우 throws는 아무 의미 없음
Comparable : 현재 객체와 다른 객체의 비교 기준을 정함 => Comparable - CompareTo (T o) 정의
Comparator : 두 객체의 비교 기준을 정함 => Comparator - Compare(T o1, T o2) 정의
<Comparable>
public class Node implements Comparable<Node> {
private int index = 0; // 노드의 번호
private int distance = 0; // 노드의 거리
private String name = ""; // 노드의 이름
public Node(int index, int distance, String name) {
this.index = index;
this.distance = distance;
this.name = name;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
public String getName() {
return this.name;
}
@Override
public int compareTo(Node otherNode) {
// TODO Auto-generated method stub
// private 변수이지만 클래스 내부에선 getDistance()로 가져올 필요 없이 직접 가져와도 됨
// return this.distance - otherNode.distance; // distance 기준 오름차순 정렬 // 1, 2, 3, ...
// return this.getDistance() - otherNode.getDistance(); // distance 기준 오름차순 정렬 // 1, 2, 3, ...
// return otherNode.distance - this.distance; // distance 기준 내림차순 정렬 // ..., 3, 2, 1
// return otherNode.getDistance() - this.getDistance(); // distance 기준 내림차순 정렬 // ..., 3, 2, 1
// distance, index, name 기준 오름차순 정렬(ORDER BY distance, index, name)
if (this.distance == otherNode.distance) { // distance가 같을 경우
if (this.index == otherNode.index) { // index가 같을 경우
return this.name.compareTo(otherNode.name); // name 기준 오름차순 정렬
// return otherNode.name.compareTo(this.name); // name 기준 내림차순 정렬
} else { // index가 같지 않을 경우
return this.index - otherNode.index; // index 기준 오름차순 정렬
// return otherNode.index - this.index; // index 기준 내림차순 정렬
}
} else { // distance가 같지 않을 경우
return this.distance - otherNode.distance; // distance 기준 오름차순 정렬
// return otherNode.distance - this.distance; // distance 기준 내림차순 정렬
}
// // int 값으로 비교 : return int - int;
// // String 값으로 비교 : return String.compareTo(String);
// ------------------------------------------------------------------------------------------------------
// // distance 값을 기준으로 오름차순 정렬을 시키는 다른 방법 1, 2, 3, ...
// if (this.distance < otherNode.distance) {
// return -1; // 해당 노드의 거리가 비교대상 노드의 거리보다 작다면 => 해당 노드가 더 작다 리턴
// }
//
// return 1; // 해당 노드의 거리가 비교대상 노드의 거리보다 크거나 같다면 => 해당 노드가 더 크다 리턴
//
// // distance 값을 기준으로 내림차순 정렬을 시키는 다른 방법 ..., 3, 2, 1
// if (this.distance < otherNode.distance) {
// return 1; // 해당 노드의 거리가 비교대상 노드의 거리보다 작다면 => 해당 노드가 더 크다 리턴
// }
//
// return -1; // 해당 노드의 거리가 비교대상 노드의 거리보다 크거나 같다면 => 해당 노드가 더 작다 리턴
//
// // int 값으로 비교 : 1(크다), 0(같다), -1(작다)
// // String 값으로 비교 : 0(같다), 다양한 양수/음수 값 : 대상 문자열의 제일 앞 부분부터 비교하여 비교대상 문자열을 포함한다면 문자열 길이 차만큼 리턴, 하지만 아예 포함하지 않거나, 중간에 포함한다면 각 문자열의 제일 앞 아스키 코드값의 차를 리턴(대상 문자열 첫 문자 아스키코드 값 - 비교대상 문자열 첫 문자 아스키코드 값)
// ------------------------------------------------------------------------------------------------------
}
}
import java.util.*;
public class ComparableTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
// --------------------------------------일반 배열--------------------------------------
int[] arr1 = {2, 1, 6, 3, 7, 4, 5};
for (int num : arr1) {
System.out.print(num + " "); // 2 1 6 3 7 4 5
}
System.out.println();
// --------------------------------------배열 정렬--------------------------------------
Arrays.sort(arr1); // 기본 오름차순 정렬
for (int num : arr1) {
System.out.print(num + " "); // 1 2 3 4 5 6 7
}
System.out.println();
// ------------------------Comparable 인터페이스를 구현한 Node 클래스------------------------
ArrayList<Node> list = new ArrayList<>();
// index, distance, name
list.add(new Node(1, 2, "B"));
list.add(new Node(2, 1, "A"));
list.add(new Node(2, 2, "C"));
list.add(new Node(1, 3, "F"));
list.add(new Node(1, 3, "E"));
list.add(new Node(1, 3, "D"));
for (Node node : list) {
System.out.print(node.getName() + " "); // "B", "A", "C", "F", "E", "D"
}
System.out.println();
// -----------------------------------Node 클래스 정렬-----------------------------------
Collections.sort(list); // Node 클래스의 정렬 기준 : ORDER BY distance, index, name
for (Node node : list) {
System.out.print(node.getName() + " "); // "A", "B", "C", "D", "E", "F"
}
}
}
<Comparator>
public class Node {
private int index = 0; // 노드의 번호
private int distance = 0; // 노드의 거리
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
import java.util.*;
public class ComparatorTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
// -------------------------------------Node 클래스-------------------------------------
ArrayList<Node> list = new ArrayList<>();
list.add(new Node(2, 2));
list.add(new Node(1, 1));
list.add(new Node(3, 3));
for (Node node : list) {
System.out.print(node.getDistance() + " "); // 2, 1, 3
}
System.out.println();
// -----------------------------------Node 클래스 정렬-----------------------------------
Collections.sort(list, new Comparator<Node>() {
@Override
public int compare(Node node1, Node node2) {
// distance 기준 오름차순 정렬 // 1, 2, 3, ...
if(node1.getDistance() < node2.getDistance()) return -1;
else if(node1.getDistance() == node2.getDistance()) return 0;
else return 1;
// distance 기준 내림차순 정렬 // ..., 3, 2, 1
// if(node1.getDistance() < node2.getDistance()) return 1;
// else if(node1.getDistance() == node2.getDistance()) return 0;
// else return -1;
// distance는 Node 클래스의 private 변수이므로 node1.distance가 아닌 distance 값을 가져오도록 만든 node1.getDistance() 메소드 사용
}
});
for (Node node : list) {
System.out.print(node.getDistance() + " "); // 1, 2, 3
}
}
}
<2차원 배열에서 다중 정렬>
int[][] arr = {{1, 3}, {1, 2}, {3, 4}, {1, 4}, {2, 4}};
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]) { // 앞 원소가 같을 경우
return o1[1] - o2[1]; // 뒤 원소 기준 오름차순
// return o2[1] - o1[1]; // 뒤 원소 기준 내림차순
}else { // 앞 원소가 같지 않을 경우
return o1[0] - o2[0]; // 앞 원소 기준 오름차순
// return o2[0] - o1[0]; // 앞 원소 기준 내림차순
}
}
});
