[Java 알고리즘] (2) 해시, BFS/DFS, Stack, DP

1. 위장 - 해시 [키와 값을 이용한 자료구조]

2. 게임 맵 최단거리 - BFS/DFS [너비우선탐색/깊이우선탐색]

3. 올바른 괄호의 개수 - Stack

4. 정수 삼각형 - DP [동적 프로그래밍]

 

---

1. 위장 - 해시

: 키와 값을 이용한 자료구조로, 검색에 특화된 자료구조이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

조건

1. 종류별로 존재하는 위장 용품

2. 착용할 수도 있고, 착용안할 수도 있는 위장 용품

3. 전체 조합의 경우의 수 = 서로 곱하는 경우 -1

 

즉, 종류별로 개수를 카운트하는 것이 목적

종류의 개수가 주어지는 경우 : 배열을 통한 인덱스 이용

종류의 개수가 주어지지 않는 경우 : 키와 값으로 이루어진 해시 이용

 

문제 풀이 순서

1. 해시맵 구현 오브젝트 <위장 용품 종류, 위장 용품 개수> 생성
2. 자료구조에 삽입
   • map.put(type, map.getOrDefault(type, 0)+1);
3. 전체 경우의 수 구하기
   1. 곱하기 위해서, anwer=1로 변경
   2. 전체 경우의 수이므로, +1해서 곱한다 (착용 / 미착용)
   3. 모두 안입는 경우도 존재하므로 마지막에 -1

 

(1) map을 이용한 풀이

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        
        //키와 값을 이용한 해시맵 자료구조 인터페이스 구현
        Map<String, Integer> counts= new HashMap<>();
        int answer = 1;
        
        //1. 위장 용품을 돌면서, 해당 위장 용품의 이름을 자료구조에 삽입
        for(String[] c: clothes){
            String type = c[1];
            //counts.put(type, counts.get(type)==null ? 0 : counts.get(type)+1);
            counts.put(type, counts.getOrDefault(type,0)+1);
        }
        
        
        //2. 모든 경우의 수를 구하기 위해서, answer에 +1해서 곱한다. (입거나, 안입거나)
        for(Integer c :counts.values()){
            answer*=c+1;
        }
        
        return answer-1;
        //모두 안입는 경우도 존재하므로 그 경우는 제외해서 반환
    }
}

(2) 스트림을 이용한 풀이

import java.util.*;
import java.util.stream.*;
class Solution {
    public int solution(String[][] clothes) {
        
        //키와 값을 이용한 해시맵 자료구조 인터페이스 구현
        int answer =
        
        //1. 위장용품 배열을 스트림으로 중복을 제거하고 생성해, 해당 요소를 위장용품의 이름으로 변환 
        //2. 해당 위장 용품과 같은 종류의 개수를 구해서 변환 (형변환 필요)
        //3. 개수에 +1 후, 모두 곱해서 총 조합의 개수를 구해서 변환 (착용 /미착용)
        //4. 최종연산으로 스트림의 요소를 하나씩 줄여가면서, 누적연산하는데
        //   : 초기값 1, 요소들을 모두 곱한다.
        Arrays.stream(clothes)
            //clothes[i][1]을 스트림의 요소로 변환
            .map(c->c[1])
            .distinct()    
            //위장 용품 종류가 같은 개수 구하기
            //: 이름을 기준 같은 타입인 요소만 필터링해서 개수를 요소로 변환
            //Arrays.stream(clothes).filter(c -> c[1].equals(type)).count()
            .map(type 
                 -> (int) Arrays.stream(clothes).filter(c -> c[1].equals(type)).count())
            .map(c->c+1)
            .reduce(1, (c, n) -> c*n);
    
        return answer-1;
        //모두 안입는 경우도 존재하므로 그 경우는 제외해서 반환
    }
}

---

2. 게임 맵 최단거리 - BFS/DFS

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

Pos클래스 정의

(1) x, y 좌표를 갖는 객체 생성

(2) 해당 좌표가 올바른 좌표인지 확인하는 메서드 정의

 

문제 풀이 순서

1.  DS
   1. 맵의 높이 변수와 맵의 너비 변수
   2. 현재 위치 객체를 받는 큐
   3. 이동한 거리를 저장하는 배열
   4. 지나간 위치인지 확인하는 boolean 배열
2. 초기값 설정
   1. 최초 시작 위치를 큐에 넣는다.(0,0)
   2. 최초 시작 위치에 이동거리를 1로 설정
   3. 최초 시작 위치에 지나간 위치로 설정
