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

1. 위장

<hide/>
import java.util.*;
class Solution {
    public static int solution(String[][] clothes) {
	    Map<String, Integer> map = new HashMap<>();
        int answer =  Arrays.stream(clothes)    // 모든 옷의 종류에 대해
            .map(c->c[1])   // 각 type은 1번 index에 있는 값이다. (종류만 얻어와서)
            .distinct()     // 중복을 제거한다. (타입을 얻어 온다.)
            .map(type -> (int) Arrays.stream(clothes).filter(c-> c[1].equals(type)).count())    
            // 타입에 해당하는 것들만 필터링해서 카운트 얻어 온다.
            .map(c -> c + 1) 
            // 타입 별로 얻어온 값에 1을 더해준다.
            .reduce(1, (c, n) -> c * n);
	        return answer - 1;
	    }	
}

  Note) 

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

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

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

 

 

2. 게임 맵 최단거리

  - 에러 수정

<hide/>
import java.util.*;
class Solution {
    class Position{
        int x, y;
        
        Position(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        boolean isValid(int width, int height){
            if(x < 0 || x >= width) return false;
            if(y < 0 || y >= width) return false;
            return true;
        }
    }
    
    public int solution(int[][] maps) {
        
        int mapHeight = maps.length;
        int mapWidth = maps[0].length;
        
        Queue<Position> queue = new LinkedList<>();
        int[][] count = new int[mapHeight][mapWidth];
        boolean[][] visited = new boolean[mapHeight][mapWidth];
        
        queue.offer(new Position(0, 0));        // 초깃값
        count[0][0] = 1;
        visited[0][0] = true;
        
        while(!queue.isEmpty()){
            Position current = queue.poll();
            int currentCount = count[current.y][current.x];
            
            final int[][]  moving = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
            for(int i = 0; i < moving.length; ++i){
                Position moved = new Position(current.x + moving[i][0], current.y + moving[i][1]);
                if(!moved.isValid(mapWidth, mapHeight)) continue;
                if(true == visited[moved.y][moved.x]) continue;
                if(0 == maps[moved.y][moved.x]) continue;
                    
                count[moved.y][moved.x] = currentCount + 1;
                visited[moved.y][moved.x] = true;
                queue.offer(moved);
            }
        }
        
        int answer = count[mapHeight-1][mapWidth-1];
        if(0 == answer) return -1;
        
        return answer;
    }
}

 

  - 오답

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을 작성한다.

<hide/>
import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        if(1 == n || 0 == n){
            return 1;
        }
        for(int i = n - 1; i >= 0 ; --i){
            answer += solution(i) * solution(n - 1 - i);
        }
        return answer;
    }
}

 

 

4. 정수 삼각형

  - 위부터 계산

<hide/>
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        for(int i = 1; i < triangle.length; ++i){
            for(int j = 0; j < triangle[i].length; ++j){
                if(j == 0){			// 가장 첫번째 열
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j];
                }else if(i == j){	// 가장 오른쪽 열
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
                }else{
                    int left = triangle[i][j] + triangle[i-1][j-1];
                    int right = triangle[i][j] + triangle[i-1][j];
                    triangle[i][j] = Math.max(left, right);
                }
                answer = Math.max(answer, triangle[i][j]);
            }
        }
        return answer;
    }
}

  - 아래에서부터 위로 계산

<hide/>
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for(int i = triangle.length - 2; i >= 0 ; --i){
            for(int j = 0; j < triangle[i].length; ++j){
                    int left = triangle[i][j] + triangle[i+1][j];
                    int right = triangle[i][j] + triangle[i+1][j+1];
                    triangle[i][j] = Math.max(left, right);
            }
        }
        return triangle[0][0];
    }
}

  Note) 

  - DynamicProgramming