[Java / 백준] 자료구조

<알고리즘 코딩테스트 - Java편> 책 공부

---

1. 배열과 리스트

01. 숫자의 합 구하기

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //숫자의 개수 입력 받음
        String sNum = sc.next();
        char[] cNum = sNum.toCharArray();

        int sum=0;
        for (int i = 0; i < cNum.length; i++) {
            sum += cNum[i]-'0';
        }

        System.out.println(sum);
    }
}

예전에 C++로 다 풀었던 문제들인데 이번에 Java 공부하면서 다시 기초부터 학습하고 있다.
C++에서는 cin으로 String을 통해 받아서 바로 배열 순회했지만... Java에서는 String으로 배열처럼 순회할 수 없다. 따라서 우선 String으로 문자열로서 받은 다음에 toCharArray(); 를 통해 문자 배열로 바꾸는 작업이 필요하다.
그러고나서 배열을 순회하면서 문자로 되어있는 걸 숫자로 계산하기 위해 아스키코드 값을 빼서 계산한다.

★처음에 문자열로 받을 때 nextLine()으로 받았다가 저장이 안 되는 문제가 있었다.
그 이유는 nextInt로 먼저 받을 때
12345/n 식으로 들어온 걸 nextInt가 1234만 저장해서 버퍼에 \n이 그대로 남아있는데,
nextLine()은 개행을 포함해서 한 문자열 전체를 받는 역할이기 때문에 \n을 읽고 그대로 끝내버린다.
반면 next()는 공백을 무시하고 받는 역할이라 그 다음 문자열을 입력받을 수 있게 되는 것이다.

---

02. 평균 구하기

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //시험 본 과목 개수
        int score[] = new int[N]; //개수를 모르기 때문에 동적할당

        for (int i = 0; i < N; i++) {
            score[i] = sc.nextInt();
        }

        long max=0, sum=0;
        for (int i = 0; i < N; i++) {
            if (score[i] > max) {
                max = score[i];
            }
            sum += score[i];
        }
        System.out.println(sum*100/max/N);
    }
}

값을 계산할 때 for문에서 하나씩 할 필요없이, 식을 변형해서 마지막에 한 번에 저렇게 할 수 있지만...
C++.때 풀었던 거 보니까 처음 for문에서 값을 입력받으면서 동시에 최댓값을 계산하고, 두번째 for문에서 정석대로 하나씩 값을 변환하는 거 봐서 그것도 괜찮아 보인다.
실제로 식을 변형할 수 있으면 그게 제일 좋겠지만 못 떠올리는 경우는 그냥 그렇게 하자(...)

---

2. 구간 합

구간 합은 합 배열을 이용해서 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다.

구간 합 알고리즘을 이용하려면 먼저 합 배열을 구해야 하는데, 배열 A가 있을 때 합 배열 S는 다음과 같이 정의된다.

//A[0] ~ A[i]까지의 합
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i];

기존 배열을 전처리한 배열이라 볼 수 있다.

이렇게 합 배열을 미리 구해 놓으면, 기존 배열의 일정 범위 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

배열 A	15	13	10	7
배열 S	15	28	38	45

 

합 배열(S)을 만드는 공식

//그 전의 합이랑 현재 배열 값 더하면 됨
S[i] = S[i-1] + A[i];

 

구간 합을 구하는 공식

//i에서 j까지 구간 합
S[j] - S[i-1];

 

만약 A[2]부터 A[5]까지의 구간 합을 구하고 싶다면

0	1	2	3	4	5
15	13	10	7	3	12
s[5]-	---	---	---	---	--->
s[1]-	--->
		<---	---	---	--->

여기서 하늘색 부분이 구하고자 하는 구간 합 부분이다. 이는 s[5] - s[1]을 통해 한 번의 연산으로 쉽게 구할 수 있는 것이다.

---

03. 구간 합 구하기

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //수의 개수
        int M = sc.nextInt(); //합을 구해야 하는 횟수

        //합 배열 미리 구하기
        int sumArr[] = new int[N+1];
        for (int i = 1; i <= N; i++) {
            sumArr[i] = sumArr[i-1] + sc.nextInt();
        }

        //구간 합 구하기
        int start =0, end=0;
        for (int i = 0; i < M; i++) {
            start = sc.nextInt();
            end = sc.nextInt();
            System.out.println(sumArr[end] - sumArr[start-1]);
        }
    }
}

처음엔 입력 받는 arr을 따로 만들고 그걸로 구간 합을 구하는 식으로 했는데, 그러면 arr은 길이가 N이고 sumArr은 길이가 N+1이라서  for문 돌 때 arr이 인덱스 초과 오류가 발생했다. 
그래서 둘 다 N길이로 똑같이 했는데, 그랬더니 마지막에 구간 합을 구할 때 start가 1인 경우엔 0을 빼야 하는데 합 배열에 그게 없다 보니 따로 if 조건문으로 구분해야 하고 공식도 맞지 않았다.
그래서 결국 책에 있는 정답을 본 결과...
arr 따로 만들 필요 없이 그냥 합 배열 계산할 때 바로 입력을 받으면 됐던 거였다(!)
N+1 길이로 합 배열을 만들고, 굳이 초기화 안 해도 자동으로 0으로 세팅되어 있어서 두번째 칸부터 합을 저장하면 되고... 
그러면 자동으로 구간 합 구할 때 공식 적용하면 start가 1로 시작해도 1-0 = 이미 자동으로 0으로 세팅되어 있음
따라서 공식 그대로 해도 성립된다!