3. 큐가 빌때 까지 반복
   1. 현재 위치에서 이동한 거리를 가지고 있는 변수
   2. 이동할 경우의 수를 담는 정적 배열 [변하지 않는 상수 배열]
   3. 이동 경우의 수를 모두 확인
      1. 이동가능한 위치인가
      2. 지나간 위치인가
      3. 벽인가
   4. 이동한 거리를 담고 있는 변수에 +1해서 이동한 거리 배열에 저장
   5. 지나간 위치라고 설정
   6. 현재 객체를 큐에 저장
4. 가장 마지막 위치에 도달한 값을 answer에 저장하고, 0일 경우 -1 리턴

 

 

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

class Pos {
	public int x, y;

	Pos(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 >= height)
			return false;
		return true;
	}
}

class Solution {
	

	public int solution(int[][] maps) {
		int mapHeight = maps.length;
		int mapWidth = maps[0].length;

		// BFS :Queue
		Queue<Pos> q = new LinkedList<>();
		// 현재 위치 객체를 받는 큐

		// 거리를 저장하는 배열
		int[][] count = new int[mapHeight][mapWidth];

		// 지나간 위치인지 확인하는 배열
		boolean[][] visited = new boolean[mapHeight][mapWidth];

		// 초기값 설정
		q.offer(new Pos(0, 0));
		count[0][0] = 1;
		visited[0][0] = true;

		while (!q.isEmpty()) {
			Pos c = q.poll();

			// 현재 위치
			int currentCount = count[c.y][c.x];

			// 4가지 경우
			final int[][] moving = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
			for (int i = 0; i < moving.length; i++) {
				Pos moved = new Pos(c.x + moving[i][0], c.y + moving[i][1]);
				if (!moved.isValid(mapWidth, mapHeight))
					continue;
				if (visited[moved.y][moved.x])
					continue;
				if (maps[moved.y][moved.x] == 0)
					continue;

				count[moved.y][moved.x] = currentCount + 1;
				visited[moved.y][moved.x] = true;
				q.offer(moved);
			}

			// -> 메서드를 이용해 확인하도록 변경
		}
		int answer = count[mapHeight - 1][mapWidth - 1];
		if (answer == 0)
			return -1;
		return answer;
	}
}

 

 

 

---

3. 올바른 괄호의 개수 - Stack

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

package twoWeek;

import java.util.Stack;

class P{
	public int open, close;
	P(int open, int close){
		this.open=open;
		this.close=close;
	}
}

public class TwoWeek03_T {
	public static void main(String[] args) {
		
	}
	public int solution(int n) {
		//DFS - stack이용
		int answer=0;
		
		Stack<P> stack = new Stack<>();
		stack.push(new P(0,0));
		//스택에 초기값 삽입
		
		while(!stack.isEmpty()) {
			P p = stack.pop();
			
			//종료 조건 설정
			//1. 올바른 괄호
			if(p.open>n) continue;
			if(p.open<p.close) continue;
			
			//2. 괄호의 개수가 n개 쌍
			if(p.open+p.close==2*n) {
				answer++;
				continue;
			}
			
			stack.push(new P(p.open+1, p.close));
			//초기값에서 열린괄호 증가시켜서 삽입
			stack.push(new P(p.open, p.close+1));
			//열린괄호 증가 시킨 후에 닫힌 괄호 증가시켜서 삽입
			
		}
		
		
		return answer;
	}

}

 

---

4. 정수 삼각형 - DP

https://school.programmers.co.kr/learn/courses/30/lessons/43105

package twoWeek;

public class TwoWeek04_R {
	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++) {

				// 케이스 분류
				// 1. 오른쪽만 존재하는 경우
				// 2. 왼쪽 오른쪽 둘다 존재하는 경우
				// 3. 왼쪽만 존재하는 경우

				// 1. 오른쪽만 존재하는 경우
				if (j == 0)
					triangle[i][j] = triangle[i][j] + triangle[i - 1][j];
				// 3. 왼쪽만 존재하는 경우
				else if (i == j)
					triangle[i][j] = triangle[i][j] + triangle[i - 1][j - 1];
				// 2. 현재 위치에서 윗줄의 -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;
	}

}

 

package twoWeek;

public class TwoWeek04_BottomUp {
	public int solution(int[][] triangle) {
		int answer=0; //max
		
		for(int i=triangle.length-1;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 answer;
	}

}