[Java] 백준 10800 컬러볼

10800 컬러볼 문제 링크

#1

package forStudy.month04;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_10800 {
	public static class Node implements Comparable<Node> {
		int index;
		int color;
		int size;
		
		public Node(int index, int color, int size) {
			this.index = index;
			this.color = color;
			this.size = size;
		}
		
		public int compareTo(Node o) {
			return Integer.compare(o.size, size);
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Node> ball = new ArrayList<>();
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			ball.add(new Node(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		
		Collections.sort(ball);
		
		int[] answer = new int[N];
		
		Node n;
		for(int i=0; i<N; i++) {
			n = ball.get(i);
			for(int j=i+1; j<N; j++) {
				if(ball.get(j).color != n.color && ball.get(j).size < n.size) 
					answer[n.index] += ball.get(j).size;
			}
		}
		
		for(int i=0; i<N; i++) {
			System.out.println(answer[i]);
		}
		
	}
}

• 시간초과가 날 것 같긴 했는데.. 진짜 남..
  
  
• 그래서 투 포인터 생각함
• Node[] middle 이라는 배열 하나 만들어서 여기에 색을 index 값으로 해서 넣어놓고 갱신하는 방식으로 색이 같은 공의 사이즈 값을 결과에서 빼주는 방식 생각했는데..
• 이렇게 하면 사이즈 값이 중복이 되는 경우를 또 따로 생각해줘야 함.. 그래서 투 포인터는 불가능 하다고 판단
  
  
• 어??? 근데 이거 정렬을 내가 반대로 생각한 거 같기도 하고??

#2

package forStudy.month04;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_10800 {
	public static class Node implements Comparable<Node> {
		int index;
		int color;
		int size;
		
		public Node(int index, int color, int size) {
			this.index = index;
			this.color = color;
			this.size = size;
		}
		
		public int compareTo(Node o) {
			return Integer.compare(size, o.size);
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Node> ball = new ArrayList<>();
		int colorMax = 0;
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			ball.add(new Node(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			colorMax = Math.max(colorMax, ball.get(i).color);
		}
		
		Collections.sort(ball);
		
		int[] answer = new int[N];
		int[] sum = new int[colorMax+1];
		
		
		int before = 0;
		int sumV = 0;
		int same = 0;
		for(int i=0; i<N; i++) {
			// 이전 공과 사이즈가 현재와 다른 경우
			if(before != ball.get(i).size) {
				// 총합 값 갱신
				sumV += same;
				same = 0;
				
			}
			// 이전 공 사이즈 갱신
			before = ball.get(i).size;
			// 중복 색의 값 빼고 answer에 값 넣기
			answer[ball.get(i).index] = sumV - sum[ball.get(i).color];
			// 색 별 중복 값 넣어주기
			sum[ball.get(i).color] += ball.get(i).size;
			// 
			same += ball.get(i).size;

		}
		
		for(int i=0; i<N; i++) {
			System.out.println(answer[i]);
		}
		
	}
}

• 이게 공의 색이 같은 경우나 사이즈가 같은 경우를 각각 고려는 잘 됐는데 색이 같고 사이즈가 같은 경우는 고려가 되지 않음..
• 근데 이런 조건 하나만 추가 하기는 좀.. 너무 복잡해짐..

#3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	public static class Node implements Comparable<Node> {
		int index;
		int color;
		int size;
		
		public Node(int index, int color, int size) {
			this.index = index;
			this.color = color;
			this.size = size;
		}
		
		public int compareTo(Node o) {
			return Integer.compare(size, o.size);
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Node> ball = new ArrayList<>();
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			ball.add(new Node(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		
		Collections.sort(ball);
		
		int[] answer = new int[N];
		int[] sum = new int[N+1];
		
		
		int sumV = 0;
		int index = 0;
		for(int i=0; i<N; i++) {
			// 현재 공 하나 빼오기
			Node now = ball.get(i);
			
			while(ball.get(index).size < now.size) {
				// 현재 공보다 작은 공의 누적 합 구하기
				sumV += ball.get(index).size;
				// 공의 색 별로 누적합 구하기
				sum[ball.get(index).color] += ball.get(index).size;
				index++;
			}
			
			answer[now.index] = sumV - sum[now.color];
			

		}
		
		for(int i=0; i<N; i++) {
			System.out.println(answer[i]);
		}
		
	}
}

• 진짜 말이 안됨..
• 거의 비슷하게 생각은 했는데.. 중간중간 꼬여가지고 이렇게 조합은 못 해봤네...