1. 두 배열 합치기
방법1: 투포인터 사용
풀이방식
- 입력받은 두개의 배열에 p1, p2를 사용하여 길이만큼 비교하도록 한다. 여기서 p1, p2는 0으로 초기화 하여 i인덱스 역할을 함
p1<n && p2<m둘중 하나라도 먼저 끝나면 남은 값들을 answer.add로 집어 넣기
import java.util.*;
class reMain01 {
public static ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
ArrayList<Integer> answer = new ArrayList<>();
int p1=0, p2=0; //포인터
while(p1<n && p2<m){ //둘중 하나라도 거짓이되면 전체 거짓 => 멈춘다
if(a[p1]<b[p2]) answer.add(a[p1++]); //p1값을 넣고 그후에 증가++
else answer.add(b[p2++]); //p2값을 넣고 그후에 증가++
}
//남은 값을 집어 넣어야 하기 때문에 둘다 사용
while(p1<n) answer.add(a[p1++]);
while(p2<m) answer.add(b[p2++]);
return answer;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] a=new int[n];
for(int i=0; i<n; i++){
a[i]=kb.nextInt();
}
int m=kb.nextInt();
int[] b=new int[m];
for(int i=0; i<m; i++){
b[i]=kb.nextInt();
}
for(int x : solution(n, m, a, b))
System.out.print(x+" ");
}
}방법2 : 한 배열로 합쳐서 정렬
import java.util.*;
public class Main01 {
public static ArrayList<Integer>solution( int []arr1, int []arr2) {
ArrayList <Integer> answer = new ArrayList<Integer>();
// 두 배열을 합치기
for (int x : arr1){
answer.add(x);
}
for (int x : arr2){
answer.add(x);
}
Collections.sort(answer);
// Arrays.sort(answer);
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int []arr1 = new int[n];
for (int i=0; i<n; i++){
arr1[i] = sc.nextInt();
}
int m = sc.nextInt();
int []arr2 = new int[m];
for (int i=0; i<m; i++){
arr2[i] = sc.nextInt();
}
for (int x : solution(arr1, arr2)){
System.out.print(x + " ");
}
}
}Collections.sort(answer);: 리스트타입 정렬Arrays.sort(answer);: 배열 타입을 정렬
2. 공통원소 구하기
주의할점
같지 않으면 모두 증가를 할경우, 동시에 증가하기 때문에 공통 원소를 구할 수 없다. 작은쪽을 증가시켜서 같을 경우를 비교해야함.
public class Main02 {
public static ArrayList<Integer>solution(int n, int m, int []arr1, int []arr2){
ArrayList<Integer> answer = new ArrayList<>();
Arrays.sort(arr1);
Arrays.sort(arr2);
int p1=0, p2=0;
while(p1<n && p2<m){
if (arr1[p1] == arr2[p2]) {
answer.add(arr1[p1++]);
p2++;
}else if (arr1[p1] < arr2[p2]) p1++;
else p2++;
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int []arr1 = new int [n];
for (int i=0; i< n; i++){
arr1[i] = sc.nextInt();
}
int m = sc.nextInt();
int []arr2 = new int [m];
for (int i=0; i<m; i++){
arr2[i] = sc.nextInt();
}
for (int x : solution(n, m , arr1, arr2)){
System.out.print(x + " ");
}
}
}3. 최대 매출
풀이 방법
- 슬라이딩을 사용하여 구하는 방법
public class Main03 {
public static int solution(int n, int k,int []arr1){
int sum = 0, answer;
for (int i=0; i<k; i++) sum += arr1[i]; //1. k 만큼의 인덱스 합
answer = sum;
for (int i=k; i<n; i++){ //2. 뒤의 인덱스 더하고 앞의 인덱스 빼기
sum += (arr1[i] - arr1[i-k]);
answer = Math.max(answer, sum); //3. 값 비교
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int []arr1 = new int[n];
for (int i=0; i<n; i++){
arr1[i] = sc.nextInt();
}
System.out.print(solution(n, k, arr1));
}
}4. 연속 부분 수열
lt, rt를 사용하여 연속된 수열을 구하기
public class Main04 {
public static int solution(int n, int m, int [] arr){
int lt=0;
int answer=0, sum = 0;
for (int rt=0; rt<n; rt++){
sum += arr[rt];
if (sum ==m)
answer++;
while (sum >= m){
sum -= arr[lt++];
if (sum==m)
answer++;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
int m = sc.nextInt();
int []arr = new int[n];
for (int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.print(solution(n, m , arr));
}
}5. 연속된 자연수의 합
방법1. TwoPointer
import java.util.Scanner;
public class Main05 {
public static int solution(int n){
int answer=0, sum = 0;
int lt =0;
int []arr = new int[n/2+1];
for (int i=0; i<n/2+1; i++)
arr[i] = i+1; // 빈 배열이기 때문에 1개씩 값 증가하여 집어넣기
for (int rt=0; rt<n/2+1;rt++) {
sum += arr[rt];
if (sum == n) {
answer++;
}
while (sum >= n) {
sum -= arr[lt++];
if (sum == n) answer++;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print(solution(n));
}
}방법2. 수학적 풀이
풀이방법
1~n까지 2개이상의 연속된 자연수의 합이 n인 경우를 구하는 방법에서
합을 분할해준다고 생각하자. cnt는 연속된 수의 자릿수를 뜻한다
n(자연수의 합)-cnt(연속된 자릿수)만큼 제외 한 값을 자릿수만큼 다시 나눈다
여기서 0으로 나눠질 경우 해당 자리만큼 연속된 수가 존재한다
public class reMain05 {
public static int solution(int n){
int answer = 0, cnt =1;
n--;
while(n>0){
cnt++;
n= n-cnt;
if (n%cnt==0) answer++;
}
return answer;
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
System.out.print(solution(n));
}
}6. 최대 길이 연속 부분 수열
풀이방법
- lt, rt를 사용
- lt가 k횟수의 cnt가 넘어가면 증가, 그 이전까지는 rt가 순회하면서 0을 1로 바꾼다
import java.util.Scanner;
public class Main06 {
public static int solution(int n, int k, int []arr){
int answer = 0;
int cnt=0; //0을 1로 바꾼 횟수
int lt=0;
for (int rt=0; rt<n; rt++){
if (arr[rt]==0) cnt++;
//0을 바꾼 횟수를 k 이하로 제한
while(cnt>k){
//lt는 rt가 바꾼 1을 다시 0으로 변경
if (arr[lt]==0) cnt--;
lt++;
} //길이 구하기
answer = Math.max(answer, rt-lt+1);
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
int k = sc.nextInt();
int []arr = new int[n];
for (int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.print(solution(n, k, arr));
}
}
개발기록