[Java 기본 알고리즘] (3) Array

package ArrayBasic;

import java.util.HashMap;
import java.util.Map;

public class Array1 {
	public static void main(String[] args) {
		Array1 a = new Array1();
		int[] nums= {2,8,11,14};
		int target = 16;
		int[] result = a.solve_for(nums, target);
		for(int i:result) {
			System.out.println(i+" ");
		}
	}
	//두개 합
	//배열에서 두 숫자 값을 더해 타겟값과 같을 경우 두 숫자의 인덱스를 리턴
	//각 입력에 정확히 하나의 솔루션이 있다고 가정하고, 동일한 요소를 두 번 사용 불가
	//문제 해결
	//1. for를 돌려 타겟과 비교
	//2. 만약 for문을 두번 돌린다면, for문 -> X, for문 -> Y이면, X+Y가 타겟을 찾으면 된다.
	//3. for문을 하나로 만들기 위해서는, for문에 Map이나 배열을 사용해야한다.
	//-> Map(숫자, 방번호)를 이용해 방번호만 리턴하는 int[]를 만든다.
	//즉, Array+Map을 이용
	
	//타겟이 16이고, {2, 8, 11, 14}일 경우
	//Key, Value
	//14	방번호0
	//8		방번호1
	//5		방번호2
	
	//O(n^2) : 이중 for문
	public int[] solve_for(int[] nums, int target) {
		//길이 변수
		int len = nums.length;
		
		for(int i=0; i<len; i++) {
			for(int j=i+1; j<len; j++) {
				if(target == nums[i]+nums[j]) { //2-> 8,11,14 / 8-> 11,14, / 11 -> 14
					return new int[] {i+1,j+1}; //반드시 하나가 존재한다고 했으므로, 예외처리 안해도 된다.
					//0번방과 3번방이지만, 1번 4번으로 출력하기 위해 +1
				}
			}
		}
		return new int[] {0,0}; //존재하지 않을때 비어있는 배열 반환
	}
	
	//O(n) 
	public int[] solve(int[] nums, int target) {
		//1. ds
		int[] result = new int[2];
		Map<Integer, Integer> map = new HashMap<>();
		
		//2. for
		for(int i=0; i<nums.length; i++) {
			if(map.containsKey(nums[i])) {
				//14가 들어온 순간에
				int val = map.get(nums[i]); //방번호 0번호 반환
				result[0] =val+1;			//0번방에는 방번호 +1 1번 설정
				result[1]=i+1;				//1번방에는 현재 인덱스 설정
			}else {
				map.put(target-nums[i], i); //14	방번호0
				//타겟이 16이고, {2, 8, 11, 14}일 경우
				//Key, Value
				//14	방번호0
				//8		방번호1
				//5		방번호2
			}
		}
		return result;
	}
	
}

 

 

package ArrayBasic;

import java.util.Stack;

public class Array2 {
	public static void main(String[] args) {
		int[] nums = {73,74,75,71,69,72,76,73};
		
		int[] res = solve_1(nums);
		
		System.out.println("====result====");
		for(int i:res) {
			System.out.println(i+" ");
		}
	}
	//일일온도
	//일일 온도를 나타내는 int 배열에서 더 따뜻한 날씰르 얻기위해 기다려야하는 날짜 수를 배열로 리턴
	//더 따뜻한 날이 오지 않으면 0 리턴
	
	//문제해결
	//-> 기준 대상에서 날짜 세기 -> ~일 후 (온도)
	//1.for문을 돌리고, 해당 온도와 온도 비교 후 인덱스 차이를 결괏값에 저장
	//2.더 높은 온도가 나오면, 그 온도를 기준으로 다시 for문을 돌린다.
	//즉, 이중for문이 필요
	//while문을 이용할 경우 -> 해당 온도보다 높은 온도가 나올때가 탈출조건이며
	//while문을 빠져나오는 시점이 max-i가 된다 -> 해당 온도의 인덱스를 i에 저장, Max온도의 인덱스를 max에 저장
	
