[BOJ] 백준 1797번 : 균형잡힌 줄서기 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1797

1797번: 균형잡힌 줄서기

문제

소시갤 회장 항승이는 클럽에 회원들을 모아놓고 함께 소녀시대 춤을 추고 난 뒤 팬들에게 소녀시대 춤에서 마지막 부분에 나오는 멤버들이 한 줄로 모이는 부분을 안무 해주고 있었다.

안무를 하던 중 항승이는 한 줄로 선 상태에서 이들 중 연속된 사람들을 그룹 지었을 때, 이 그룹에 속한 남녀의 수가 같은 그룹이 가장 보기 좋다는 것을 알았다.

그래서 항승이는 팬들이 한 줄로 섰을 때 위의 조건을 만족하는 그룹 중 가장 길이가 긴 그룹을 찾고자 한다. 가장 길이가 길다는 의미는 그룹에서 x좌표가 가장 작은 사람과 큰 사람의 차이가 가장 크다는 것이다. 우리는 이런 항승이를 도와주자.

 

풀이

누적합과 정렬을 이용하는 문제였습니다. 어떻게 하면 그룹을 묶었을 때, 남자와 여자의 수가 동일한지 판단하는 것이 관건이었고, 성별의 누적합을 구하면 해결할 수 있었습니다.

단, 여기서 남자의 성별은 0으로 표시하는데, 그 대신 -1로 표기해야 가능합니다. 로직은 아래와 같습니다.

1. 남자의 성별은 -1, 여자의 성별은 1로 표시하면서, 성별과 x 좌표를 담은 객체(member) 배열을 만든다.

2. x 좌표를 기준으로 배열을 오름차순 정렬한다.

3. 성별에 대한 누적합을 만든다.

4. 누적합이 같은 인덱스끼리 따로 list에 저장한다.

5. 각 list마다 맨 끝 인덱스에 해당하는 member의 x 좌표와 맨 처음 + 1 인덱스에 해당하는 member의 x 좌표 사이의 거리를 구하면서 최댓값을 구한다.

 

예제

풀이만 가지고는 명확하게 이해하기는 어렵다고 생각해서 예제와 함께 자세하게 설명하겠습니다.

 

7

0 11

1 10

1 25

1 12

1 4

0 13

1 22

 

member 배열을 만들어서 위 정보를 입력받습니다.

그리고 x좌표끼리 정렬을 하면 다음과 같습니다. (남자는 원, 여자는 세모로 표시)

여기서 성별에 대해서 누적합을 구해보면 아래와 같습니다. (위는 인덱스, 아래는 누적합을 의미합니다.)

0	1	2	3	4	5	6
1	2	1	2	1	2	3

누적합을 구하는 이유는 누적합이 동일한 인덱스끼리 보면 알 수 있습니다.

예를 들어, 1번째와 5번째 인덱스는 같기때문에 2번째 ~ 5번째 인덱스를 하나의 그룹으로 묶을 수 있습니다.

이것이 왜 성립할까요?

1번쨰와 5번째 누적합이 같다는 소리는, 2번째부터 5번째 인덱스의 증가 폭이 0이라는 의미이므로 남, 녀, 남, 녀와 같은 식으로 남자와 여자의 비율이 같게 됩니다.

따라서, 누적합을 구한 뒤, 누적합이 동일한 인덱스는 따로 list를 만들어서 관리해 줍니다.

저는 ArrayList<ArrayList<Integer>>를 통해 구현하였고, 위 예제를 따르면,

0 = {}, 1 = {0, 2, 4}, 2 = {1, 3, 5}, 3 = {6}이 될 것입니다.

그리고 ArrayList.get(i)의 size가 2이상인 영역만 검사를 합니다. 위에 경우에는 1, 2번째 인덱스가 해당이 됩니다.

1의 경우, member[4].x - member[1].x = 13 - 10 = 3. 2의 경우, member[5].x - member[2].x = 22 - 11 = 11이 되므로 결과적으로 최댓값은 11이 되는 것을 알 수 있습니다.

 

주의 사항

위 예제에 경우, x좌표를 기준으로 오름차순 정렬을 하였을 때, 여자가 먼저 오고, 누적합도 음수가 오지 않았습니다. 이 쯤되면 눈치채셨겠지만, 누적합이 음수가 될 경우 ArrayList에 담을 수 없습니다.

따라서, 저는 ArrayList에 누적합을 담을 때는 ArrayList.get(sum[i]).add()가 아니라, ArrayList.get(sum[i] + 1000000).add()으로 하였습니다. 문제에서 N은 최대 1000000이고, 모두 같은 성별은 아니기때문에 모든 범위에 대해서 음수를 방지할 수있게 됩니다.

 

아래는 위 로직을 구현한 소스코드입니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Member implements Comparable<Member> {
    int gender;
    int x;
 
    Member(int gender, int x) {
        this.gender = gender;
        this.x = x;
    }
 
    @Override
    public int compareTo(Member o) {
        return x - o.x;
    }
}
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
 
        final int MAX = 1000000;
        Member[] members = new Member[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int gender = Integer.parseInt(st.nextToken());
 
            if (gender == 0) { // 남자일 경우 0 대신 -1로 초기화
                gender = -1;
            }
 
            int x = Integer.parseInt(st.nextToken());
 
            members[i] = new Member(gender, x);
        }
        Arrays.sort(members); // x를 기준으로 오름차순.
 
        if (N == 2) { // N이 2일 때는 단순히 둘 사이의 거리를 뺸다. (예외 처리)
            bw.write((members[1].x - members[0].x) + "\n");
            bw.close();
            br.close();
            return;
        }
 
        int[] sum = new int[N]; // gender의 누적합
        sum[0] = members[0].gender;
 
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i - 1] + members[i].gender;
        }
 
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= N + MAX; i++) {
            a.add(new ArrayList<>());
        }
 
        // 누적합이 같은 것끼리 묶는다.
        for (int i = 0; i < N; i++) {
            a.get(sum[i] + MAX).add(i);
        }
 
        int ans = 0;
        for (int i = 0; i < N + MAX; i++) {
            int temp = 0;
            if (a.get(i).size() > 1) {
                // 누적합이 같은 리스트 중에서 가장 처음 + 1 인덱스와 맨 끝 인덱스에 해당하는
                // members의 x 사이의 거리를 구한다.
                int end = a.get(i).get(a.get(i).size() - 1);
                int start = a.get(i).get(0) + 1;
 
                temp = members[end].x - members[start].x;
            }
            ans = Math.max(ans, temp);
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.