개발 학습 블로그

첫 시도에서 런타임 에러가 발생해 다른 방법으로 풀이하였다.

import java.util.HashSet;

public class Solution {
	
	// 등대
	
	public static int solution(int n, int[][] lighthouse) {
		int answer = 0;
		int[] linkedCntArr; // 각 등대에 연결된 등대의 수를 입력받기 위한 배열
		
		HashSet<Integer> edgeHs = new HashSet<>(); // 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대의 번호를 담을 HashSet
		HashSet<Integer> turnOnHs = new HashSet<>(); // 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된, 반드시 켜야 하는 등대의 번호를 담을 HashSet
		int[][] remainingLightHouse; // 반드시 켜야 하는 등대를 킨 후 남은 등대 쌍을 담을 2차원 배열
		int remainingCnt; // remainingLightHouse에 담긴 등대 쌍의 수
		
		// CASE 1을 기준으로 설명
		
		for (int a = 0; a < n; a++) { // 과정 반복
			
			// 현재 turnOnHs가 비어있지 않은 상황이라면, turnOnHs에 담긴 번호의 등대를 킨 상황으로, 켜진 등대의 영향을 받는 등대는 고려해야 할 대상에서 제외한다.(lighthouse의 길이가 줄었을 것)
			
			linkedCntArr = new int[n + 1]; // linkedCntArr 초기화 // 0 ~ n
			remainingLightHouse = new int[lighthouse.length][2]; // remainingLightHouse 초기화
			remainingCnt = 0; // remainingCnt 초기화
			
			for (int i = 0; i < lighthouse.length; i++) {
				linkedCntArr[lighthouse[i][0]]++;
				linkedCntArr[lighthouse[i][1]]++;
			}
			
			// linkedCntArr : {0, 4, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 3, 1, 1}
			
			for (int i = 0; i < linkedCntArr.length; i++) {
				
				if (linkedCntArr[i] == 1) { // 연결된 등대가 하나뿐이라면 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대
					edgeHs.add(i); // edgeHs에 등대 번호 담기
				}
			}
			
			// edgeHs : [3, 4, 7, 8, 11, 13, 14]
			
			for (int i = 0; i < lighthouse.length; i++) {
				
				// 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된 등대 번호를 turnOnHs에 담기 // 반드시 켜야 하는 등대 번호
				
				if (edgeHs.contains(lighthouse[i][0]) || edgeHs.contains(lighthouse[i][1])) {
					
					if (edgeHs.contains(lighthouse[i][0])) {
						turnOnHs.add(lighthouse[i][1]);
					} else {
						turnOnHs.add(lighthouse[i][0]);
					}
				}
			}
			
			// turnOnHs : [1, 6, 10, 12]
			
			for (int i = 0; i < lighthouse.length; i++) {
				
				// turnOnHs에 담긴 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍이 있는지 확인
				
				if (!turnOnHs.contains(lighthouse[i][0]) && !turnOnHs.contains(lighthouse[i][1])) {
					remainingLightHouse[remainingCnt] = lighthouse[i];
					remainingCnt++;
				}
			}
			
			// remainingLightHouse : {{2, 9}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}
			// remainingCnt == 1
			
			if (remainingCnt == 0) { // 현재 켜진 등대로 모든 등대를 밝힐 수 있다면
				break;
			}
			
			if (remainingCnt == 1) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍이 1쌍 존재한다면
				answer += 1; // 남은 1쌍의 등대 중 어떤 등대를 켜도 되기 때문에 1만 증가
				break;
			}
			
			if (remainingCnt < lighthouse.length) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍의 수가 2 이상 lighthouse.length 미만이라면
				lighthouse = new int[remainingCnt][2]; // lighthouse의 길이 줄이기
				
				for (int i = 0; i < remainingCnt; i++) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍만 고려하면 된다.
					lighthouse[i] = remainingLightHouse[i];
				}
			}
			
			// 다시 for문으로 가 과정 반복
		}
		
		answer += turnOnHs.size(); // 켜진 등대의 수를 더해준다.
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// CASE 1
		int n = 14;
		int[][] lighthouse = {{4, 1}, {5, 1}, {5, 6}, {7, 6}, {1, 2}, {1, 3}, {6, 8}, {2, 9}, {9, 10}, {10, 11}, {5, 12}, {12, 13}, {12, 14}};
		// CASE 2