	//1. for문 돌리면서 0번방부터 스택에 저장
	//2. 1번방 만나서 비교					-> peek() 이용 (최상단과 비교 후 최상단과 교체)
	//3. 만나는 시점에 인덱스의 차이를 결과에 저장	-> 인덱스의 차이을 저장
	
	//1. 이중 for문
	public static int[] solve_1(int [] tem) {
		
		//1. ds
		int len = tem.length;
		int[] result = new int[len];	//배열의 길이만큼의 결과값 배열
		int count=0, j;
		
		//2. for
		for(int i=0;i<len;i++) {
			for(j=i+1;j<len-1;j++)	//i보다 한칸앞에서부터 시작해서 len보다 한칸전까지
			{
				if(tem[i]<tem[j]) {
					count++;
					break;
				}else {
					count++;
				}
			}
			if(j==tem.length)
				result[i]=0;		//따뜻한 날이 오지 않기 때문에
			else
				result[i]=count;	//따뜻한 날이 오기만 한다면 count를 넣어준다->count 누적안되게 초기화
			count=0;
		}
		return result;
	}
	//2. stack
	public static int[] solve_stack(int[] temper) {
		//1. ds
		int len = temper.length;
		int[] result = new int[len];		//배열의 길이만큼의 결과값 배열
		Stack<Integer> stack=new Stack<>();	//Stack<>-Stack<>();
		
		for(int i=0;i<len; i++) {
			
			while(!stack.isEmpty()&&temper[stack.peek()] <temper[i])
				//NULL체크하고 stack의 최상단이 배열보다 작을때까지 반복
			{
				//최상단보다 다음 배열이 더 클때 -> 인덱스 추출
				int index=stack.pop();	//stack의 인덱스기때문에 0번
				result[index]=i-index;	//1-0
			}
				
			stack.push(i); //0
		}
		return result;
	}//차곡차곡 쌓이는 경우 -> 앞의 배열과 다음 배열과 비교해야할 경우 -> 스택 사용
}

 

 

package ArrayBasic;

public class Array3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		// int[] nums= {-30, -20, -10,10};
		// int[] nums= {10,10,-3,10,10,};
		int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		System.out.println("Maximum Subarray : "+solve(nums));

	}
	// SubArray 최댓값
	// 배열에서 합계가 가장 큰 연속 하위 배열 (최소한 하나의 숫자 포함)을 찾아 합계를 리턴

	// 문제 해결 [1] -> Math.Max함수 이용
	// -> 하나씩 배열에 추가하면서 그이전의 max값과 비교
	// 문제 해결 [2] -> Math.Max함수 두번 이용
	// -> 작아질경우 값을 버리는 방법

	// (1) 부분에 대한 max값 -> [누적 or 새로운 값]
	// (2) 전체에 대한 max값
	// Max(i번에서 구한 값, 전체 누적값) -> curMax= Math.max(nums[i], curMax+nums[i])
	// Max(처음부터 누적한 값, 현재값) -> allMax= Math.max(allMax, curMax)
	// 두 가지 모두 사용해 문제 해결

	// 즉, 최소한 하나의 숫자가 필요하므로
	// 다음 배열에 나올 값을 추가할 때, 앞의 배열을 버리고 새로 시작할지, 추가할지 결정 -> 대소비교

	public static int solve(int[] nums) {

		// 1. -2를 뽑았을때
		int curMax = nums[0];
		int allMax = nums[0];

		// 2. -2를 뽑았을때를 가정해서 for문 돌리기
		for (int i = 1; i < nums.length; i++) {
			System.out.println("nums["+i+"] "+nums[i]+" nums["+i+"] "+"+curMax: "+(nums[i]+curMax));
			
			// 누적값과 현재값을 비교해 -> 현재값이 큰 경우 현재값 선택
			curMax = Math.max(nums[i], nums[i] + curMax); // 1, 1+-2 -> 1선택
			allMax=Math.max(allMax, curMax);
			
			System.out.println("curMax: "+curMax+" allMax: "+allMax);
			System.out.println("  ");
		}
		return allMax;
	}

}

 

 

