개발 학습 블로그

https://dev-skill.tistory.com/

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BfsIceCream {
	
	// 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고,
	// 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다.
	// 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경
	// 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크
	
	static int n = 0;
	static int m = 0;
	static String str = "";
	static int[][] arr = new int[1000][1000];
	public static int[] moveRow = {-1, 1, 0, 0};
	public static int[] moveCol = {0, 0, -1, 1};
	
	public static boolean bfs(int a, int b) {
		
		Queue<Point> q = new LinkedList<>();
		
		if (arr[a][b] == 0) { // 아이스크림 재료를 부을 수 있는 칸이라면
			
			q.offer(new Point(a,b));
			
			arr[a][b] = 1; // 아이스크림 재료 붓기
			
			while (!q.isEmpty()) {
				
				Point p = q.poll();
				
				int row = p.x;
				int col = p.y;
				
				for (int z = 0; z < 4; z++) { // 아이스크림 재료를 부은 칸의 상, 하, 좌, 우 확인하며 재료를 부을 수 있다면 같이 얼려서 아이스크림 덩어리 키우기
					int nextRow = row + moveRow[z];
					int nextCol = col + moveCol[z];
					
					// 4회 반복으로 인해 nextRow, nextCol은 아이스크림 재료를 부은 칸의 상, 하, 좌, 우 좌표가 될 것
					
					if (nextRow < 0 || nextRow > n - 1 || nextCol < 0 || nextCol > m - 1) { // 범위를 벗어난다면 continue
						continue;
					}
					
					if (arr[nextRow][nextCol] == 0) { // nextRow, nextCol이 재료를 부을 수 있는 칸이라면
						q.offer(new Point(nextRow,nextCol)); // nextRow, nextCol 기준 상, 하, 좌, 우 좌표 또한 같이 얼릴 수 있는 칸인지 확인을 위해 큐에 담기
						
						arr[nextRow][nextCol] = 1; // 재료 붓기
					}
				}
			}
			
			return true; // 아이스크림 재료를 부을 수 있는 칸이었으므로 true 리턴하여 result 값 1 증가되도록 하기
		}
		
		return false; // 아이스크림 재료를 부을 수 없는 칸이므로 false 리턴
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		
		System.out.print("행을 입력하세요 : ");
		
		n = scan.nextInt(); // 정수 입력 후 엔터를 치면 // 여기에 정수
		
//		scan.nextLine(); // 버퍼 비워주기 // 여기에 위에서 입력한 엔터
		
		System.out.print("열을 입력하세요 : ");
		
		m = scan.nextInt(); // 여기에 정수
		
		scan.nextLine(); // 버퍼 비워주기 // 위에서 입력받은 엔터들 이쪽으로
		
		System.out.println(n + "행 " + m + "열의 아이스크림 틀에서 아이스크림을 만듭니다. 빈 공간은 0 막힌 공간은 1로 입력해주세요 : ");
		
		for (int i = 0; i < n; i++) {
			System.out.print((i+1) + "번째 줄 입력 : ");
			str = scan.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		scan.close(); // 입력 그만 받도록
		
		int result = 0;
		
		for (int k = 0; k < n; k++) {
			for (int z = 0; z < m; z++) {
				if (bfs(k, z)) {
					result += 1; // 결과적으로 이 result 카운트는 총 n x m 횟수 중 true일 경우에만 증가한다.
				}
			}
		}
		
		System.out.print("아이스크림 갯수 : " + result);
	}
}

BFS 알고리즘 문제 풀이 Java 소스 코드

import java.util.Scanner;

public class DfsIceCream {
	
	// 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고,
	// 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다.
	// 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경
	// 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크
	
	static int n = 0;
	static int m = 0;
	static String str = "";
	static int[][] arr = new int[1000][1000];
	
	public static boolean dfs(int a, int b) {
		
		if (a < 0 || a > n - 1 || b < 0 || b > m - 1) { // 범위 벗어나는지 확인
			return false;
		}
		
		if (arr[a][b] == 0) { // 아이스크림을 만들 수 있는 공간이라면
			arr[a][b] = 1; // 아이스크림을 붓기
			dfs(a, b + 1); // 상 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행 // 여기서 또 0이 나오면 아이스크림 붓고 상,하,좌,우 체크하여 dfs함수 실행 반복 또 반복
			dfs(a, b - 1); // 하 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			dfs(a - 1, b); // 좌 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			dfs(a + 1, b); // 우 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			return true; // 아이스크림을 만들었다면 카운트 증가를 위해 true 반환
		}
		
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		
		System.out.print("행을 입력하세요 : ");
		
		n = scan.nextInt(); // 정수 입력 후 엔터를 치면 // 여기에 정수
		
//		scan.nextLine(); // 버퍼 비워주기 // 여기에 위에서 입력한 엔터
		
		System.out.print("열을 입력하세요 : ");
		
		m = scan.nextInt(); // 여기에 정수
		
		scan.nextLine(); // 버퍼 비워주기 // 위에서 입력받은 엔터들 이쪽으로
		
		System.out.println(n + "행 " + m + "열의 아이스크림 틀에서 아이스크림을 만듭니다. 빈 공간은 0 막힌 공간은 1로 입력해주세요 : ");
		
		for (int i = 0; i < n; i++) {
			System.out.print((i+1) + "번째 줄 입력 : ");
			str = scan.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		scan.close(); // 입력 그만 받도록
		
		int result = 0;
		
		for (int k = 0; k < n; k++) {
			for (int z = 0; z < m; z++) {
				if (dfs(k, z)) {
					result += 1; // 결과적으로 이 result 카운트는 총 n x m 횟수 중 true일 경우에만 증가한다.
				}
			}
		}
		
		System.out.print("아이스크림 갯수 : " + result);
	}
}

DFS 알고리즘 문제 풀이 Java 소스 코드

public class Solution {
	
	// 순위
	// Floyd Warshall 알고리즘으로 풀이
	
	public static int solution(int n, int[][] results) {
		int answer = 0;
		int zeroCnt = 0;
		int[][] board = new int[n][n]; // 0 ~ 4
		
		for (int i = 0; i < results.length; i++) {
			// {4, 3}의 경우
			board[results[i][0] - 1][results[i][1] - 1] = 1; // 4는 3에게 이겼으므로 board[3][2] = 1
			board[results[i][1] - 1][results[i][0] - 1] = -1; // 3은 4에게 졌으므로 board[2][3] = -1
		}
		
//		0 : {0, 1, 0, 0, 0}
//		1 : {-1, 0, -1, -1, 1}
//		2 : {0, 1, 0, -1, 0}
//		3 : {0, 1, 1, 0, 0}
//		4 : {0, -1, 0, 0, 0}
		
		for (int k = 0; k < n; k++) {
			
			for (int i = 0; i < n; i++) {
				
				for (int j = 0; j < n; j++) {
					
					if (k == i || i == j || k == j) { // 자기 자신과의 경기는 있을 수 없다.
						continue;
					}
					
					if (board[i][j] == 0) { // i와 j의 경기 결과를 분실했다면
						
						if (board[i][k] == 1 && board[k][j] == 1) { // i가 k에게 이기고, k가 j에게 이겼다면
							board[i][j] = 1; // i는 j에게 이긴 것으로 체크
						} else if (board[i][k] == -1 && board[k][j] == -1) { // i가 k에게 지고, k가 j에게 졌다면
							board[i][j] = -1; // i는 j에게 진 것으로 체크
						}
					}
				}
			}
		}
		
//		0 : {0, 1, 0, 0, 1}
//		1 : {-1, 0, -1, -1, 1} // 자기 자신을 제외하고 다른 모든 선수들과의 경기 결과를 알 수 있는 선수
//		2 : {0, 1, 0, -1, 1}
//		3 : {0, 1, 1, 0, 1}
//		4 : {-1, -1, -1, -1, 0} // 자기 자신을 제외하고 다른 모든 선수들과의 경기 결과를 알 수 있는 선수
		
		for (int i = 0; i < n; i++) {
			
			zeroCnt = 0;
			
			for (int j = 0; j < n; j++) {
				
				if (board[i][j] == 0) {
					zeroCnt++;
				}
			}
			
			if (zeroCnt == 1) {
				answer++;
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};
		
		System.out.println(solution(n, results)); // 2
	}
}

플로이드 워셜 알고리즘

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.

public class FloydWarshall {
	
	// 플로이드 워셜 알고리즘
	// 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
	// 만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.
	
	static int number = 4;
	static int INF = 100000000;
	static int[][] originArr = {{0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0}}; // 자료 배열 초기화
	
	public static void floydWarshall() {
		int[][] renewArr = new int[number][number]; // 결과 배열 초기화
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				renewArr[i][j] = originArr[i][j]; // 결과 배열을 초기 자료 배열과 동일하게 만들어 준다.
			}
		}
		
		// k : 거쳐가는 노드
		for (int k = 0; k < number; k++) {
			
			// i : 출발 노드
			for (int i = 0; i < number; i++) {
				
				// j : 도착 노드
				for (int j = 0; j < number; j++) {
					
					if (renewArr[i][k] + renewArr[k][j] < renewArr[i][j]) { // k 노드를 거쳐갈 때 거리 값이 더 작다면
						renewArr[i][j] = renewArr[i][k] + renewArr[k][j]; // i 노드에서 j 노드로 가는 최단 거리 갱신
					}
				}
			}
		}
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				System.out.print(renewArr[i][j] + " "); // 결과 배열 출력
			}
			
			System.out.println();
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		floydWarshall();
	}
}

