1. 문제
지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.
공 | 번호색 | 크기 |
1 | 1 | 10 |
2 | 3 | 15 |
3 | 1 | 3 |
4 | 4 | 8 |
이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다.
공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오.
2. 풀이
Ball 클래스
public static class Ball {
int color, size, idx;
Ball(int idx, int color, int size) {
this.idx = idx;
this.color = color;
this.size = size;
}
}
Main
1. Ball[]에 입력받은 뒤 사이즈 순으로 정렬한다. 만약 사이즈가 동일하다면 색 번호 순으로 정렬한다.
2. answer은 정답 저장 배열, color는 색 별 누적합 배열이다. sum에 전체 누적합을 저장하고 size,count에는 직전 공 크기와 그 크기가 총 몇 번 나왔는지 저장해둔다.
3. 직전 정보를 prev에 저장한다.
4. balls 배열을 하나씩 탐색한다.
4-1. 만약 직전과 사이즈가 다르다면 전체 누적합에서 현재 색의 누적합을 뺀다.
4-2. 만약 직전과 사이즈가 같고 색이 다르다면 전체 누적합에서 현재 색 누적합과 count*size를 뺀다.
4-3. 만약 직전과 사이즈가 같고 색도 같다면 직전 답을 그대로 저장한다.
4-4. 사이즈비교가 끝났다면 sum과 color[현재색]에 사이즈를 더한다. prev도 교체한다.
5. answer을 하나씩 sb에 더해서 출력한다.
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
StringTokenizer st;
//입력
Ball[] balls = new Ball[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
balls[i] = new Ball(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
Arrays.sort(balls, (o1, o2) -> {
if (o1.size == o2.size) return o1.color - o2.color;
else return o1.size - o2.size;
});
int[] answer = new int[N];//답 저장
int[] color = new int[N + 1];//색 별 누적합
int sum = 0;//전체 누적합
int size = 0, count = 0;//직전 공 크기, 개수
Ball prev = null;
for (Ball ball : balls) {
answer[ball.idx] = sum - color[ball.color];
if (size == ball.size) {
if (prev != null && ball.color == prev.color) {
answer[ball.idx] = answer[prev.idx];
} else {
answer[ball.idx] -= count * size;
}
count++;
} else {
size = ball.size;
count = 1;
}
sum += ball.size;
color[ball.color] += ball.size;
prev = ball;
}
//출력
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(answer[i]).append('\n');
}
System.out.print(sb);
}
3. 결과
사이즈와 크기가 동일한 공이 조건에 포함되는 지 몰라서 틀렸다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 2616 소형기관차 - JAVA (0) | 2023.04.10 |
---|---|
[BOJ] 4659 비밀번호 발음하기 - JAVA (0) | 2023.04.09 |
[BOJ] 13900 순서쌍의 곱의 합 - JAVA (0) | 2023.04.07 |
[BOJ] 17425 약수의 합 - JAVA (0) | 2023.04.06 |
[BOJ] 16139 인간-컴퓨터 상호작용 - JAVA (0) | 2023.04.05 |
댓글