package ArrayBasic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Array4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] list= {"eat", "tea", "tan", "ate", "nat", "bat" };
		System.out.println(solve(list));
		System.out.println(solve_ascii(list));
	}
	//그룹 아나그램
	//다른 문자열과 아나그램 관계를 갖는 주어진 문자열 배열에서 문자열 순서와 상관없이 같은 아나그램을 리턴
	
	//아나그램은 문자의 단어를 재배열해 새로운 문자를 형성하는 것
	//같은 알파벳으로 구성된 단어끼리 묶어 출력
	
	//문제 해결
	
	//1. 키값을 고유하게 만들기 	-> for loop를 이용, 한개의 String을 기준으로 toCharArray 이용해 sort후 키로 이용
	//-> 혹은 26개의 알파벳배열을 만들어 아스키코드를 이용해 고유한 키값을 만든다.
	
	//2. Map을 이용 -> Key에 해당하는 값들을 리스트로 만들기
	//Key Value
	//aet ate, eat, tea
	//ant nat, tan
	//abt bat
	
	//1. sort 이용하는 방법
	public static List<List<String>> solve(String[] strs){
		//1. ds
		List<List<String>> result = new ArrayList<>();
		if(strs==null || strs.length==0) {
			return result;
		}
		Map<String, List<String>> map = new HashMap<>();
		
		//2. for
		for (String str : strs){
			char[] charArr = str.toCharArray();
			Arrays.sort(charArr);	//['a','e','t']
			//chararr을 String으로 Map에 저장하기 위해 캐스팅
			String key = String.valueOf(charArr);
			System.out.println("key "+key);
			
			//String을 Map에 넣기 -> map.getOrDefault(key,null)함수로 대체 가능
			if(map.containsKey(key)) {	//Map에 키가 있을 때
				map.get(key).add(str);	//Map에서 키를 꺼내서 str 넣기
			}else {						//Map에 키가 없을 때
				List<String> list = new ArrayList<>();
				list.add(str);			//List에 str 넣기
				map.put(key, list);		//Map에 Key와 list 넣기
			}
			//List<String> list = map.getOrDefault(key, new ArrayList<>());
			//list.add(str);
			//map.put(key, list);
		}
		
		//리턴하는 방법 세가지
		// result.addAll(map.values());
		
//		return new ArrayList<>(map.values());
		//map.value가 List<String>이기 때문에 List<List<String>>으로 만들어 List 타입으로 ArrayList를 만들어 리턴
		
		for(Map.Entry<String, List<String>> entry : map.entrySet()) {
			result.add(entry.getValue());
		}
		return result;
	}
	
	//2. sort 이용하지 않는 방법
	public static List<List<String>> solve_ascii(String[] strs){
		Map<String, List<String>> map =new HashMap<>();
		List<List<String>> result = new ArrayList<>();
		
		for(String str : strs) {
			int[] count=new int[26];				//알파벳개수만큼의 배열 만들기
			for(int k=0; k<str.length();k++) {
				count[str.charAt(k)-'a']++;			//[0,0,0,0,0,.....] 26개
			}
			String key = Arrays.toString(count);	//배열을 스트링으로 바꾸는 캐스팅
			System.out.println("key "+key);
		}
		//2. for
		for (String str : strs){
			char[] charArr = str.toCharArray();
			Arrays.sort(charArr);	//['a','e','t']
			//chararr을 String으로 Map에 저장하기 위해 캐스팅
			String key = String.valueOf(charArr);
			System.out.println("key "+key);
			
			//String을 Map에 넣기 -> map.getOrDefault(key,null)함수로 대체 가능
			if(map.containsKey(key)) {	//Map에 키가 있을 때
				map.get(key).add(str);	//Map에서 키를 꺼내서 str 넣기
			}else {						//Map에 키가 없을 때
				List<String> list = new ArrayList<>();
				list.add(str);			//List에 str 넣기
				map.put(key, list);		//Map에 Key와 list 넣기
			}
			//List<String> list = map.getOrDefault(key, new ArrayList<>());
			//list.add(str);
			//map.put(key, list);
		}
		
		//리턴하는 방법 세가지
		// result.addAll(map.values());
		
//				return new ArrayList<>(map.values());
		//map.value가 List<String>이기 때문에 List<List<String>>으로 만들어 List 타입으로 ArrayList를 만들어 리턴
		
		for(Map.Entry<String, List<String>> entry : map.entrySet()) {
			result.add(entry.getValue());
		}
		return result;
	}

}

 

 

