Yong's Tech Story

문제 풀이 (JAVA)

package algorithm;

import java.util.*;
public class part3_2 {

	public static void main(String[] args) {
		// 공통원소 구하기
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int [] arr1 =new int[N];
		for(int i=0; i<N; i++) {
			arr1[i]=input.nextInt();
		}
		int M = input.nextInt();
		int [] arr2 = new int[M];
		for(int i=0; i<M; i++) {
			arr2[i]=input.nextInt();
		}
		int [] answer = solution(N,arr1,M,arr2);
		for(int i=0; i<answer.length; i++) {
			System.out.print(answer[i]+" ");
		}
	}
	private static int [] solution(int N, int [] a, int M, int [] b) {
		List<Integer> list = new ArrayList<>();
		int p1 =0 , p2=0; // 투포인터 선언 
		// 오름차순 정렬
		Arrays.sort(a);  
		Arrays.sort(b);
		while(p1 < N && p2< M) { // 각 배열이 포인터가 끝을 바라보지 않는다면 
			if(a[p1] == b[p2]) {
				list.add(a[p1]);
				p1++; p2++;
			}else if(a[p1] < b[p2]) {
				p1++;
			}else if(a[p1] > b[p2]) {
				p2++;
			}
		}
		int [] result = new int[list.size()];
		for(int i=0; i< list.size(); i++) {
			result[i]=list.get(i);
		}
	
		return result;
	}
}

주요 핵심 포인트

1. 기존에는  for문으로 풀었으나 O(n2)번 비교하므로 효율성테스트에서 시간 초과 오류로 문제가 풀리지 않는다.

2. 투포인터 알고리즘의 핵심 개념인 2개의 포인터를 사용하여 O(n)번 탐색하도록 변경한다.

3. while문을 통해 포인터가 각배열의 끝을 가리키지 않는다면, 반복하여 탐색한다.

4. 숫자는 오름차순 정렬 되었으므로 각 숫자가 작을시 작은 배열의 포인터를 증가시킨다.

문제 풀이 (JAVA)

import java.util.*;
public class part2_10 {

	public static void main(String[] args) {
		// 봉우리
		Scanner input = new Scanner(System.in);
		
		int n = input.nextInt();
		
		int [][] numArr = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				numArr[i][j] = input.nextInt();
			}
		}
		int answer=solution(numArr, n);
		
		System.out.print(answer);

	}
	private static int solution(int [][] arr, int n) {
		int [] dx = {-1, 0, 1, 0};
		int [] dy = {0, 1, 0, -1};
		int answer=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				boolean flag=true;
				for(int k=0; k<4; k++) {
					int nx=i+dx[k];
					int ny=j+dy[k];
					if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny]>=arr[i][j]) {
						flag=false;
						break;
					}
				}
				if(flag) answer++;
			}
		}
		return answer;
	}
}

주요 핵심 포인트

1.  이차원 배열의 숫자가 왼쪽,오른쪽,위,아래 배열 숫자 중 가장 큰 수인지를 탐색하는 문제로, 키워드는 사면에 배열이 있을수도 있고 없을수도 있으므로, 존재하지 않는 행은 체크하지 않아야 한다.

2. 문제풀이의 핵심은 dx, dy 배열을 만들어 중앙값을 기준으로 (-1,0),(0,1),(1,0),(0,-1)이 존재할때에 탐색하도록 삼중 for문을 돌린다. 이차원 배열의 각 숫자를 사면으로 k번 비교하여 비교 숫자가 더 크면 flag는 false로 가장 큰 숫자가 아니게 된다따라서 각 배열의 숫자 flag가 변하지 않고 true 라면 봉우리이다.

3. nx , ny 값 범위를 잘 설정하여야 존재하는 배열만 탐색한다.