JJJ

출발지(빨간색) → 도착지(파란색) 으로 가는 최단경로 구하기

import java.util.*;

public class Main {	
	
	// 이동방향
	static int[][] D = {
			{0,1},
			{0,-1},
			{1,0},
			{-1,0}
	};
	
	// MAP
	static int[][] matrix = {
		{0,0,0,0,0},
		{0,1,1,1,1},
		{0,0,0,0,0},
		{1,1,1,1,0},
		{0,0,0,0,0}
	};

	public static void main(String[] args) {				
		
		Scanner sc = new Scanner(System.in);
		// 출발지
		int sRow = sc.nextInt();
		int sCol = sc.nextInt();
		
		// 목적지
		int eRow = sc.nextInt();
		int eCol = sc.nextInt();
		
		System.out.println(bfs(sRow, sCol, eRow, eCol));
	}
	
	public static int bfs(int sRow, int sCol, int eRow, int eCol) {
		int m = matrix.length;	// 가로
		int n = matrix[0].length;	// 세로
		boolean[][] visit = new boolean[m][n];	// 방문체크
		Queue<Node> queue = new LinkedList<Node>();	// 탐색용 큐
		
		// 시작 Node 추가
		queue.add(new Node(sRow, sCol, 0));
		
		while(!queue.isEmpty()) {			
			Node node = queue.poll();	// 큐에서 꺼내서 확인
			int row = node.row;
			int col = node.col;
			int dist = node.dist;
			visit[row][col] = true;					
			
            // 실제 작업 : 현재 Node의 row,col이 eRow, eCol과 같아지면 도착지
			if(row == eRow && col == eCol) {
				return dist;
			}
			
			// 다음 노드 탐색
			for (int i = 0; i < 4; i++) {				
				int nRow = row + D[i][0];	// row이동
				int nCol = col + D[i][1];	// col이동
				if(nRow < 0 || nRow >= m || nCol < 0 || nCol >= n)	// MAP범위를 벗어나면 Skip
					continue;
				if(visit[nRow][nCol])	// 이미 방문했으면 Skip
					continue;
				if(matrix[nRow][nCol] == 1) // 벽이면 Skip
					continue;		
				
				queue.add(new Node(nRow, nCol, dist+1));
			}						
		}
				
		return -1;
    }
	
	// Node 클래스
	static class Node {
		int row;
		int col;
		int dist;
		
		public Node(int row, int col, int dist) {
			this.row = row;
			this.col = col;	
			this.dist = dist;
		}
		
	}
		
}

BFS참고 => https://www.youtube.com/watch?v=yQ7o1Y7X_Rg

class Solution {
	
	// 이동방향
	private static int[][] D = {{0,1}, {1,0}, {0,-1}, {-1,0}};
	
	// 노드 클래스
	static class Point{
		int row;
		int col;
		int dist;
		
		public Point(int row, int col, int dist) {			
			this.row = row;
			this.col = col;
			this.dist = dist;		
		}		
	}
	
	public static List<Integer> spiralOrder(int[][] matrix) {
        
		int m = matrix.length;		// 가로길이
		int n = matrix[0].length;	// 세로길이			
		int cnt = 0;	// 탐색횟수
		
		List<Integer> result = new ArrayList<Integer>();	// 결과
		boolean[][] visit = new boolean[m][n];	// 방문체크
		Queue<Point> queue = new LinkedList<Point>();	// 탐색용 큐
				
		queue.add(new Point(0, 0, 0));	// 시작 Point를 큐에 넣음 (0,0), 첫 이동은 D[0][0], D[0][1]
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();	// 큐에서 꺼내서 확인
			int row = point.row;
			int col = point.col;			
			int dist = point.dist;
			
			visit[row][col] = true;	// 방문체크
			
            // 실제 작업 : 결과입력
            result.add(matrix[row][col]);
            cnt++;
			if(cnt == m * n) break;
			
			// 우선 이전 방향으로 이동해봄
			int nRow = row + D[dist][0];
			int nCol = col + D[dist][1];			
			if(nRow < 0 || nRow >= m || nCol < 0 || nCol >= n || visit[nRow][nCol]) {	
                // 범위를 벗어나거나 이미 방문했다면, 새로운 방향으로 이동
				dist++;
				if(dist == 4) dist = 0;
				nRow = row + D[dist][0];
				nCol = col + D[dist][1];
			}
			queue.add(new Point(nRow, nCol, dist));			
		}
						
		return result;
    }
}

- while안쪽에서 문제에서 요구하는 내용에 따하서 구현하는 내용이 다를 수 있음

- 이 문제에서는 값을 읽어서 result라는 ArrayList에 넣는 것이 요구사항

- while을 종료하기 위한 탐색 종료 시점을 확인해야 함 (모든 노드 탐색 완료, 목적지 도착 완료 등)

- 이동을 하는 방식도 문제마다 다를 수 있음

- 이 문제에서는 달팽이모양 방향을 요구하여서, Point클래스의 dist에 이동 방향에 대한 정보를 둠

