반응형
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;
}
}반응형
'Java > Java 알고리즘' 카테고리의 다른 글
| [Java 기본 알고리즘] (4) 투 포인터 (0) | 2022.01.04 |
|---|---|
| [Java 기본 알고리즘] (2) 정렬 탐색 (0) | 2022.01.03 |
| [Java 기본 알고리즘] (1) String (0) | 2021.12.30 |
| [Java] String 메서드 (0) | 2021.12.30 |
| [Java] Casting (형 변환) (0) | 2021.11.25 |