package ArrayBasic;

public class Array5 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
		System.out.println("물의 양 :"+solve(nums));
		System.out.println("물의 양 :"+solve2(nums));

	}
	// 빗물 잡기
	// elevation map(양의 정수)인 너비가 1인 검은 네모에서 높이가 주어지면
	// 비가 내린 후 가둘 수 있는 물의 양 계산

	// 문제 해결 [Divide & Conquer]
	// 1. 물이 차는 영역 결정 -> Math.min
	// -> 왼쪽벽과 오른쪽 벽의 값의 차이 만큼 물이 찬다.
	// 2. 밑의 높이만큼 빼야한다. -> Math.min -밑의 높이

	// 즉, 왼쪽벽 1, 오른쪽벽 2일때 =1 [값의 차이가 존재할 때 작은 값이 물이 차는 크기]
	// 왼쪽벽 2, 오른쪽벽 3일때 =2
	// left, right, height를 이용해 값을 구한다.
	// ->left : 왼쪽 최대 벽
	// ->right : 오른쪽 최대 벽
	// ->height : 밑의 높이

	public static int solve(int[] height) {
		int result =0;
		if(height==null||height.length<=2) {	//예외처리 하는 부분 : 높이가 null이거나, 높이의 길이가 2보다 같거나 작을때
			return result;
		}
		int len=height.length;		//12
		int[] left = new int[len];	//길이만큼 왼쪽벽의 배열을 생성
		int[] right = new int[len];	//길이만큼 오른쪽벽의 배열을 생성
		//공간복잡도를 줄이기 위해서는, 배열을 생성하지않고, while문을 이용해 구현가능

		//1.leftMax[]
		
		int max=height[0];			//왼쪽벽 최대값을 0번째로 일단 기준을 정한다.
		left[0]=height[0];			//왼쪽벽의 0번방은 높이의 0번방
		
		for(int i=1; i<len; i++){
			if(height[i]<max) {
				left[i]=max;		//맥스가 높이보다 크다면, 왼쪽벽 최대 값으로 설정
				//맥스가 제일 큰상태로 유지하기 위한 조건
			}else {
				left[i]=height[i];	//맥스가 높이보다 작은 경우, 왼쪽벽 최대 값으로 높이를 설정
				max=height[i];		//높이를 맥스로 설정
				//맥스가 제일 큰상태가 아닐 때 큰상태로 유지하기 위한 조건
			}
		}
		
		print(left);
		//2.rightMax[]
		max=height[len-1];			//오른쪽벽 최대값이기 때문에, 0번이 아닌 거꾸로 끝방인 길이로 설정한다.[길이는 0부터시작하므로 -1]
		right[len-1]=height[len-1];			//오른쪽벽의 끝방은 높이의 끝방
		
		for(int i=len-2; i>=0; i--) {//끝방이 채워진 상태이므로, 끝방에서 -1
			if(height[i]<max) {
				right[i]=max;		//맥스가 높이보다 크다면, 오른쪽벽 최대 값으로 설정
				//맥스가 제일 큰상태로 유지하기 위한 조건
			}else {
				right[i]=height[i];	//맥스가 높이보다 작은 경우, 오른쪽벽 최대 값으로 높이를 설정
				max=height[i];		//높이를 맥스로 설정
				//맥스가 제일 큰상태가 아닐 때 큰상태로 유지하기 위한 조건
			}
		}
		print(right);
			
		//3.min() - height
		for(int i=0; i<len; i++) {
			result += Math.min(left[i],right[i])-height[i];
		}
		return result;
	}
	public static int solve2(int[] height) {
		//배열을 따로 만들지않고 for문을 이용해 maxLeft와 maxRight을 이용해 물의 양 구하는 방법
		
		int result=0;
		int n=height.length;
		
		for(int i=1; i<n-1;i++) {
			int maxLeft=0, maxRight=0;
			for(int j=i;j>=0;j--) 
				maxLeft=Math.max(maxLeft, height[j]);
			for(int j=i;j<n;j++)
				maxRight=Math.max(maxRight, height[j]);
			System.out.println("maxLeft "+maxLeft+" maxRight "+maxRight);
			result +=Math.min(maxLeft, maxRight)-height[i];
			}
		return result;
		}

	
	public static void print(int [] left) {
		for(int i=0;i<left.length; i++) {
			System.out.println(" 순서: "+i+" 값:"+left[i]);
		}
	}
}

 

 