- 이전에 사용한 방향으로 먼저 가보고, 아니면 다른 방향을 선택하도록 구현함

carry가 없으면 간단하지만, carry가 생기는 경우를 생각해야 함

9로만 되어 있는 경우에는 자릿수가 하나 늘어나도 첫 번째 digit만 1이고 나머지는 0일 것임

{9,9,9,9} => {1,0,0,0,0}

class Solution {
    public int[] plusOne(int[] digits) {        
		int n = digits.length;				
		for (int i = n-1; i >= 0; i--) {
			if(digits[i] == 9) {
				digits[i] = 0;
				
				if(i == 0) {
					digits = new int[digits.length + 1];
					digits[0] = 1;
					return digits;
				}
			} else {
				digits[i]+=1;
				return digits;
			}
		}		
		return digits;
    }
}

class Solution {
    public int[] plusOne(int[] digits) {
        int dex = digits.length - 1;
        for(int i = dex; i>=0;i--){
            digits[i]++;
            digits[i] = digits[i] % 10;
            if(digits[i] != 0){
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

class Solution {
    public int dominantIndex(int[] nums) {
        
        if(nums.length == 1) return 0;
        
        int result = -1;
		int max = 0;
		int maxIndex = 0;				
		
		for (int i = 0; i < nums.length; i++) {
			if(max < nums[i]) {
				max = nums[i];
				maxIndex = i; 
			}
		}		
		
		for (int i = 0; i < nums.length; i++) {
			if(maxIndex == i)
				continue;
			
			if(max >= nums[i] * 2)
				result = maxIndex;
			else
				return -1;
		}
		
        return result;
    }
}

나머지 것들의 2배값이 최대값보다 커지면 바로 끝내버려야 함

class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        int lSum = 0;
        
        for(int num : nums)
        	sum += num;
        
        for (int i = 0; i < nums.length; i++) {
			if(lSum == sum - lSum - nums[i])
				return i;

			lSum += nums[i];
		}
        return -1;
    }
}

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
		
		for (int i = 0; i < nums.length; i++) {
			if(list.contains(nums[i]))
				continue;
			else
				list.add(nums[i]);
		}
		
		for (int i = 1; i <= nums.length; i++) {
			if(list.contains(i)) {
				list.remove(list.indexOf(i));
			}else {
				list.add(i);
			}
		}			
		
		return list;	
    }
}

이 방법은 Time Limit Exceeded

그래서, HashMap사용 (HashMap의 containsKey는 O(1)이라고 함)

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		List<Integer> list = new ArrayList<Integer>();
		
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], nums[i]);
		}
		for (int i = 1; i <= nums.length; i++) {
			if(!map.containsKey(i))
				list.add(i);
			else
				continue;
		}		
		return list;		
    }
}

https://soft.plusblog.co.kr/74

class Solution {
    public int maxArea(int[] height) {
        int maxWater = 0;        
		
        for (int i = 0; i < height.length - 1; i++) {
			for (int j = i+1; j < height.length; j++) {								
				int water = (j - i) * Math.min(height[i], height[j]);
				if(maxWater < water)
					maxWater = water;
			}
		}		
		return maxWater;
    }
}

그냥 for를 활용한 브루트포스로 하면 풀리긴 하는데, 시간초과

역시, Two Pointer를 사용하면 되는데, 인덱스를 옮겨가면서, 탐색을 하는 방법을 찾는게 어려웠음

맨 처음 가장 넓은(0 ~ height.length-1)너비에서 그 다음으로 가면 너비가 점점 줄어드는데, 총 용량이 늘어나려면 높이가 큰 막대를 찾아야 함

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxWater = 0;
        
        while(left < right) {        	
        	maxWater = Math.max((right - left) * Math.min(height[left], height[right]), maxWater);
        	if(height[left] < height[right]) {
        		left++;
        	}else {
        		right--;
        	}
        }        
        return maxWater;
    }
}

Move Zeroes 와 동일한 문제로 Two Pointer로 풀이

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int i = 0;
		for (int j = i+1; j < nums.length; j++) {
			if(nums[i] % 2 != 0) {
				if(nums[j] % 2 != 0) {
					continue;
				}else {
					int tmp = nums[j];
					nums[j] = nums[i];
					nums[i] = tmp;					
				}				
			}
			i++;
		}				
		return nums;
    }
}

Two Pointer로 풀이

class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0;
		
		for (int j = i+1; j < nums.length; j++) {
			if(nums[i] == 0) {
				if(nums[j] == 0) {
					continue;
				}else {
					int tmp = nums[j];
					nums[j] = nums[i];
					nums[i] = tmp;					
				}
			}
			i++;
		}
    }
}

class Solution {
    public int[] replaceElements(int[] arr) {
        int rightMax = 0;		
		
		for (int i = 0; i < arr.length - 1; i++) {
			
			for (int j = i+1; j < arr.length; j++) {
				if(rightMax < arr[j])
					rightMax = arr[j];				
			}			
			arr[i] = rightMax;
			rightMax = 0;											
		}		
		arr[arr.length - 1] = -1;
				
		return arr;
    }
}