자료구조와 알고리듬 With Java/[프로그래머스] KDC

[3주차] Coding Test 해시 / BFS / DFS / 동적계획법

계란💕 2022. 5. 4. 18:14

1. 위장

java
열기

  Note) 

  - hash함수는 최대한 겹치지 않도록 유일한 값을 생성한다.

  - 해시의 자료구조 구성: 배열, 리스트, 탐색, 해시

  - map은 인터페이스이므로 생성할 수 없다. 따라서 이를 구현하는 HashMap을 만든다.

 

 

2. 게임 맵 최단거리

  - 에러 수정

java
열기

 

  - 오답

java
닫기
import java.util.*;

class Solution {

	static int MAX_COUNT = 101;
	static int [][] AdjMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int [][] VisitMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int Width; 
	static int Height;
	static int DIRECTION = 4;
	static int [][] DirMatrix = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<Integer> queueRow = new LinkedList<>();
	static Queue<Integer> queueCol = new LinkedList<>();
	static Queue<Integer> queueDis = new LinkedList<>();
	static int Distance = 0;
	static int answer = 0;
	static int flag = 0;

	    public static int solution(int[][] maps) {
	    	
	    	AdjMatrix = maps;
	    	VisitMatrix[1][1] = 1;
	    	queueRow.add(1);
	    	queueCol.add(1);
	    	queueDis.add(1);
	    	
	    	while(false == queueRow.isEmpty()) {
	    		int currRow = queueRow.poll();
	    		int currCol = queueCol.poll();
	    		int currDis = queueDis.poll();
	    		
	    		for(int i = 0; i < DIRECTION; ++i) {
	    			int nextRow = currRow + DirMatrix[i][0];
	    			int nextCol = currCol + DirMatrix[i][1];
	    			int nextDis = currDis + 1;
	    			answer = nextDis;
	    			if(1 == VisitMatrix[nextRow][nextCol]) continue;
	    			if(1 == AdjMatrix[nextRow][nextCol] &&
	    				1 <= nextRow && nextRow <= Height &&
	    				1 <= nextCol && nextCol <= Width) {
	    				if(5 == nextRow && 5 == nextCol) {
	    					flag = 1;
	    				}
	    				VisitMatrix[nextRow][nextCol] = 1;
	    		    	queueRow.add(nextRow);
	    		    	queueCol.add(nextCol);
	    		    	queueDis.add(nextDis);
	    		  //  	System.out.printf("[%d] (%d, %d)->(%d, %d)\n", nextDis, currRow, currCol, nextRow, nextCol);
	    			}
	    		}
	    	}
	    	if(0 == flag) {
                System.out.print(-1);
	    		return -1;
	    	}
	    	System.out.print(answer - 1);
            return (answer - 1);
	   
        }
}

  Note) 

  - 너비우선탐색, Queue를 이용한다.

  - Queue interface를 구현하는 LinkedList를 이용한다.

 

 

3. 올바른 괄호의 개수

  - "카탈랑 수"를 이용한다.

  - 재귀함수로 solution을 작성한다.

java
열기

 

 

4. 정수 삼각형

  - 위부터 계산

java
열기

  - 아래에서부터 위로 계산

java
열기

  Note) 

  - DynamicProgramming