๊ณ ์๋๋ก๋ฅผ ์ด๋ํ๋ ๋ชจ๋ ์ฐจ๋์ด ๊ณ ์๋๋ก๋ฅผ ์ด์ฉํ๋ฉด์ ๋จ์์ฉ ์นด๋ฉ๋ผ๋ฅผ ํ ๋ฒ์ ๋ง๋๋๋ก ์นด๋ฉ๋ผ๋ฅผ ์ค์นํ๋ ค๊ณ ํฉ๋๋ค.
๊ณ ์๋๋ก๋ฅผ ์ด๋ํ๋ ์ฐจ๋์ ๊ฒฝ๋ก routes๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฐจ๋์ด ํ ๋ฒ์ ๋จ์์ฉ ์นด๋ฉ๋ผ๋ฅผ ๋ง๋๋๋ก ํ๋ ค๋ฉด ์ต์ ๋ช ๋์ ์นด๋ฉ๋ผ๋ฅผ ์ค์นํด์ผ ํ๋์ง๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์.
์ ํ์ฌํญ
์ฐจ๋์ ๋์๋ 1๋ ์ด์ 10,000๋ ์ดํ์ ๋๋ค.
routes์๋ ์ฐจ๋์ ์ด๋ ๊ฒฝ๋ก๊ฐ ํฌํจ๋์ด ์์ผ๋ฉฐ
routes[i][0]์๋ i๋ฒ์งธ ์ฐจ๋์ด ๊ณ ์๋๋ก์ ์ง์ ํ ์ง์ , routes[i][1]์๋ i๋ฒ์งธ ์ฐจ๋์ด ๊ณ ์๋๋ก์์ ๋๊ฐ ์ง์ ์ด ์ ํ ์์ต๋๋ค.
์ฐจ๋์ ์ง์ /์ง์ถ ์ง์ ์ ์นด๋ฉ๋ผ๊ฐ ์ค์น๋์ด ์์ด๋ ์นด๋ฉ๋ผ๋ฅผ ๋ง๋๊ฒ์ผ๋ก ๊ฐ์ฃผํฉ๋๋ค.
์ฐจ๋์ ์ง์ ์ง์ , ์ง์ถ ์ง์ ์ -30,000 ์ด์ 30,000 ์ดํ์ ๋๋ค.
์ ์ถ๋ ฅ ์
routes : [[-20,15], [-14,-5], [-18,-13], [-5,-3]]
return : 2
๐ก ๋๊ฐ๋ ์์ ์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
๐ก ์์ ์ฐจ๊ฐ ๋๊ฐ๋ ์๊ฐ๊ณผ ๋ค์ ์ฐจ๊ฐ ๋ค์ด์ค๋ ์๊ฐ์ ๋น๊ตํ์ฌ ํ์๋ฅผ ์ธ์ค
1) ๋๊ฐ๋ ์์ ์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
Arrays.sort(routes, new Comparator<int[]>(){
@Override
public int compare(int[] r1, int[] r2){
return r1[1] - r2[1];
}
});
2) ์์ ์ฐจ๊ฐ ๋๊ฐ๋ ์๊ฐ๊ณผ ๋ค์ ์ฐจ๊ฐ ๋ค์ด์ค๋ ์๊ฐ์ ๋น๊ตํ์ฌ ํ์๋ฅผ ์ธ์ค
if(time < routes[i][0]){
answer++;
time = routes[i][1];
}
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public int solution(int[][] routes) {
int answer = 1;
Arrays.sort(routes, new Comparator<int[]>(){
@Override
public int compare(int[] r1, int[] r2){
return r1[1] - r2[1];
}
});
int time = routes[0][1];
for(int i=1; i<routes.length; i++){
if(time < routes[i][0]){
answer++;
time = routes[i][1];
}
}
return answer;
}
}
์ฑ๊ณตโจ