Pccp 준비하기 - 4 투포인터와 메모리 효율적인 방법 고민하기

이번에 투포인터 문제와 bfs를 메모리와 시간 효율을 생각해서 사용하는 문제를 풀어보고
메모리와 시간을 철저하게 검사해야하는구나...를 제대로 느꼈습니다.

그래서 이 2문제를 각각 무슨 알고리즘을 왜 사용했고 어떻게 코드로 활용했는지 정리했습니다

연속된 부분 수열의 합

문제링크!!

문제에 사용한 알고리즘

이 문제는 비내림차순 즉 이미 오름차순 정렬이 되어있던 문제였습니다.
그리고 각 부분을 돌면서 k값에 맞는 가장 짦은 부분수열을 찾는 것이었는데

만약 이중 for문을 사용한다면 1000000 * 1000000 이어서 시간 초과였습니다
그래서 투포인터를 사용해 nlogn만큼만 돌렸습니다

left와 right라는 변수를 활용해서 k값이 넘어가지 않으면 right가 증가,
k값을 넘길 시 left를 빼주고 한칸 옮깁니다! -> 즉 그 부분은 제외!

문제를 어떻게 코딩했는지

class Solution {
	public int[] solution(int [] sequence, int k) {
    	int answer[] = new int[2];
        int sLeft = 0;
        int sRight = 0;
        int range = 1000001;
        int left = 0;
        int right = -1;
        int N = sequence.length;
        int sum = 0;
        
        while (right < N) {
        	if (sum < k) {
            	if (++right < N) {
                	sum += sequence[right];
                }
            }
            else if (sum > k) {
            	sum -= sequence[left++];
            } else {
            	// sum == k
                if (range > (right - left)) {
                	range = right - left;
                    sLeft = left;
                    sRight = right;
                }
                sum -= sequence[left++];
            }
        }
        answer[0] = sLeft;
        answer[1] = sRight;
        return answer;
    }
}

석유 시추

석유시추 문제 분석

석유시추 문제 링크!!

이 문제는 정확성과 효율성 테스트가 추가로 있는 문제였습니다.
그래서 단순 이중 for문으로 풀 수 있어도 효율에서 정답이 아니게 됩니다.

석유시추에 사용한 알고리즘과 효율성

이 문제는 가로를 각각 돌아다니면서 어디가 가장 많은 석유를 가지고 있는지 보는 문제입니다.
이때 매번 가로를 돌때마다 석유의 양을 찾기 위해 bfs를 사용할 수도 있지만 이렇게 된다면 시간 효율이 매우 떨어지게 됩니다

그렇기에 해쉬맵을 사용해서 석유의 양을 각 부분마다 저장한 뒤 가로를 돌때 해쉬맵에서 데이터를 꺼내오는 방식으로 효율성을 지켰습니다.

석유시추 코드

import java.util.*;

class Solution {
	static int dy[] = {-1,1,0,0};
    static int dx[] = {0,0,-1,1};
    static int[][] fragments;
    static boolean[][] visited;
    static int fragmentIdx = 1;
    static int N,M;
    static HashMap<Integer, Integer> map = new HashMap<>();
    
    public int solution(int [][] land) {
    	int answer = 0;
        N = land.length;
        M = land[0].length;
        fragments = new int[N][M];
        visited = new boolean[N][M];
        
        // 미리 각 부분의 석유 양 지정하기
        for (int i < 0; i < N; i++) {
        	for (int j < 0; j< M; j++) {
            	if(land[i][j] == 1 && visited[i][j] == false) {
                	initFragment(land, i,j);
                }
            }
        }
        
        // 이제 가로를 돌면서 가장 석유양 많은 애 구하기
        for (int c = 0; c < M; c++) {
        	Set<Integer> set = new HashSet<>();
            int tmp = 0;
            for (int r = 0; r < N; r++) {
            	if (land[r][c] == 1) {
                	set.add(fragments[r][c]);
                }
            }
            for (int s : set) {
            	tmp += map.get(s);
            }
            answer = Math.max(answer, tmp);
        }
        return answer;
    }
    static void initFragment(int[][] land, int r, int c) {
        int size = 1;
        Queue<int[]> frg = new LinkedList<>();
        visited[r][c] = true;
        fragments[r][c] = fragmentIdx;
        frg.add(new int[]{r,c});
        
        while (!frg.isEmpty()) {
            int arr[] = frg.poll();
            int y = arr[0];
            int x = arr[1];
            
            for (int d = 0; d < 4; d++) {
                int drtR = dy[d] + y;
                int drtC = dx[d] + x;
                
                if (0 <= drtR && drtR < N
                   && 0 <= drtC && drtC < M 
                   && visited[drtR][drtC] == false
                    && land[drtR][drtC] == 1) {
                    
                    visited[drtR][drtC] = true;
                    fragments[drtR][drtC] = fragmentIdx;
                    frg.add(new int[]{drtR, drtC});
                    size++;
                }
            }
        }
        map.put(fragmentIdx++, size);
    }
}