BAEKJOON 7568๋ฒˆ ๋ฉ์น˜๐Ÿ™ˆ

๐Ÿ‘ธ๐Ÿป ๋ฉ์น˜๋ฌธ์ œ์™€ ํ•จ๊ป˜ ๋Œ์•„์™”์Šต๋‹ˆ๋‹ค^^

๋ฉ์น˜๋ฌธ์ œ๋Š” ๋ฐฑ์ค€์˜ 7568๋ฒˆ์˜ ๋ฌธ์ œ๋กœ ์™„์ „ํƒ์ƒ‰๊ณผ ๊ด€๋ จ๋œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๐Ÿคท๐Ÿปโ€โ™€๏ธ ์™„์ „ํƒ์ƒ‰? ๊ทธ๊ฒŒ๋ญ”๋ฐ? what?

๐Ÿ“Œ ์™„์ „ํƒ์ƒ‰์ด๋ž€? '๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ „๋ถ€ ์ฐพ์•„์„œ ๋‹ต์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜' ์„ ๋œปํ•œ๋‹ค. ์˜์–ด๋กœ๋Š” Exhaustive Search ๋ผ๊ณ  ํ•œ๋‹ค. ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋‹ค ํ•ด๋ณด๋Š” ๊ฒƒ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ’€๋•Œ ๊ฐ€์žฅ ๊ฐ•๋ ฅํ•˜๊ณ  ํ™•์‹คํ•œ ๋ฐฉ๋ฒ•์ด์ง€๋งŒ ๊ทธ๋งŒํผ ์‹œ๊ฐ„์ด ๊ฐ€์žฅ ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋Š” ํƒ์ƒ‰ ๊ธฐ๋ฒ•์ด๋‹ค.

์™„์ „ํƒ์ƒ‰ ๊ธฐ๋ฒ•์˜ ์ข…๋ฅ˜

  • Brute Force : for๋ฌธ๊ณผ if๋ฌธ์„ ์ด์šฉํ•˜์—ฌ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•
  • ๋น„ํŠธ ๋งˆ์Šคํฌ : ์ด์ง„์ˆ˜ ํ‘œํ˜„์„ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ ์“ฐ๋Š” ๊ธฐ๋ฒ• (AND, OR, XOR, SHIFT, NOT)
  • ์žฌ๊ท€ ํ•จ์ˆ˜
  • ์ˆœ์—ด : ์„œ๋กœ ๋‹ค๋ฅธ n๊ฐœ์˜ ์›์†Œ์—์„œ r๊ฐœ์˜ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๊ณ  ์ˆœ์„œ๋Œ€๋กœ ๋Š˜์–ด ๋†“์€ ์ˆ˜
  • BFS(๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰), DFS(๊นŠ์ด์šฐ์„ ํƒ์ƒ‰)

    ์œ„์˜ ์‚ฌ์ง„์€ ๋งจ ๋งˆ์ง€๋ง‰ ๋ฐฉ๋ฒ•์ธ DFS / BFS์˜ ์‚ฌ์ง„์ด๋ฉฐ ์ด๋ฅผ ์ดํ•ดํ•˜๊ธฐ ์œ„ํ•ด์„  ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์•Œ์•„์•ผ ํ•œ๋‹ค. ์ด๋Š” ๋‹ค์Œ๋ฌธ์ œ ํ’€ ๋•Œ ๋‹ค๋ฃจ์–ด ๋ณด์ž! ์ง€๊ธˆ ํฌ์ŠคํŒ…์—” ์™„์ „ ํƒ์ƒ‰์˜ ์ดํ•ด๋งŒ ํ•ด๋ณด์ž ๐Ÿ™†๐Ÿปโ€โ™‚๏ธ

    ์ด ๋‹ค์„ฏ๊ฐœ์˜ ์™„์ „ํƒ์ƒ‰์˜ ๊ธฐ๋ฒ•์ด ์žˆ๋Š”๋ฐ 3์ฃผ์ฐจ์˜ ๋ฌธ์ œ๋Š” for๋ฌธ๊ณผ if๋ฌธ์„ ์ด์šฉํ•œ ๋ฌธ์ œ์˜€๋‹ค.

๋ฐฑ์ค€ ๋งํฌ ๊ฐ€๊ธฐ
https://www.acmicpc.net/problem/7568

์œ„์™€ ๊ฐ™์€ ๋ฌธ์ œ์ด๋‹ค. Scanner๋ฅผ ์ด์šฉํ•ด ์ž…๋ ฅ๋ฐ›์€ ๋’ค ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•˜์˜€๋‹ค. ์ฒ˜์Œ ์–ด๋ ค์›€์„ ๋Š๋‚€ ๋ถ€๋ถ„์€ 2์ฐจ ๋ฐฐ์—ด์„ ๊นŒ๋จน์–ด์„œ .... ์ƒ๊ฐํ•˜๋Š”๋ฐ 10๋ถ„์ •๋„ ์žก์•„๋จน์€ ๊ฒƒ ๊ฐ™๋‹ค... ๋‚˜์˜ ๋จธ๋ฆฌ ๊ธˆ๋ถ•์–ด ๋จธ๋ฆฌ ๐Ÿก

