Do it! 알고리즘 코딩테스트 (5번 ~ 9번)

lusida0131 2022. 5. 16. 15:46

2022. 5. 16. 15:46

728x90

5번 문제 나머지 합

잘못된 풀이

//답이 안나오는 풀이입니다.
import java.io.*;
import java.util.*;
public class Baek10986 {
	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 cnt = 0;
		int rem = 0;
		int [] s = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {		
			s[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 0; i < n; i++) {
			rem = 0;
			for(int j = i; j < n; j++) {
				rem += s[j];
				if(rem % m == 0) {
					cnt++;
				}
			}
			
		}
		System.out.println(cnt);
	}
}

내가 떠올린 풀이 해설

첫째를 기준으로 하나씩 다 더해가면서 3으로나누고 나눠지는 수는 카운트 수 증가하고 그리고 왼쪽 배열 위치를 움직이면서 수를 하나씩 빼준다. 하지만 이렇게 풀었을 때 시간 오류가 나온다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek10986 {

	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());
		long cnt = 0;
		long [] s = new long[n];
		long [] c = new long[m];
		st = new StringTokenizer(br.readLine());
		s[0] = Integer.parseInt(st.nextToken());
		for(int i = 1; i < n; i++) {	//수열의 합 배열 만들기 
			s[i] = s[i - 1] + Integer.parseInt(st.nextToken());
		}
		for(int i = 0; i < n; i++) {	//합 배열의 모든 값에 % 연산 수행하기 
			int rem = (int)(s[i] % m);
			//0 ~ i 까지의 구간 합 자체가 0일 때 정답에 더하기  
			if(rem == 0) {
				cnt++;
			}
			// 나머지가 같은 인덱스의 개수 카운트 
			c[rem]++;
		}
		for(int i = 0; i < m; i++) {
			if(c[i] > 1) {
				// 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하
				cnt = cnt + (c[i] * (c[i] - 1) / 2);
			}
		}
		System.out.println(cnt);
	}
}

문제점

시간 초과가 나온 이유는 N의 최대값이 106이라 모든 구간합을 구하기에 1초는 너무 짧다. 따라서 구간 합 배열을 이용해야 된다.

문제에서 구간 합 배열의 풀이 방법을 떠올리지 못했다. 또한 구간 합 배열의 개념이 부족했다.

나머지 합 배열 핵심 아이디어

1. (A+B)%C는 ((A%C) + (B%C))%C와 같다 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

2. S[i] - S[j] 는 원본 배열의 j+1 부터 i 까지의 구간 합이다.

3. S[i] % M 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. 즉 구간 합 배열의 원소를 M으로 나눈 나머지 값을 업데이트하고 4. S[i] 와 S[j] 가 같은 (i,j)쌍을 찾으면 원본 배열에서 j + 1부터 i 가지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.

6번 문제 수들의 합 5

잘못된 풀이

import java.io.*;
import java.util.*;
public class Beak2018 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			sum = 0;
			for(int j = i; j <= n; j++) {
				sum = sum + j;
				if(sum == n) {
					cnt++;				
				}
			}
		}
		System.out.println(cnt);
	}
}

내가 떠올린 풀이 해설

앞에와 비슷한 방식으로 풀었습니다. for문으로 j가 하나씩 증가 시키면서 더해주고 n이랑 같으면 cnt를 늘려주고를 15번 실시한다.

안에 있는 for문이 다 돌면 sum을 0으로 초기화 시켜주고 i의 for문이 실행된다 이를 15번 실시한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2018 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 1;
		int sum = 1;
		int start_index = 1; // 시작 인덱스 추가 
		int end_index = 1;  // 끝 인덱스 추가 
		while(end_index != n) {
			if(sum == n) {
				cnt++;
				end_index++;
				sum = sum + end_index; // sum == n; end_index++; sum = sum + end_index; cnt++;
			} else if(sum > n) {
				sum = sum - start_index;
				start_index++;
			} else {
				end_index++;
				sum = sum + end_index;
			}
		}
		System.out.println(cnt);
	}
}

문제점

시간 초과가 나온 이유는 N의 최대값이 10,000,000으로 매우 큰 수로 잡혀있다. 이런 상황에서는 O(nlogn)의 알고리즘이 아닌 O(n)의 시간 복잡도 알고리즘을 사용해야 된다. 이런 경우 자주 사용하는 방법은 투 포인터이다.

투 포인터 핵심 아이디어

배열의 index를 탐색하는 start_index와 end_index를 만들어서 배열에서 예를 들어 sum과 n이 같으면 카운트 수 하나 증가시켜주고 end_index를 한 칸 이동하고 sum = sum + end_index를 해준다. 만약 sum이 n 보다 크면 start_index를 한칸 이동하고 sum = sum - start_index를 해준다. 만약 sumd이 n보다 작으면 end_index를 한칸 이동하고 sum = sum + end_index를 해준다.

7번 문제 주몽

정확한 풀이

import java.util.*;
import java.io.*;
public class Baek1940 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		int [] arr = new int[n];
		int cnt = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int i = 0;
		int j = n -1;
		while (i < j) {
			if(arr[i] + arr[j] == m) {
				i++;
				j--;
				cnt++;		
			} 
			else if(arr[i] + arr[j] < m) {
				i++;
			}
			else {
				j--;
			}
		}
		
		System.out.println(cnt);
	}

}

투 포인터 핵심 아이디어

6번 문제와 같은 투포인터 문제입니다.

n의 크기가 15,000이므로 O(nlogn)인 시간 복잡도 알고리즘을 사용해도 문제가 없다.

일반적으로 정렬 알고리즘의 시간 복잡도가 O(nlogn)입니다. 여기에서는 재료 데이터를 배열에 저장시킨 후 오름차순 정렬을 합니다.

투 포인터 i, j 를 양쪽 끝에 둔 후에 포인터 이동 원칙을 활용해 탐색한다.

투포인터 이동 원칙

while 조건 (i < j) 일 때까지 반복한다.
A [i] + A[j] > M : j--; // 번호의 합이 M보다 크므로 큰 번호 index를 내립니다.
A[i] + A[j] < M : j++; // 번호의 합이 M보다 작으므로 작은 번호 index를 올립니다.
A[i] + A[j] == M : i++; j--; count++; // 양쪽 포인터를 모두 이동시키고 count를 증가시킵니다

8번 문제 좋다

문제 해설

n의 개수가 최대 2,000이라 가정해도 좋은 수 찾는 알고리즘의 시간 복잡도는 N^2의 보다 작아야 합니다.

이 문제의 알고리즘의 시간복잡도는 최소 O(nlogn)이어야 합니다. 정렬이나 투 포인터를 사용해야 된다.

단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안 된다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1253 {

	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 cnt = 0;
		Arrays.sort(arr);
		for(int k = 0; k < n; k++) {
			long find = arr[k];
			int i = 0;
			int j = n - 1;
			
			while(i < j) {
				if(arr[i] + arr[j] == find) {
					if(i != k && j != k) {
						cnt++;
						break;
					}
					else if(i == k) {
						i++;
					}
					else if(j == k) {
						j--;					
					}
				}
				else if(arr[i] + arr[j] < find) {
					i++;
				} else {
					j--;
				}
			}
		}
		System.out.println(cnt);
		br.close();
	}

}

9번 문제 DNA 비밀번호

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek12891 {
	static int [] checkArr;
	static int [] myArr;
	static int checkInt;
	static int result;
	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());
		char [] str = br.readLine().toCharArray();
		checkArr = new int [4];
		myArr = new int [4];
		checkInt = 0;
		result = 0;
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < 4; i++) {
			checkArr[i] = Integer.parseInt(st.nextToken());
			if(checkArr[i] == 0) {
				checkInt++;
			}
		}
		for(int i = 0; i < m; i++) {
			Add(str[i]);
		}
		if(checkInt == 4) {
			result++;
		}
		for(int i = m; i < n; i++) {
			int j = i - m;
			Add(str[i]);
			Remove(str[j]);
			if(checkInt == 4) {
				result++;
			}
		}
		System.out.println(result);
		br.close();
	}

	private static void Remove(char c) {
		switch(c) {
		case 'A' :
			if(myArr[0] == checkArr[0]) {
				checkInt--;
			}
			myArr[0]--;
			break;
		case 'C' :
			if(myArr[1] == checkArr[1]) {
				checkInt--;
			}
			myArr[1]--;
			break;
		case 'G' :
			if(myArr[2] == checkArr[2]) {
				checkInt--;
			}
			myArr[2]--;
			break;
		case 'T' :
			if(myArr[3] == checkArr[3]) {
				checkInt--;
			}
			myArr[3]--;
			break;
		}		
	}

	private static void Add(char c) {
		switch(c) {
			case 'A' :
				myArr[0]++;
				if(myArr[0] == checkArr[0]) {
					checkInt++;
				}
				break;
			case 'C' :
				myArr[1]++;
				if(myArr[1] == checkArr[1]) {
					checkInt++;
				}
				break;
			case 'G' :
				myArr[2]++;
				if(myArr[2] == checkArr[2]) {
					checkInt++;
				}
				break;
			case 'T' :
				myArr[3]++;
				if(myArr[3] == checkArr[3]) {		
					checkInt++;
				}
				break;
		}
	}
}

문제 해설

슬라이딩 윈도우를 이용하는 문제이다. 위의 문제는 n의 크기가 1,000,000이기 때문에 시간 복잡도 O(n)의 시간 복잡도를 이용하여 풀어야 된다. 슬라이딩 윈도우는 시간 복잡도가 O(n)입니다. 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓습니다. 그런 다음 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색합니다. 배열의 S의 길이만큼 탐색을 진행하면 되므로 O(n)의 시간 복잡도를 가집니다.

오늘의 회고

오늘 코딩테스트를 대비하려고 코딩테스트를 한번 풀어봤습니다. 많은 시간을 투자해서 풀려고 노력했지만 답은 나왔어도 시간 초과나 풀지 못하는 문제가 있었습니다. 알고리즘은 효율적인 방식으로 해결해 나가야 되지만 풀이 방식을 떠올리는 것은 쉽지만은 않은 것 같습니다.

좌절하지 않고 천천히 하반기 공채까지 진행해보겠습니다. 내일은 오늘 부족했던 문제들 복습하고 오늘보다 난의도가 쉬운 문제투 포인터 2문제, 구간 합 2문제, 슬라이딩 윈도우 1문제를 풀어보겠습니다.

728x90

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

백준) 수학, 좌표정렬 (0)	2022.05.21
Do it! 알고리즘 코딩테스트(14번) (0)	2022.05.20
백준) 스택, 덱, 큐 (0)	2022.05.19
Do it! 알고리즘 코딩테스트 (11번 ~ 13번) (0)	2022.05.18
백준) 투포인터, 슬라이드윈도우, 누적합 (0)	2022.05.17

고민의 흔적