//		int n = 10;
//		int[][] lighthouse = {{4, 1}, {5, 1}, {5, 6}, {7, 6}, {1, 2}, {1, 3}, {6, 8}, {2, 9}, {9, 10}};
		// CASE 3
//		int n = 8;
//		int[][] lighthouse = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {5, 6}, {5, 7}, {5, 8}};
		
		System.out.println(solution(n, lighthouse));
	}
}

2022.11.17 기준 정답률이 6%밖에 안되는 문제이기 때문일까? 점수를 13점이나 준다.

내가 풀이한 방법은 이렇다.

STEP 1. 반드시 켜야 하는 등대의 기준

가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된 등대는 반드시 켜야 한다.

가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대는 lighthouse 배열의 원소들 중 하나만 존재하는 번호에 해당하며,

그 번호와 쌍을 이루는 번호는 반드시 켜야 하는 등대의 번호를 의미한다.

STEP 2. 반드시 켜야 하는 등대의 번호를 HashSet에 담고, lighthouse 배열의 원소들 중 HashSet에 존재하는 번호가

있을 경우, 그 번호를 포함한 등대 쌍(배열)을 제거한다. => 현재 켜진 등대로 밝힐 수 없는 등대 쌍만 남게 된다.

STEP 3. STEP 2에서 남은 등대 쌍으로 lighthouse 배열을 다시 만든다.

STEP 4. STEP 1부터 과정을 반복한다.

프로그래머스 등대 문제 풀이 Java 소스 코드

import java.util.ArrayList;
import java.util.HashMap;

public class Solution {
	
	// 양과 늑대
	
	static int maxSheepCnt;
	static HashMap<Integer, ArrayList<Integer>> hm;
	
	public static void dfs(int currentIndex, int s, int w, ArrayList<Integer> indexList, int[] info) {
		
		if (info[currentIndex] == 0) {
			s += 1;
		} else {
			w += 1;
		}
		
		if (s <= w) return;
		
		maxSheepCnt = Math.max(maxSheepCnt, s);
		
		ArrayList<Integer> nextIndexList = new ArrayList<>();
		nextIndexList.addAll(indexList);
		
		if (hm.containsKey(currentIndex)) {
			nextIndexList.addAll(hm.get(currentIndex));
		}
		
		nextIndexList.remove(Integer.valueOf(currentIndex));
		
		for (int nextIndex : nextIndexList) {
			dfs(nextIndex, s, w, nextIndexList, info);
		}
		
		return;
	}
	
	public static int solution(int[] info, int[][] edges) {
		maxSheepCnt = 0;
		hm = new HashMap<>();
		
		for (int i = 0; i < edges.length; i++) {
			
			if (!hm.containsKey(edges[i][0])) {
				hm.put(edges[i][0], new ArrayList<>());
			}
			
			hm.get(edges[i][0]).add(edges[i][1]);
		}
		
//		hm : {0=[1, 8], 1=[2, 4], 4=[3, 6], 6=[5], 8=[7, 9], 9=[10, 11]}
		
		ArrayList<Integer> startIndexList = new ArrayList<>();
		startIndexList.add(0);
		
		dfs(0, 0, 0, startIndexList, info);
		
		return maxSheepCnt;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] info = {0,0,1,1,1,0,1,0,1,0,1,1};
		int[][] edges = {{0,1},{1,2},{1,4},{0,8},{8,7},{9,10},{9,11},{4,3},{6,5},{4,6},{8,9}};
		
		System.out.println(solution(info, edges));
	}
}

프로그래머스 양과 늑대 문제 풀이 Java 소스 코드

<MySQL & Oracle>

SELECT A.CATEGORY
     , A.PRICE AS MAX_PRICE
     , A.PRODUCT_NAME
  FROM (
         SELECT CATEGORY
              , PRICE
              , PRODUCT_NAME
              , RANK() OVER (PARTITION BY CATEGORY ORDER BY PRICE DESC) AS PRICE_RANK
           FROM FOOD_PRODUCT
          WHERE CATEGORY IN ('과자', '국', '김치', '식용유')
       ) A
 WHERE A.PRICE_RANK = 1
 ORDER BY A.PRICE DESC