Scanner๋ฅผ ์ด์šฉํ•ด์„œ ํ’€์ดํ•œ ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

Scanner๋ฅผ ์ด์šฉํ•œ ์ฝ”๋“œ ๋ณด๊ธฐ ๐Ÿ‘€
import java.io.IOException;
import java.util.Scanner;

public class ๋ฉ์น˜๋ฌธ์ œ_7568 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		//์™„์ „ ํƒ์ƒ‰ ๋ฌธ์ œ (๋ฐฑ์ค€-7568๋ฒˆ)
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);//scanner๋ฅผ์ด์šฉํ•œ ๋ฌธ์ œํ’€์ด
		int cnt = sc.nextInt();
		
		int[][] person = new int[cnt][2];//cnt๊ฐœ์ˆ˜๋งŒํผ ๋ฐฐ์—ด ์ƒ์„ฑ ๊ทธ ์•ˆ์˜ ๋ฐฐ์—ด์€ ํ‚ค ๋ชธ๋ฌด๊ฒŒ = 2๊ฐœ
		int rank[] = new int[cnt];//๋“ฑ์ˆ˜๋ฅผ ์ž…๋ ฅํ•  ๋ฐฐ์—ด
		
		for(int i=0;i<person.length;i++) {
			person[i][0] = sc.nextInt();//๋ชธ๋ฌด๊ฒŒ
			person[i][1] = sc.nextInt();//ํ‚ค
			rank[i] = 1;//๋“ฑ์ˆ˜๋ฅผ ์ „๋ถ€ 1๋“ฑ์ด๋ผ๊ณ  ์„ ์–ธ
		}
		
		for(int i=0;i<person.length;i++) {//๋น„๊ตํ•  ๊ธฐ์ค€์ด ๋˜๋Š” ๋ฒˆํ˜ธ
			for(int j=0;j<person.length;j++) {//๋น„๊ตํ•  ๋Œ€์ƒ์ด ๋˜๋Š” ๋ฒˆํ˜ธ
				if(person[i][0] > person[j][0] && person[i][1] > person[j][1]) {
					rank[j]++;
				}
			}
		}
		for(int i=0;i<person.length;i++) {
			System.out.print(rank[i]+" ");
		}
	}
}

์ž…๋ ฅ๋œ ์ˆซ์ž๋งŒํผ **int person[][]=new int[์ž…๋ ฅ๋ฐ›์€ ๊ฐ’๋งŒํผ][2(ํ‚ค,๋ชธ๋ฌด๊ฒŒ)]**์„ ์ƒ์„ฑํ•˜์˜€๊ณ  ๋“ฑ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด๋„ ๋”ฐ๋กœ ๋งŒ๋“ค์—ˆ๋‹ค. for๋ฌธ์„ ์ด์šฉํ•ด ๋ชธ๋ฌด๊ฒŒ์™€ ํ‚ค๋ฅผ ์ €์žฅ & rank๋ฅผ ์ „๋ถ€ 1๋“ฑ์œผ๋กœ ์„ค์ •ํ•ด์ฃผ์—ˆ๋‹ค.

๊ทธ ๋‹ค์Œ 2์ค‘ for๋ฌธ์„ ๋Œ๋ ค (Why๐Ÿคท๐Ÿปโ€โ™‚๏ธ? 2์ฐจ์—ด ๋ฐฐ์—ด์ด๋‹ˆ๊นŒ~) ๋น„๊ต ๊ธฐ์ค€๊ณผ ๋Œ€์ƒ์„ ๋น„๊ต๋ฅผ ํ•ด์ฃผ์—ˆ๊ณ , ๋งŒ์•ฝ ๋น„๊ต๊ธฐ์ค€์ด ๋Œ€์ƒ๋ณด๋‹ค ๋ชธ๋ฌด๊ฒŒ๋ž‘ ํ‚ค๊ฐ€ ๋ชจ๋‘ ํฌ๋‹ค๋ฉด ๋น„๊ต ๋Œ€์ƒ์— rank++ํ•ด์ฃผ์–ด ๋“ฑ์ˆ˜๊ฐ€ ๋’ค๋กœ ๋ฐ€๋ฆฌ๋„๋ก ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ–ˆ๋‹ค.