package ArrayBasic;

import java.util.ArrayList;
import java.util.List;

public class Array6 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums= {2,3,5,50,75};
		int lower=0, upper=99;
		System.out.println("누락된 범위는 : "+solve(nums,lower,upper));
		//[0->1, 4, 6->49, 51->74, 76-> 99]

	}
	//누락된 범위
	//모든 요소를 포함하는 범위와 정렬된 고유 정수 배열을 이용해
	//x라는 숫자가 범위에 존재하지만, 정수배열에 없다면 누락된 값으로 간주
	//누락된 모든 숫자를 정확히 포함하는 가장 작은 정렬된 범위를 리턴
	
	//문제 해결 -> 기준값을 정해놓고 만들면 편하다
	//1.최대최소 범위사이에 누락된 값은 값으로, 범위는 범위로 표시
	//2.최소는 lower<nums[0]
	//3.최대는 nums[nums.length-1]<upper
	//4.중간부분은 nums[i]+1<nums[i+1]	-> i번방보다 1큰수부터~i+1번방보다 1작은수까지 [미만이기때문에]
	
	public static List<String> solve(int[] nums, int lower, int upper){
		//1
		List<String> result=new ArrayList<>();
		if(nums==null||nums.length==0)			//예외처리
			return result;
		
		//2
		//최소에서 작은 부분, 최대에서 큰부분, 가운데부분
		//최소
		if(lower<nums[0]) {	//2보다 작은 부분
			result.add(makeRange(lower, nums[0]-1));	//0-> 1을 전달
			System.out.println(result);
		}
		
		//중간
		for(int i=0;i<nums.length-1;i++) {
			if(nums[i]!=nums[i+1]&&nums[i]+1<nums[i+1]) { 		//중간 부분에 대한 범위 설정
				//nums의 배열 전 부분과 후부분이 다르고, nums[i]번째보다 1큰것보다 nums[i+1]번째보다 1작은것까지
				//6->49 부분을 기준
				result.add(makeRange(nums[i]+1,nums[i+1]-1));	//6->49
				System.out.println(result);
			}
		}
		//.최대
		if(nums[nums.length-1]<upper) {	//75<99
			result.add(makeRange(nums[nums.length-1]+1,upper));	//76->99 즉, 75인 nums[nums.length-1]에서 +1
			System.out.println(result);
		}
		
		return result;
	}
	private static String makeRange(int low, int high) {
		return low==high? String.valueOf(low):(low+"->"+high);	//low와 high가 같다면 valueOf, 같지 않다면 low부터 high
	}

}

 

 

 

package ArrayBasic;

import java.util.ArrayList;
import java.util.List;