프로그래머스 식품분류별 가장 비싼 식품의 정보 조회하기 SQL

<MySQL>

SELECT A.REST_ID
     , A.REST_NAME
     , A.FOOD_TYPE
     , A.FAVORITES
     , A.ADDRESS
     , ROUND(AVG(IFNULL(NULLIF(B.REVIEW_SCORE, ''), 0)), 2) AS SCORE
  FROM REST_INFO A
     , REST_REVIEW B
 WHERE A.REST_ID = B.REST_ID
   AND A.ADDRESS LIKE '서울%'
 GROUP BY A.REST_ID
 ORDER BY ROUND(AVG(IFNULL(NULLIF(B.REVIEW_SCORE, ''), 0)), 2) DESC, A.FAVORITES DESC

<Oracle>

SELECT A.REST_ID
     , A.REST_NAME
     , A.FOOD_TYPE
     , A.FAVORITES
     , A.ADDRESS
     , ROUND(AVG(NVL(B.REVIEW_SCORE, 0)), 2) AS SCORE
  FROM REST_INFO A
     , REST_REVIEW B
 WHERE A.REST_ID = B.REST_ID
   AND A.ADDRESS LIKE '서울%'
 GROUP BY A.REST_ID, A.REST_NAME, A.FOOD_TYPE, A.FAVORITES, A.ADDRESS
 ORDER BY ROUND(AVG(NVL(B.REVIEW_SCORE, 0)), 2) DESC, A.FAVORITES DESC

평균 계산 함수 AVG 사용 시 주의할 점

SCORE 값이 NULL이거나 빈 값일 경우 0으로 평균 계산에 포함시키려면

<MySQL> : IFNULL(NULLIF(컬럼, ''), 컬럼 값이 NULL이거나 빈 값일 경우 보여줄 값)

=> AVG(IFNULL(NULLIF(SCORE, ''), 0))

<Oracle> : NVL(컬럼, 컬럼 값이 NULL이거나 빈 값일 경우 보여줄 값)

=> AVG(NVL(SCORE, 0))

