알고리즘/알고리즘 문제풀이
백준) 투포인터, 슬라이드윈도우, 누적합
lusida0131
2022. 5. 17. 13:11
728x90
백준 11728번 배열 합치기
잘못된 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
System.out.println(list);
}
}잘못된 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
int [] aArr = new int[aSize];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
aArr[i] = Integer.parseInt(st.nextToken());
}
int [] bArr = new int [bSize];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
bArr[i] = Integer.parseInt(st.nextToken());
}
int lt = 0;
int rt = 0;
ArrayList<Integer> list = new ArrayList<>();
while(rt < aSize && lt < bSize) {
if(aArr[rt] > bArr[lt]) {
list.add(bArr[lt]);
lt++;
}
else if(aArr[rt] < bArr[lt]) {
list.add(aArr[rt]);
rt++;
}
else {
lt++;
rt++;
}
}
while(rt < aSize) {
list.add(aArr[rt]);
rt++;
}
while(lt < bSize) {
list.add(bArr[lt]);
lt++;
}
System.out.println(list);
}
}
내가 생각한 풀이 해설
배열을 리스트에 담아서 출력하는 방법을 생각했다.
하지만 시간 초과가 나왔다. 다른 방식으로 투포인터 알고리즘으로 풀었는데도 시간 초과가 나왔다.(?)
계속 바꿔도 시간초과가 나왔는데 그 이유는 마지막에 정답을 출력할 때System.out.print를 사용하면 시간 초과가 나는 것이었다.
이것 때문에 시간을 많이 썼다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < list.size(); i++) {
bw.write(list.get(i) + " ");
}
br.close();
bw.close();
}
}
백준 21921번 블로그
문제점
for문에서 max를 구할 때 크기만큼 달라지는 합해주는 값이 달라지는 것과 count에서 어려움을 느꼈습니다.
for문 안에서 while과 if로 처리해주는 것에 대한 이해가 필요할 것 같습니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek21921 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int [] arr = new int [n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int end = 0;
int sum = 0;
int max = 0;
int count = 1;
for(int i = 0;i < n; i++){
while((end - i < m) && end < n){
sum += arr[end];
end++;
}
if(max == sum){
count++;
}
else if(max < sum){
max = sum;
count = 1;
}
sum -= arr[i];
}
if(max == 0){
System.out.println("SAD");
return;
}
System.out.println(max);
System.out.println(count);
}
}백준 3273번 두 수의 합
내가 생각한 풀이
어제 풀었던 투포인터 알고리즘을 사용해서 풀면 쉽게 풀리는 문제였다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek3273 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int [n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine());
int i = 0;
int j = n - 1;
int cnt = 0;
Arrays.sort(arr);
while(i < j) {
if(arr[i] + arr[j] == m) {
cnt++;
i++;
j--;
}
else if(arr[i] + arr[j] < m) {
i++;
}
else {
j--;
}
}
System.out.println(cnt);
}
}
백준 14706번 구간 합 최대
문제점
위에 문제는 아직 해결을 하지 못했다. 고민을 많이 해봐야 될 것 같다. 또한 코드를 참고하려고 해도 아직까지 블로그에 올리신 분이 없습니다.
백준 2167번 2차원 배열의 합
내가 생각한 풀이
이와 비슷한 문제를 푼 적이 있어서 오래 걸리지는 않았다. 처음에 이 문제를 접했을 때 구간에서 다음 구간까지 더해주는 것에서 방법을 떠올리기 힘들었다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2167 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int [][] arr = new int [n + 1][m + 1];
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int k = Integer.parseInt(br.readLine());
int sum;
for(int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
sum = 0;
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
for(int j = x1; j <= x2; j++) {
for(int t = y1; t <= y2; t++) {
sum += arr[j][t];
}
}
System.out.println(sum);
}
}
}
오늘의 회고
오늘은 시간 초과 문제로 시간을 많이 소비했습니다. 시간 초과가 났을 때 알고리즘 문제가 아니라 출력해주는 부분에도 시간초과가 날 수 있다는 것을 배웠습니다. 또한 아직도 투포인터에서 이해하지 못한 부분이 있습니다. 자료를 계속 찾아서 공부하고 이해하려고 노력해야 될 것 같습니다. 또한 오늘 해결하지 못한 문제는 내일 이어서 고민해보고 내일은 책에 연습문제 4문제를 풀겠습니다.
728x90