[SWEA] 5644 무선충전 - JAVA

1. 문제

SW Expert Academy

지도는 10*10 크기다.

배터리충전기(BC) 위치, 충전범위, 성능이 주어진다.

(1,1)위치와 (10,10)위치에 한 사람씩 있고, 1초에 한 번씩 M초동안 움직이는 동안 BC의 충전 범위 안에 들어갈 때 접속한 BC의 성능만큼 충전할 수 있다.

한 BC에 두 명의 사용자가 접속한 경우, 접속한 사용자의 수만큼 충전양을 균등하게 분배한다.

두 지점 사이의 거리는 |Xa-Xb|+|Ya-Yb|로 구한다.

---

2. 풀이

BC, Location 클래스

BC, Location 클래스를 만들었다. 굳이 만들지 않아도 되는데, 배열로 하다간 너무 복잡해서 헷갈릴까봐 만들었다.

BC에는 입력받은 위치에서 충전이 가능한지 반환하는 isAvailable 메서드가 있다.

Location에는 입력받은 위치와 본인 위치의 거리를 반환하는 calcDistance가 있다.

calcDistance를 이용해서 isAvailable을 계산했다.

class BC {
    Location location;
    int coverage;
    int performance;

    BC(String x, String y, String coverage, String performance) {
        this.location = new Location(Integer.parseInt(x), Integer.parseInt(y));
        this.coverage = Integer.parseInt(coverage);
        this.performance = Integer.parseInt(performance);
    }

    boolean isAvailable(Location o) {
        return coverage >= location.calcDistance(o);
    }
}

class Location {
    int x;
    int y;

    Location(int x, int y) {
        this.x = x;
        this.y = y;
    }

    int calcDistance(Location o) {
        return Math.abs(x - o.x) + Math.abs(y - o.y);
    }
}

 

static 변수들

static BC[] bc;
static StringBuilder sb = new StringBuilder();
static int[][] deltas = {{0, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 0}};//x,y순, 이동없음 상 우 하 좌
static Location[][] people;

 

입력 부분

특별한 건 없고 대신 people배열에 처음위치를 넣어줬다. ( (1,1)이랑 (10,10) )

보면 StringTokenizer로 자른 문자열을 바로 BC에 넣어버렸는데 하나하나 파싱하기 싫어서 BC클래스 생성자에서 파싱해줬다.

st = new StringTokenizer(in.readLine());
int M = Integer.parseInt(st.nextToken());//이동시간
int A = Integer.parseInt(st.nextToken());//BC 개수

people = new Location[M + 1][2];

//사용자 위치
people[0][0] = new Location(1, 1);
people[0][1] = new Location(10, 10);
for (int i = 0; i < 2; i++) {
    st = new StringTokenizer(in.readLine());
    for (int m = 1; m <= M; m++) {
        int d = Integer.parseInt(st.nextToken());
        people[m][i] = new Location(people[m - 1][i].x + deltas[d][0], people[m - 1][i].y + deltas[d][1]);
    }
}

//배터리 충전기
bc = new BC[A];
for (int a = 0; a < A; a++) {
    st = new StringTokenizer(in.readLine());
    bc[a] = new BC(st.nextToken(), st.nextToken(), st.nextToken(), st.nextToken());
}

 

탐색

(M+1번--> 처음 위치도 포함시켜야 하기 때문이다)

1. 사람마다 가능한 배터리 인덱스를 리스트에 각각 추가한다. 이 때 BC클래스의 isAvailable 메서드를 활용한다.

2. 전부 탐색했으면 리스트를 저장한 인덱스를 이용해 "성능" 내림차순으로 정렬한다.

3. 둘 다 list 사이즈가 0이면 더할 게 없으므로 넘어간다.

4. 둘 다 하나 이상이라면 비교를 시작한다.

• 내림차순으로 정렬했으므로 반복은 각각 2나 list사이즈 중 작은 만큼만 돌게 한다. 
• 만약 리스트에 저장된 인덱스가 서로 같다면 그 성능값 하나와 이미 저장된 tmpMax를 비교해 큰 값을 넣는다.
• 같지 않다면 tmpMax와 둘 성능을 더한 값을 비교하고 더 큰 값을 저장한다.

5. 둘 중 하나가 0이라면 나머지 list의 첫번째 인덱스로 성능값을 찾아서 저장한다.

6. 최종 sum에 tmpMax를 저장한다.

7. 다음 비교를 위해 list를 비운다.

//M+1만큼 탐색
int sum = 0;
List<Integer> tmpD1 = new ArrayList<>(), tmpD2 = new ArrayList<>();
for (int m = 0; m <= M; m++) {
    //가능한 배터리 모두 list에 추가
    for (int a = 0; a < A; a++) {
        if (bc[a].isAvailable(people[m][0])) tmpD1.add(a);
        if (bc[a].isAvailable(people[m][1])) tmpD2.add(a);
    }

    Collections.sort(tmpD1, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return bc[o2].performance-bc[o1].performance;
        }
    });
    Collections.sort(tmpD2, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return bc[o2].performance-bc[o1].performance;
        }
    });

    //가능한 배터리 중 어떤 선택이 나은지 체크
    int tmpMax = 0;
    // 둘 다 가능한 게 없으면 넘어감
    if (tmpD1.size() == 0 && tmpD2.size() == 0) continue;


    // 둘 다 하나 이상
    if (tmpD1.size() >= 1 && tmpD2.size() >= 1) {

        for(int i=0;i<Math.min(2,tmpD1.size());i++){

            for(int j=0;j<Math.min(2,tmpD2.size());j++){

                if(tmpD1.get(i).equals(tmpD2.get(j))) tmpMax = Math.max(tmpMax, bc[tmpD1.get(i)].performance);
                else tmpMax = Math.max(tmpMax, bc[tmpD1.get(i)].performance + bc[tmpD2.get(j)].performance);

            }
        }

    }
    //둘 중 하나가 0개
    else if (tmpD1.size() == 0) {
        tmpMax = bc[tmpD2.get(0)].performance;

    } else {// else if(tmpD2.size()==0){
        tmpMax = bc[tmpD1.get(0)].performance;
    }

    //합계추가
    sum += tmpMax;

    //다음 반복을 위해 list clear
    tmpD1.clear();
    tmpD2.clear();
}

---

3. 결과

처음에 정렬하지 않고 하나하나 다 비교했더니 200ms 넘는 시간이 들었다. 

정렬하고 최대 두개씩만 비교하니 시간이 훨씬 줄었다.