import java.util.HashMap;

public class Solution {
	
	// 롤케이크 자르기
	
	public static int solution(int[] topping) {
		int answer = 0;
		
		HashMap<Integer, Integer> hm1 = new HashMap<>();
		HashMap<Integer, Integer> hm2 = new HashMap<>();
		
		for (int i = 0; i < topping.length; i++) {
			hm2.put(topping[i], hm2.getOrDefault(topping[i], 0) + 1);
		}
		
		// hm2 : {1=4, 2=2, 3=1, 4=1}
		
		for (int i = 0; i < topping.length; i++) {
			hm1.put(topping[i], hm1.getOrDefault(topping[i], 0) + 1);
			
			if (hm2.containsKey(topping[i])) {
				hm2.put(topping[i], hm2.get(topping[i]) - 1);
			}
			
			if (hm2.get(topping[i]) == 0) {
				hm2.remove(topping[i]);
			}
			
			if (hm1.size() == hm2.size()) { // hm1 : {1=2, 2=1, 3=1}, hm2 : {1=2, 2=1, 4=1} // hm1 : {1=3, 2=1, 3=1}, hm2 : {1=1, 2=1, 4=1}
				answer++;
			}
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] topping = {1, 2, 1, 3, 1, 4, 1, 2}; // 1, 2, 1, 3과 1, 4, 1, 2로 잘랐을 떄, 1, 2, 1, 3, 1과 4, 1, 2로 잘랐을 때
		
		System.out.println(solution(topping)); // 2
	}
}

