on
외벽 점검
외벽 점검
import java.util. * ;
class Solution {
static ArrayList < ArrayList < Integer > > orders = new ArrayList < ArrayList < Integer > > ();
static ArrayList < ArrayList < Integer > > weak_orders = new ArrayList < ArrayList < Integer > > ();
static void setOrder(ArrayList < Integer > all_dist, ArrayList < Integer > res) {
for ( int i = 0 ;i < all_dist.size();i + + ) {
res. add (all_dist.remove(i));
orders. add ( new ArrayList(res));
setOrder(all_dist, res);
all_dist. add (i, res.remove(res.size() - 1 ));
}
}
static boolean checkOrder( int n, int [] weak, int [] dist, ArrayList < Integer > order, ArrayList < Integer > weak_order) {
boolean [] visited = new boolean [n];
int cnt = 0 ;
int pos = 0 ;
for ( int i = 0 ; i < weak_order.size(); i + + ) {
if (pos > = order.size())
break ;
if (visited[weak_order.get(i)])
continue ;
// 방문 체크
for ( int j = weak_order.get(i); j < = weak_order.get(i) + order.get(pos); j + + ) {
if (j > = n)
visited[j - n] = true ;
else
visited[j] = true ;
}
pos + + ;
}
for ( int i = 0 ; i < weak. length ; i + + ) {
if (visited[weak[i]])
cnt + + ;
}
if (cnt = = weak. length )
return true ;
else
return false ;
}
public int solution( int n, int [] weak, int [] dist) {
int answer = 0 ;
ArrayList < Integer > all_dist = new ArrayList < Integer > ();
for ( int i = 0 ;i < dist. length ;i + + )
all_dist. add (dist[i]);
// 친구를 보내는 방법 초기화
setOrder(all_dist, new ArrayList < Integer > ());
// 친구 수 오름차순으로 정렬
Collections.sort(orders, new Comparator < ArrayList < Integer > > () {
@Override
public int compare(ArrayList < Integer > o1, ArrayList < Integer > o2) {
return o1.size() - o2.size();
}
});
// 방문 순서 초기화
for ( int i = 0 ;i < weak. length ;i + + ) {
ArrayList < Integer > weak_order = new ArrayList < Integer > ();
for ( int j = i;j < weak. length ;j + + ) {
weak_order. add (weak[j]);
}
for ( int j = 0 ;j < i;j + + ) {
weak_order. add (weak[j]);
}
weak_orders. add (weak_order);
}
for ( int i = 0 ; i < orders.size(); i + + ) {
for ( int j = 0 ; j < weak_orders.size(); j + + ) {
// 성공했을 경우 해당 인원을 반환
if (checkOrder(n, weak, dist, orders.get(i), weak_orders.get(j))) {
return orders.get(i).size();
}
}
}
return - 1 ;
}
}
from http://zzunsik.tistory.com/239 by ccl(A) rewrite - 2021-11-26 22:28:16