public class Array7 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		int[][]nums ={
//			{1,2,3},
//			{4,5,6},
//			{7,8,9}};
//		
		int[][] nums = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
		System.out.println(spiralOrder(nums));

	}
	// 나선형 매트릭스
	// m x n의 요소로 이루어진 매트릭스
	// 나선형 순으로 모든 요소를 출력 [동글뱅이]
	// -> 상하좌우 위치 좌표값 변경을 이용해 문제해결
	// [0,0]:1, [0,1]:2, [0,2]:3, [0,3]:4
	// [1,0]:5, [1,1]:6, [1,2]:7, [1,3]:8
	// [2,0]:9, [2,1]:10, [2,2]:11, [2,3]:12

	// 문제 해결 -> 방향을 기준으로 분류, 오른쪽방향, 아래쪽방향, 왼쪽방향, 위쪽방향, 오른쪽방향

	// 1. 규칙찾기
	// {00, 01, 02, 03} : 오른쪽으로 이동시
	// -> int rowStart =0, int rowEnd=2, matrix.length-1;
	// -> int colStart =0, int colEnd=3, matrix[0].length-1;
	// 즉, rowStart=0은 그대로 int colStart=0, intcolEnd=3, 끝나고 rowStart++
	// colStart가 0에서 colEnd인 3까지 : for(int i=colStart; i<=colEnd; i++)
	// 결과값행렬에 rowStart은 0 고정, i값 증가할때마다 추가 : {result.add(matrix[rowStart][i]);}
	// result는 ArrayList로 List를 담는다.
	// 한행 고정하고, 칼럼이 증가하면서 한행이 끝났기 때문에 : rowStart++;

	// {03, 13, 23} : 아래쪽으로 이동시
	// -> int rowStart =0, int rowEnd=2, matrix.length-1;
	// -> int colStart =0, int colEnd=3, matrix[0].length-1;
	// 즉, colEnd=3은 그대로 int rowStart=1, int rowStart=2로 증가, 끝나고 colEnd--
	// rowStart가 0에서 rowEnd인 2까지 : for(int i=rowStart; i<=rowEnd; i++)
	// 결과값행렬에 칼럼인 colEnd는 0 고정, 행은 i값 증가할때마다 추가 : {result.add(matrix[i][colEnd]);
	// result는 ArrayList로 List를 담는다.
	// 한 칼럼을 고정하고, 행이 증가하면서 한 칼럼이 끝났기 때문에 : colend--;

	// {23, 22, 21, 20} : 왼쪽으로 이동시
	// rowEnd=2은 그대로 int colEnd=에서 int colStart=0까지 감소, 끝나고 rowEnd--
	// while문 안에서 rowStart가 내부적으로 증가 [rowStart++;] : if(rowStart<=rowEnd{
	// colEnd가 3에서 colStart인 0까지 : for(int i=colEnd; i>=colStart; i--)
	// 결과값행렬에 행인 rowEnd는 2 고정, 칼럼은 i값 감소할때마다 추가 : {result.add(matrix[rowEnd][i]);}}
	// result는 ArrayList로 List를 담는다.
	// 한 행을 고정하고, 칼럼이 감소하면서 한 행이 끝났기 때문에 : rowEnd--;

	// {20, 10} :위쪽으로 이동시
	// colStart=0 그대로 int rowEnd=1, int rowEnd=0으로 감소, 끝나고 colStart++
	// while문 안에서 colStart가 내부적으로 증가 [colStart++;] : if(colStart<=colEnd){
	// rowEnd가 2에서 rowStart인 1까지 : for(int i=rowEnd; i>=rowStart; i--)
	// 결과값행렬에 칼럼인 colStart는 0 고정, 행은 i값 감소할때마다 추가:
	// {result.add(matrix[i][colStart]);}}
	// result는 ArrayList로 List를 담는다.
	// 한 칼럼을 고정하고, 행이 감소하면서 한 칼럼이 끝났기 때문에 : colStart++;

	public static List<Integer> spiralOrder(int[][] matrix){
		//1. ds
		List<Integer> result =new ArrayList<>();
		if(matrix==null||matrix.length==0) {
			return result;
		}
		int rowStart=0;
		int rowEnd=matrix.length-1;
		
		int colStart=0;
		int colEnd=matrix[0].length-1;
		
		//2. for, while문
		while(rowStart<=rowEnd&&colStart<=colEnd) {
			//right
			for(int i=colStart; i<=colEnd; i++)
			{result.add(matrix[rowStart][i]);}
			rowStart++;
			
			//down
			for(int i=rowStart; i<=rowEnd; i++)
			{result.add(matrix[i][colEnd]);}
			colEnd--;
			
			//left
			if(rowStart<=rowEnd){
			for(int i=colEnd; i>=colStart; i--)
			{result.add(matrix[rowEnd][i]);}}
			rowEnd--;
				
			//up
			if(colStart<=colEnd){
			for(int i=rowEnd; i>=rowStart; i--)
			{result.add(matrix[i][colStart]);}}
			colStart++;
		}
		return result;
	}
}