<객체 비교>

== : 동일성 비교(객체 인스턴스의 주소 값을 비교)

equals() : 동등성 비교(객체 내부의 값을 비교)

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로 처리

<MySQL>

SELECT A.MEMBER_NAME
     , B.REVIEW_TEXT
     , DATE_FORMAT(B.REVIEW_DATE, '%Y-%m-%d') AS REVIEW_DATE
  FROM MEMBER_PROFILE A
     , REST_REVIEW B
 WHERE A.MEMBER_ID = B.MEMBER_ID
   AND B.MEMBER_ID IN (
                        SELECT MEMBER_ID
                          FROM REST_REVIEW
                      GROUP BY MEMBER_ID
                        HAVING COUNT(MEMBER_ID) = (
                                                    SELECT COUNT(MEMBER_ID) AS CNT
                                                      FROM REST_REVIEW
                                                  GROUP BY MEMBER_ID
                                                  ORDER BY COUNT(MEMBER_ID) DESC
                                                     LIMIT 1                      
                                                  )
                      )
 ORDER BY B.REVIEW_DATE, B.REVIEW_TEXT

<Oracle>

SELECT A.MEMBER_NAME
     , B.REVIEW_TEXT
     , TO_CHAR(B.REVIEW_DATE, 'YYYY-MM-DD') AS REVIEW_DATE
  FROM MEMBER_PROFILE A
     , REST_REVIEW B
 WHERE A.MEMBER_ID = B.MEMBER_ID
   AND B.MEMBER_ID IN (
                        SELECT MEMBER_ID
                          FROM REST_REVIEW
                      GROUP BY MEMBER_ID
                        HAVING COUNT(MEMBER_ID) = (
                                                    SELECT MAX(COUNT(MEMBER_ID)) AS CNT
                                                      FROM REST_REVIEW
                                                  GROUP BY MEMBER_ID                 
                                                  )
                      )
 ORDER BY B.REVIEW_DATE, B.REVIEW_TEXT

프로그래머스 그룹별 조건에 맞는 식당 목록 출력하기 SQL