문법
ArrayList 정렬 (Collections.sort() 이용)
- Collections.sort() 이용
- 오름차순 Collections.sort(arrayList);
- 내림차순 Collections.reverse(arrayList);
- new Compartor와 CompareTo를 이용하여 사용자가 원하는 데로 재정렬
- Integer대신에 클래스를 넣고 필드값을 비교 가능
Collections.sort(arrayList, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1.compareTo(o2); // compareTo() 정수값을 반환, o1과 o2를 비교하여 같으면 0, o1이 크면 양수, 작으면 음수 // 이 코드는 오름차순 // return o2.compareTo(o1) -> 내림차순 } });
투 포인터
- 리스트에 순차적으로 접근해야 할 때 2개 점의 위치를 기록하면서 처리하는 알고리즘
- 완전탐색으로 인해 시간이 초과될때 투 포인터를 이용해서 해결
- lt, rt (점의 시작 위치를 기록하는 포인터 생성)
- while (lt<rt) 가 만족할때 배열로 접근하면서 문제 해결
문제 1
이슈
while문안에 2개의 포인터를 넣어 종료하는 것을 생각못함
- while (p1<n && p2<m) -> 2개의 조건 중 1개만 만족해도 종료
해결 방법
- while 문 1개만 씀
- 두 배열 정렬
- 핵심 포인트는 while 문 종료시키는 조건 -> 둘중 하나만 lt가 넘어도 종료 while (p1<n && p2<m) -> 이걸 생각
- ex) 1 2 3 4 5
2 3 4 5
brr이 크면 arr의 위치 1 증가
arr이 크면 brr의 위치 1 증가
코드
public void solution2(int n,int m,int arr[],int brr[]) {
// 정렬
Arrays.sort(arr);
Arrays.sort(brr);
int p1=0;
int p2=0;
ArrayList<Integer>arraylist=new ArrayList<>();
// 둘중 한개만 만족해도 종료
while (p1<n && p2<m) {
// 같으면 둘자 p1, p2 증가
if (arr[p1]==brr[p2]) {
arraylist.add(arr[p1]);
p1++;
p2++;
}
else if (arr[p1]>brr[p2]) {
p2++;
}
else {
p1++;
}
}
System.out.println(arraylist.toString());
}
문제 2
이슈
k가 커지면 N*K = O(n^2)의 시간 복잡도가 발생 -> 시간 초과
- 해결 방법은 슬라이싱 윈도우!
- 슬라이싱 윈도우란 창문을 이동시키듯이 이동하는 방법 (같은 크기)
- 공통 원소를 재사용하는 것.
슬라이싱 윈도우 방법
- K만큼 초기값을 더한다.
- 같은 원소를 재사용하기 위해 다음 인덱스는 더하고 처음 인덱스는 빼준다. (반복 k~n까지)
코드
public int solution2(int n,int k,int []arr) {
// 슬라이싱 윈도우
// 밀면서 이동하는 것
int hap=0;
// 초기 3개 더한 값을 구한다
for (int i=0;i<m;i++) {
hap+=arr[i];
}
int answer=hap;
// 하나씩 밀면서 증가시키고 처음 인덱스 값은 하나씩 지운다.
for (int i=k;i<n;i++) {
hap+=(arr[i]-arr[i-k]); // 다음 인덱스는 더하고, 처음 인덱스는 빼준다.
if (answer<hap) {
answer=hap;
}
}
System.out.println(answer);
return answer;
}
문제 3
이슈 및 해결방법
연속 부분 수열
- 대표적인 투 포인터 문제
- lt, rt=0으로 초기화, 처음 값(k)도 0으로 초기화
- lt는 인덱스의 위치, rt는 증가하는 값의 인덱스
- while 문 1개만 돌리고 k가 주어진 m보다 큰지 작은지 같은지 나누어서 풀이
- 주의사항은 k값이 >=m 일때 k값을 0으로 초기화 시키는 것이 중요
코드
public int solution(int n,int m, int arr[]) {
int answer=0;
int lt=0;
int rt=0;
int k=0;
while (lt<n && rt<n) {
k+=arr[rt];
if (k<m) {
rt++;
}
else if (k==m) { // 같으면 답 증가, lt를 1증가, rt와 lt위치를 같게 하고 k값은 0으로 초기화
answer+=1;
lt++;
rt=lt;
k=0;
}
// 너무 크면 k를 lt의 위치를 한칸 이동 후 초기화, rt
else {
k=0;
lt++;
rt=lt;
}
}
return answer;
}
문제 3
해결 방법
- 투포인터 이용
- 2개 이상의 연속된 자연수이기 때문에 초기 lt =1로 하고 rt는 lt보다 1개 증가된 2로 설정, k(합)=lt로 초기화
- while문 돌면서 rt를 더한다
if (k==rt) : answer+1, lt+=1, k=lt, rt는 lt보다 1큰 값으로 설정
else if (k<n) : rt만 1개씩 증가
else : lt+=1, k=lt, rt는 lt보다 1큰 값으로 설정
코드
public int solution(int n) {
int answer=0;
int lt=1;
int rt=2;
int k=lt;
while (lt<n && rt<n) {
k+=rt;
if (k==n) {
answer+=1;
lt++;
k=lt;
rt=lt+1;
}
else if (k<n) {
rt+=1;
}
// 초과되면 lt를 1칸 이동
else {
lt++;
k=lt;
rt=lt+1;
}
}
return answer;
}
문제 4
코드
public int solution(int n,int m, int arr[]) {
int answer=1;
int mm=m; // 다시 초기화해서 쓰기 위해 임시 저장
int lt=0;
int rt=0;
// String은 저장값이 누적되기 때문에 StringBuilder 이용
StringBuilder sb=new StringBuilder();
while (lt<n && rt<n) {
int k=arr[rt];
// int -> String
if (k==0) {
// 주어진 m이 남아있으면
if (m>0) {
k=1;
sb.append(Integer.toString(k));
m--;
rt++;
} // 주어진 m을 다 써버리면
else {
lt+=1;
rt=lt;
// sb초기화
sb=new StringBuilder();
m=mm;
}
}
else { // k==1이면 계속 저장
rt++;
sb.append(Integer.toString(k));
}
// 길이가 큰지 확인
if (sb.length()>answer) {
answer=sb.length();
}
}
System.out.println(answer);
return answer;
}느낀점
주어진 문제에서 연속된 수열 or 부분 집합을 찾는다.
주어진 계산이 N*M이 1억을 넘어간다 ->
투포인터 or 슬라이스 윈도우 문제로 의심하고 풀이
- 투포인터는 lt와 rt의 범위를 while 문 안 조건을 꼭 생각하고 풀이
REF
BackEnd Developer