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๋ก๋ ํ์๋ค..
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(BAEKJOON 7568๋ฒ ๋ฉ์น๐), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@yeonjae/BAEKJOON-7568๋ฒ-๋ฉ์น์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค