목차
- 문제 설명
- 알고리즘 접근방법 & 아이디어
- 1차 소스코드
- 문제점 파악 및 최적화
- 최종 코드
1. 문제 설명
- 재윤이는 총 N개의 종이컵의 안 쪽에 임의의 자연수를 적어둔다.
- 모든 종이컵은 숫자가 보이지 않도록 뒤집은 채로 일렬로 나열한다.
- 종이컵의 위치는 게임 도중에 변경될 수 없다.
- 현무는 임의의 인접한 K개의 연속된 종이컵을 선택하여 숫자를 확인하고 그 숫자들의 합을 구한다.
- 해당 숫자들의 합이 짝수이면 재윤이가 청소를 하고, 홀수이면 현무가 청소를 한다.
입력형식
-
첫 줄에는 종이컵의 수 N과 현무가 선택할 종이컵의 수 K가 공백으로 구분되어 주어진다. N과 K는 1이상 10만 이하의 자연수이다.
-
두 번째 줄에는 총 N개의 종이컵에 적힌 숫자들이 실제 놓여진 순서대로 주어진다. 종이컵에 적힌 숫자들은 모두 0이상 100만 이하의 정수이다.
2. 알고리즘 접근방법 & 아이디어
위 문제는 N = 5, K = 3 일때 data[] = 1, 2, 3, 4, 5가 주어진다면
[1, 2, 3], [2, 3, 4], [3, 4, 5]의 합을 구해 이가 홀짝인지 판별하면 되는 문제다.
즉 우리는 연속한 K개의 그룹을 순회해야 한다
이때 순회 방법을 어떻게 해야할까?
우리는 두칸을 순회할 때 아래의 방식을 쓸 수 있다
for(int i = 0; i + 1 < n; i++){
data[i] + data[i + 1]
}근데 이제 위 방식에서 이제 2칸이 아닌 K칸이라는 가변으로 바꼈다
그래서 위 방식은 2칸 고정이기에 하나의 for문을 사용했지만
우리는 이제 고정이 아닌 k번이라는 가변처리를 해주기 위해 이중for문을 사용한다
위 사진과 같은 상황에서는 [1, 2, 3], [2, 3, 4], [3, 4, 5] 이렇게 3번 돌아야하는데
[2, 3, 4] 덧셈을 한다고 가정하면 i의 인덱스가 1일 때 i + k - 1번까지 반복을한 후
i의 인덱스를 증가시키고 [3, 4, 5]를 또 처리해 줄 것이다
즉 i의 반복은 i + k - 1(끝인덱스)가 < N 일때까지 처리하고
데이터의 반복은 i <= i + k - 1로 해주면 되는 것이다
for(int i = 0; i + k - 1 < n; i++){
for(int j = i; j <= i + k - 1; j++){
sum += data[j];
}
}즉 위와 같이 순회를 하고 그 안에서 조건을 넣어주면 해당 답을 쉽게 구할 수 있다
3. 1차 소스코드
public class Main {
public static final Scanner scanner = new Scanner(System.in);
/**
* 게임의 규칙에 따라 현무가 승리할 수 있는 경우의 수가 존재하는지 검사하는 함수
*
* @param data
* @param n
* @param k
* @return true 현무가 승리할 수 있는 경우의 수가 하나 이상 존재한다면
* @return false else
*/
public static boolean isWinnable(int[] data, int n, int k) {
int winCount = 0;
long sum = 0;
// 가변적 데이터 순회 반복문!! (n, k)의 크기에 따른 가변 데이터 반복
for(int i = 0; i + k - 1 < n; i++){
for(int j = i; j <= i + k - 1; j++){
sum += data[j];
}
if(sum % 2 == 0){ // 총합이 짝수라면
winCount++;
break; // 나머지 탐색할 필요 없이 바로 종료 (가지치기)
}
}
if(winCount > 0) // 조건에 따른 출력문
{
return true;
}else{
return false;
}
}
public static void main(String[] args) throws Exception {
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] data = new int[n];
for(int i = 0 ; i < n ; i++)
{
data[i] = scanner.nextInt();
}
boolean result = isWinnable(data, n, k);
if(result)
{
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
4. 문제점 탐색 및 최적화
그러나 위 코드엔 문제가 있는데 바로 O(n^2)의 시간 복잡도를 가지기에 시간초과가 걸린다sliding Window
크기가 일정한 범위(k)들을 한방향으로 순서대로 조회하는 방법
교집합의 정보는 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법
k의 범위를 윈도우라고 부르겠다
배열 내에서 모든 윈도우를 순회해야 할 때 사용
위 사진을 [1, 2, 3], [2, 3, 4], [3, 4, 5] 이렇게 순회해야 한다고 말했다
교집합의 정보를 공유하고 차이가 나는 양쪽 끝 원소만 갱신하는 방법이 무엇이냐하면
[1, 2, 3]을 순회하고 -> [2, 3, 4]를 순회하는 과정에서
1을 빼고 4를 추가하고 기존의 원소(2, 3)를 그대로 사용하는 방법이다
info) sliding window가 어려운 문제 = 양쪽 끝 원소만으로 갱신 복잡해짐
이 방법으로 합을 구하는 방법은 이전 원소를 이용해 합을 구하면 된다
[2, 3, 4]
= [1, 2, 3] - 1 + 4
순회 원소의 합 = 이전원소의 합 - 이전원소의 첫값 + 들어올 원소ex)[1, 2, 3, 4, 5, 6]
= 2 + 3 + 4 = 9
= 9 - 2 + 5 = 14
아래를 구할 때 이때 3, 4 값을 사용하지 않고 이전 값을 이용했기에 효율적이다
sliding window 사용 조건
- 고정된 윈도우 범위(k)가 있어야 한다
- 모든 윈도우를 순회해야하는 경우
- 연속한 두 윈도우 사이에 효율적인 갱신방법
5. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Q2J {
private static boolean isWinnable(int[] data, int n, int k) { // n : 4 k : 2
int winCount = 0;
long sum = 0;
// 첫 윈도우는 이전 값을 참조하지 못하니 따로 처리해준다
for(int i = 0; i < k; i++){
sum += data[i];
}
if(sum % 2 == 0){
return true;
}
// sliding window 적용
for(int i = 1; i + k - 1 < n; i++) { // 첫 윈도우를 제외한 나머지 윈도우
sum = sum - data[i -1] + data[i + k - 1]; // 기존의 합에서 이전윈도우의 첫 값을 빼고 기존 윈도우의 마지막값을 추가하면 된다
if (sum % 2 == 0){
return true;
}
}
return false;
}
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()); // n = 입력 데이터 수
int k = Integer.parseInt(st.nextToken()); // k = k개의 범위를 묶어 순회
int[] data = new int[n]; // n개의 배열 할당
st = new StringTokenizer(br.readLine()); // 실제 데이터 입력
for(int i = 0; i < n; i++){
data[i] = Integer.parseInt(st.nextToken()); // 배열에 데이터 추가
}
boolean result = isWinnable(data, n, k);
if(result){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