๋ฐฑ์ค€ ์ฒด์ ์— ๋งž์•˜์Šต๋‹ˆ๋‹ค!! ๋ฅผ ๋ณด๊ธด ํ–ˆ์ง€๋งŒ ์ „๋ถ€ ์ž‘์„ฑํ•˜๊ณ  ๋ณด๋‹ˆ Scanner๋Š” ๋งค์šฐ ๋น„ํšจ์œจ์ ์ธ ๊ฒƒ ๊ฐ™์€ ๋Š๋‚Œ... ๊ทธ๋ž˜์„œ StringBuffer๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ•ด๋ดค์ง€๋งŒ ๊ณ„์† ๋Ÿฐํƒ€์ž„์—๋Ÿฌ๊ฐ€ ๋‚ฌ๋‹ค. ์™ ์ง€ ์‚ดํŽด๋ณด๊ณ  StringBuffer๋ฅผ ์ด์šฉํ•ด์„œ ๋‹ค์‹œ ์ž‘์„ฑํ•ด๋ด์•ผ๊ฒ ๋‹ค..ใ…Žใ…Ž ๋‹ค์‹œ ๋Œ์•„์˜ฌ๊ฒŒ์šฉ~

Buffer์™€ (๋Ÿฐํƒ€์ž„์—๋Ÿฌ์™€) ์ปด๋ฐฑํ•œ ์—ฐ์žฌ ๐Ÿ˜Ž

StringBuffer๋ฅผ ์ด์šฉํ•œ ์ฝ”๋“œ ๋ณด๊ธฐ ๐Ÿงธ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class ๋ฉ์น˜๋ฌธ์ œ2_7569 {
	public static void main(String[] args) throws IOException {
		//์™„์ „ ํƒ์ƒ‰ ๋ฌธ์ œ (๋ฐฑ์ค€-7568๋ฒˆ)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int cnt = Integer.parseInt(br.readLine());
		int[][] person = new int[cnt][2];//cnt๊ฐœ์ˆ˜๋งŒํผ ๋ฐฐ์—ด ์ƒ์„ฑ ๊ทธ ์•ˆ์˜ ๋ฐฐ์—ด์€ ํ‚ค ๋ชธ๋ฌด๊ฒŒ = 2๊ฐœ
		int rank[] = new int[cnt];//๋“ฑ์ˆ˜๋ฅผ ์ž…๋ ฅํ•  ๋ฐฐ์—ด
		
		for(int i=0;i<person.length;i++) {
			person[i][0] = Integer.parseInt(br.readLine());//๋ชธ๋ฌด๊ฒŒ
			person[i][1] = Integer.parseInt(br.readLine());//ํ‚ค
			rank[i] = 1;//๋“ฑ์ˆ˜๋ฅผ ์ „๋ถ€ 1๋“ฑ์ด๋ผ๊ณ  ์„ ์–ธ
		}
		
		for(int i=0;i<person.length;i++) {//๋น„๊ตํ•  ๊ธฐ์ค€์ด ๋˜๋Š” ๋ฒˆํ˜ธ
			for(int j=0;j<person.length;j++) {//๋น„๊ตํ•  ๋Œ€์ƒ์ด ๋˜๋Š” ๋ฒˆํ˜ธ
				if(person[i][0] > person[j][0] && person[i][1] > person[j][1]) {
					rank[j]++;
				}
			}
		}
		for(int i=0;i<person.length;i++) {
			System.out.print(rank[i]+" ");
		}
	}
}

์Œ...์ฝ˜์†”์—๋Š” ๋‹ต์ด ๋‚˜์™€์š”..? ๊ทผ๋ฐ ๋ฐฑ์ค€์ด ์ธ์ •์„ ์•ˆํ•ด์ค˜ ๐Ÿคฌ ์ง„์งœ ํ™”๊ฐ€๋‚˜~ ^^ ๋ฐฑ์ค€ ๋ญ๊ฐ€ ๊ทธ๋ฆฌ ๊นŒ๋‹ค๋กญ๋‹ˆ~~~ ํ˜น์‹œ ์™œ ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ ๋‚˜๋Š”์ง€ ์•Œ๋ ค์ฃผ์‹ค ๋ถ„ ์—†๋‚˜์š”... ใ…Žใ…Žใ…Žใ…Žใ…Žใ…Žใ…Ž

๋ฐฑ์ค€์ด ์ธ์ •์„ ํ•ด์ค˜์•ผ ๋น„๊ต๋ฅผ ํ•˜๋˜๋ง๋˜ ํ•˜์ง€ ใ… ใ…  ๋น„๊ต๋„ ๋ชปํ•˜๊ฒŒ ํ•ด ๐Ÿ˜ฅ ์•„๋ฌดํŠผ StringBuffer๋กœ๋„ ํ’€์—ˆ๋‹ค..

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