아래는 디버깅 사진으로 각 과정마다 값을 보여준다.

---

04. 구간 합 구하기 2

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

 

구간 합 배열이 2차원인 경우이다.

 

-기존 배열 A[i][j]

	1	2	3
1	1	2	3
2	2	3	4
3	3	4	5

 

-구간 합 배열 D[i][j]

	1	2	3
1	1	3	6
2	3	8	15
3	6	15	27

 

//1행 값 구하기
D[1][j] = D[1][j-1] + A[1][j];

//1열 값 구하기
D[i][1] = D[i-1][1] + A[i][1];

//구간 합 채우는 공식
//: 그 전 값들 더한 다음에 중복 값(대각선 왼쪽) 빼고, 원래 배열 값 더함
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

//질의에 대한 답을 구간 합으로 구하는 방법
//질의 형식: X1, Y1, X2, Y2
//: 질의 구간의 상단 구간 합, 좌측 구간 합 뺀 다음에 중복 값 더하면 됨
D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1];

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //N*N 표의 크기
        int M = sc.nextInt(); //합을 구해야 하는 횟수

        int A[][] = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                A[i][j] = sc.nextInt();
            }
        }
        int D[][] = new int[N+1][N+1];
        //구간 합 구하기
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
            }
        }

        int x1=0, x2=0, y1=0, y2=0, result=0;
        for (int i = 0; i < M; i++) {
            x1 = sc.nextInt();
            y1 = sc.nextInt();
            x2 = sc.nextInt();
            y2 = sc.nextInt();
            //구간 합 배열을 이용하여 질의에 답변하기
            result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
            System.out.println(result);
        }
    }
}

이건 진짜 공식을 외워야 될 것 같은데...
그래도 표 그려가면서 하면 이해는 되니까... 최대한 원리를 이해하고 있자!!

---

05. 나머지 합 구하기

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

 

(A+B) % C   ==   ((A%C) + (B%C)) % C

-> 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과, 구간 합에 나머지 연산을 한 값은 동일하다.

 

구간 합: S[j] - S[i] // i+1부터 j까지의 구간 합

 

if (S[j] % M == S[i] % M) {

   (S[j] - S[i]) % M == 0 이라는 뜻

}

-> 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고, S[j]와 S[i]가 같은 (i, j)쌍을 찾으면

원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있다.

 

1. 문제에서 구하고자 하는 것
: 연속 구간 합이 M으로 나누어 떨어지는 경우의 개수

2. 구간 합을 구해야 하므로 공식 이용
: S[j] - S[i] // i+1부터 j까지의 구간 합

3. 핵심 조건 변형
구하고자 하는 것: (S[j]  -  S[i]) % M == 0
이걸 변형하면: S[j] % M == S[i] % M
→ 구간 합의 나머지가 같으면, 그 사이 구간은 M으로 나누어 떨어짐.

예를 들어
S[i] % 3 = 1
S[j] % 3 = 1
라면 S[j] - S[i] = (3의 배수)이다.  나머지가 같으면 차이는 반드시 M의 배수가 되기 때문이다.

 

따라서 이 문제를 풀 때 구간 합을 먼저 구하고, 그에 대해 나머지 연산을 하면 다음과 같이 된다.

5 3

1 2 3 1 2

입력인 경우

i	S[i]	S[i] % 3
1	1	1
2	3	0
3	6	0
4	7	1
5	9	0

나머지 배열: 1, 0, 0, 1, 0

 

같은 나머지끼리 묶으면

나머지 0 -> 3개

나머지 1 -> 2개

 

쌍 개수를 구해야 하므로 조합을 이용한다.

조합 공식: nC2 = n * (n-1) / 2

0 -> 3C2 = 3

1 -> 2C2 = 1

총합: 3 + 1 = 4

여기서 나머지가 0인 경우는 단독으로도 가능(구간 자체가 이미 조건에 만족)하므로, 0이 3개인 경우도 다시 더해서 총합은 7이 된다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //N개의 수
        int M = sc.nextInt(); //M으로 나누어 떨어지는 수

        long S[] = new long[N]; //합 배열
        S[0] = sc.nextInt();
        for (int i = 1; i < N; i++) {
            S[i] = S[i-1] + sc.nextInt();
        }

        long C[] = new long[M]; //나머지 배열
        int remainder = 0;
        long answer = 0;
        for (int i = 0; i < N; i++) {
            remainder = (int) (S[i] % M); //인덱스로 쓸 거라 int로 캐스팅
            if(remainder == 0) { //구간 합의 나머지가 0일 때
                answer++;
            }
            C[remainder]++; //나머지가 같은 인덱스 개수 카운팅하기
        }
        for (int i = 0; i < M; i++) {
            if(C[i] > 1) { //나머지가 같은 게 최소 2개 이상 있음
                answer = answer + (C[i] * (C[i]-1) / 2);
            }
        }
        System.out.println(answer);
    }
}

---