프로그래머스 서울에 위치한 식당 목록 출력하기 SQL

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	
	// 아이템 줍기
	
	public static int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
		int answer = 0;
		int[][] board = new int[101][101]; // 전체 영역
		boolean[][] visited = new boolean[101][101]; // 방문한 좌표인지 확인을 위한 2차원 boolean 배열
		int[] dx = {0, 0, -1, 1}; // 상, 하, 좌, 우 이동에서 x 좌표 증감 값
		int[] dy = {1, -1, 0, 0}; // 상, 하, 좌, 우 이동에서 y 좌표 증감 값
		
		// STEP 1. 모든 사각형의 모서리 영역과 내부 영역을 1로 채운다.
		for (int i = 0; i < rectangle.length; i++) {
			
			int[] eachRectangle = rectangle[i]; // 하나의 사각형 꼭지점 정보가 담긴 배열
			
			// 그림1의 문제를 해결하기 위해 모든 좌표 값의 크기를 2배로 해준다.
			for (int x = eachRectangle[0] * 2; x <= eachRectangle[2] * 2; x++) {
				
				for (int y = eachRectangle[1] * 2; y <= eachRectangle[3] * 2; y++) {
					board[x][y] = 1;
				}
			}
		}
		
		// STEP 2. 모서리 영역을 제외한 내부 영역을 0으로 채운다.
		for (int i = 0; i < rectangle.length; i++) {
			
			int[] eachRectangle = rectangle[i]; // 하나의 사각형 꼭지점 정보가 담긴 배열
			
			// 시작 꼭지점 좌표 + 1 ~ 마지막 꼭지점 좌표 - 1까지 0으로 채우면 사각형 내부 영역이 0으로 채워지게 된다.
			for (int x = eachRectangle[0] * 2 + 1; x <= eachRectangle[2] * 2 - 1; x++) {
				
				for (int y = eachRectangle[1] * 2 + 1; y <= eachRectangle[3] * 2 - 1; y++) {
					board[x][y] = 0;
				}
			}
		}
		
		// STEP 3. 캐릭터의 이동 정보를 담을 클래스 CharacterPosition에 캐릭터 초기값 세팅
		CharacterPosition characterPosition = new CharacterPosition(characterX * 2, characterY * 2, 0);
		
		// STEP 4. BFS 수행
		Queue<CharacterPosition> q = new LinkedList<>();
		
		q.add(characterPosition);
		
		visited[characterX * 2][characterY * 2] = true;
		
		while (!q.isEmpty()) {
			CharacterPosition tempCharacterPosition = q.poll();
			
			if (tempCharacterPosition.x == itemX * 2 && tempCharacterPosition.y == itemY * 2) { // 캐릭터가 아이템 위치에 도달했다면
				answer = tempCharacterPosition.moveCnt / 2;
				break;
			}
			
			for (int i = 0; i < 4; i++) { // 상, 하, 좌, 우 이동
				int nextX = dx[i] + tempCharacterPosition.x;
				int nextY = dy[i] + tempCharacterPosition.y;
				
				// 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다. 이 조건에 의해 2배 값인 2부터 100까지가 캐릭터의 이동 가능 범위가 된다.
				if (nextX < 2 || nextX > 100 || nextY < 2 || nextY > 100) {
					continue;
				}
				
				if (!visited[nextX][nextY] && board[nextX][nextY] == 1) { // 방문하지 않은 모서리 영역이라면
					q.offer(new CharacterPosition(nextX, nextY, tempCharacterPosition.moveCnt + 1));
					visited[nextX][nextY] = true;
				}
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] rectangle = {{1,1,7,4},{3,2,5,5},{4,3,6,9},{2,6,8,8}};
		int characterX = 1;
		int characterY = 3;
		int itemX = 7;
		int itemY = 8;
		
		// 전체 영역을 만들고, 모든 사각형의 모서리 영역과 내부 영역을 1로 채운 후, 내부 영역만 다시 0으로 채워 모서리에 남은 값 1을 따라서 좌표 이동을 하도록 만들면 된다.
		// 아래 그림1을 보면 서로 떨어져 있는 사각형이지만 두 모서리의 간격이 1이기 때문에 1을 따라서 좌표 이동을 할 경우 두 사각형이 붙어있는 것으로 인식하는 문제가 발생한다.
		// 모든 사각형의 좌표, 캐릭터의 좌표, 아이템의 좌표를 x2 하여 문제를 해결할 수 있다.
		// 이후 총 이동 거리에서 나누기 2를 해주면 된다.
		// int[][] rectangle = {{2,2,14,8},{6,4,10,10},{8,6,12,18},{4,12,16,16}};
		// int characterX = 2;
		// int characterY = 6;
		// int itemX = 14;
		// int itemY = 16;
		// 조건을 위와 같이 바꾼 후 문제를 풀고, 결과 값의 1/2을 답으로 제출하면 된다.
		
		System.out.println(solution(rectangle, characterX, characterY, itemX, itemY));
	}
}

public class CharacterPosition {
	int x = 0;
	int y = 0;
	int moveCnt = 0;
	
	public CharacterPosition(int x, int y, int moveCnt) {
		this.x = x;
		this.y = y;
		this.moveCnt = moveCnt;
	}
}

프로그래머스 아이템 줍기 문제 풀이 Java 소스 코드

<MySQL>

SELECT A.SALES_DATE
     , A.PRODUCT_ID
     , A.USER_ID
     , A.SALES_AMOUNT
  FROM (
         SELECT DATE_FORMAT(SALES_DATE, '%Y-%m-%d') AS SALES_DATE
              , PRODUCT_ID
              , USER_ID
              , SALES_AMOUNT
           FROM ONLINE_SALE
          WHERE DATE_FORMAT(SALES_DATE, '%Y-%m') = '2022-03'
      UNION ALL 
         SELECT DATE_FORMAT(SALES_DATE, '%Y-%m-%d') AS SALES_DATE
              , PRODUCT_ID
              , NULL AS USER_ID
              , SALES_AMOUNT
           FROM OFFLINE_SALE
          WHERE DATE_FORMAT(SALES_DATE, '%Y-%m') = '2022-03'
       ) A
ORDER BY A.SALES_DATE, A.PRODUCT_ID, A.USER_ID

