Java 백준 25379- 피하자

백준 링크

https://www.acmicpc.net/problem/25379

25379번: 피하자

---

문제

입력

출력

입출력 예시

 

---

제출한 코드

 

첫 번째 코드 (10점)

package BaekJun;

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException, NumberFormatException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        boolean[] data = new boolean[t];

        int leftCnt = 0;
        int rightCnt = 0;

        for (int i = 0; i < t; i++) {
            if (Integer.parseInt(st.nextToken()) % 2 == 0) {
                data[i] = true;
                if (i < (int) t / 2) {
                    leftCnt += 1;
                } else if (i > (int) t / 2) {
                    rightCnt += 1;
                }
            }
        }
        int cnt = 0;
        int answer = 0;
        if(leftCnt > rightCnt) {
            for(int i = 0 ; i < t;i++) {
                if(data[i] == true) {
                    answer += i - cnt;
                    cnt+=1;
                }
            }
        }
        else {
            for(int i = t-1;i>=0;i--) {
                if(data[i] == true) {
                    answer += (t-1)-i-cnt;
                    cnt+=1;
                }
            }
        }
        System.out.println(answer);
    }
}

 

 

 

1. 전체 입력받는 데이터의 수/2를 기준으로 좌, 우 어느 쪽으로 밀어 넣을지 고민을 했었다.

2. 단순히 0 or 2의 배수의 개수만 구하고 정했기에 문제가 있었다.

---

 

2번째 코드 (50점)

package BaekJun;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException, NumberFormatException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int leftCnt = 0;
        int rightCnt = 0;
        int cnt = 0;
        int sum = 0;

        for (int i = 0; i < t; i++) {
            if ((Integer.parseInt(st.nextToken()) % 2) == 0) {
                leftCnt += i;
                rightCnt += t-1-i;
                sum += cnt;
                cnt +=1;
            }
        }

        System.out.println(Math.min(leftCnt,rightCnt)-sum);
    }
}

 

 

로직을 접근하는 부분에 있어서 큰 문제가 있는 것을 알고 전체적인 코드를 지우고 다시 작성했다.

기존의 코드에 반복문이 많아 시간복잡도 부분에서 문제가 있을 것이라고 생각했다.

 

1. 시간제한에 걸리지 않기 위해서 BufferedReader를 이용해서 입력을 받았다.

2. StringTokenizer를 이용해서 데이터를 한줄에 입력받는다.

3. 입력받은 데이터가 좌 or 우로 갈 때 소요되는 횟수를 leftCnt, rightCnt에 저장하였다.

4. 추가적으로 빼줘야 하는 횟수까지 생각해서 짝수와 0의 개수를 cnt를 이용해서 sum에 저장하였다.

5. 마지막 정답을 출력하는 부분에서 leftCnt와 rightCnt중 작은 값을 저장해 둔 sum을 빼고 출력한다.

 

하지만 이 코드는 50점을 받았다.

---

최종 제출 코드

package BaekJun;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException, NumberFormatException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        long leftCnt = 0;
        long rightCnt = 0;
        int cnt = 0;
        long sum = 0;

        for (int i = 0; i < t; i++) {
            if ((Integer.parseInt(st.nextToken()) % 2) == 0) {
                leftCnt += i;
                rightCnt += t-1-i;
                sum += cnt;
                cnt +=1;
            }
        }

        System.out.println(Math.min(leftCnt,rightCnt)-sum);
    }
}

 

기존의 코드 로직에서는 차이가 없다.

 

하지만 서브태스크를 보고 50점에서 끝난 이유를 알 수 있었다.

 

N의 개수가 제약 없이 1,000,000개 까지 들어가게 되고 모든 값이 0이나 짝수일 경우 leftCnt와 rightCnt에 저장되는 값이 500,000,500,000으로 int형 범위( -2,147,483,648  ~ 2,147,483,648 ) 약 21억을 넘어가게 되버린다.

 

그래서 처음 입력받는 개수를 저장하는 t를 제외하고 int형 범위를 넘어갈 것이라고 예상되는 나머지 변수의 타입을 long으로 수정해 주었다.