<Oracle>

SELECT A.SALES_DATE
     , A.PRODUCT_ID
     , A.USER_ID
     , A.SALES_AMOUNT
  FROM (
         SELECT TO_CHAR(SALES_DATE, 'YYYY-MM-DD') AS SALES_DATE
              , PRODUCT_ID
              , USER_ID
              , SALES_AMOUNT
           FROM ONLINE_SALE
          WHERE TO_CHAR(SALES_DATE, 'YYYY-MM') = '2022-03'
      UNION ALL 
         SELECT TO_CHAR(SALES_DATE, 'YYYY-MM-DD') AS SALES_DATE
              , PRODUCT_ID
              , NULL AS USER_ID
              , SALES_AMOUNT
           FROM OFFLINE_SALE
          WHERE TO_CHAR(SALES_DATE, 'YYYY-MM') = '2022-03'
       ) A
ORDER BY A.SALES_DATE, A.PRODUCT_ID, A.USER_ID

<NULL 값을 먼저 또는 나중에 출력되도록 정렬 방법>

MySQL : ORDER BY 컬럼 IS NULL (ASC / DESC)

Oracle : ORDER BY 컬럼 (ASC / DESC) NULLS (FIRST / LAST)

프로그래머스 오프라인/온라인 판매 데이터 통합하기 SQL

<MySQL>

SELECT A.APNT_NO
     , B.PT_NAME
     , B.PT_NO
     , A.MCDP_CD
     , C.DR_NAME
     , A.APNT_YMD
  FROM APPOINTMENT A
     , PATIENT B
     , DOCTOR C
 WHERE A.PT_NO = B.PT_NO
   AND A.MDDR_ID = C.DR_ID
   AND DATE_FORMAT(A.APNT_YMD, '%Y-%m-%d') = '2022-04-13'
   AND A.APNT_CNCL_YN = 'N'
   AND A.MCDP_CD = 'CS'
 ORDER BY A.APNT_YMD

<Oracle>

SELECT A.APNT_NO
     , B.PT_NAME
     , B.PT_NO
     , A.MCDP_CD
     , C.DR_NAME
     , A.APNT_YMD
  FROM APPOINTMENT A
     , PATIENT B
     , DOCTOR C
 WHERE A.PT_NO = B.PT_NO
   AND A.MDDR_ID = C.DR_ID
   AND TO_CHAR(A.APNT_YMD, 'YYYY-MM-DD') = '2022-04-13'
   AND A.APNT_CNCL_YN = 'N'
   AND A.MCDP_CD = 'CS'
 ORDER BY A.APNT_YMD

프로그래머스 취소되지 않은 진료 예약 조회하기 SQL

public class Solution {
	
	// 피로도
	
	static int answer = 0;
	static boolean[] visited = {};
	
	public static void dfs(int depth, int k, int[][] dungeons) {
		
		for (int i = 0; i < dungeons.length; i++) {
			
			if (!visited[i] && dungeons[i][0] <= k) { // depth가 0 & 첫 번째 던전에서 dfs -> depth가 0 & 두 번째 던전에서 dfs -> depth가 0 & 세 번째 던전에서 dfs
				visited[i] = true; // 해당 던전을 방문한 상태에서 다음 depth로 dfs
				dfs(depth + 1, k - dungeons[i][1], dungeons); // depth가 1 & 위 3가지 각각의 경우에 대해 방문하지 않은 던전 dfs
				visited[i] = false; // 해당 던전으로의 dfs가 끝났으므로 다시 방문 전 상태로 변경
			}
		}
		
		answer = Math.max(answer, depth); // 몇 번째 depth까지 들어갈 수 있는지 확인
	}
	
	public static int solution(int k, int[][] dungeons) {
		visited = new boolean[dungeons.length];
		
		dfs(0, k, dungeons); // depth, 현재 피로도, 던전 배열
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int k = 80;
		int[][] dungeons = {{80,20},{50,40},{30,10}}; // 최소 필요 피로도, 소모 피로도 // {80,20} -> {30,10} -> {50,40} 가능
		
		System.out.println(solution(k, dungeons)); // 3
	}
}

프로그래머스 피로도 문제 풀이 Java 소스 코드