반응형
그러하다...
ㅇSherlock and Array
int size = arr.size();
int leftSum = 0;
int rightSum = 0;
int leftIndex = 0;
int rightIndex = size - 1;
String answer = "";
for(int i = 0 ; i < size ; i++) {
leftSum = leftSum + arr.get(leftIndex);
rightSum = rightSum + arr.get(rightIndex);
//System.out.println(leftSum + " " + rightSum);
if(leftIndex == rightIndex) {
if (leftSum == rightSum) {
answer = "YES";
} else {
answer = "NO";
}
break;
}
if(leftSum > rightSum) {
rightIndex--;
leftSum = leftSum - arr.get(leftIndex);
} else {
leftIndex++;
rightSum = rightSum - arr.get(rightIndex);
}
}
====================================================================================
ㅇMarc's Cakewalk
static long marcsCakewalk(int[] calorie) {
long sum = 0;
int powDepth = 0;
Integer[] conv = Arrays.stream(calorie).boxed().toArray(Integer[]::new);
Arrays.sort(conv, Collections.reverseOrder());
calorie = Arrays.stream(conv).mapToInt(Integer::intValue).toArray();
for(int i = 0 ; i < calorie.length ; i++) {
sum = sum + (long)((Math.pow(2, powDepth) * calorie[i]));
powDepth++;
}
return sum;
}
====================================================================================
ㅇJim and the Orders
static class Customer implements Comparable<Customer> {
int custNum;
int totTime;
Customer(int c, int t){
this.custNum = c + 1;
this.totTime = t;
}
public int compareTo(Customer c1) {
if(c1.totTime == this.totTime) {
return custNum - c1.custNum;
} else {
return totTime - c1.totTime;
}
}
}
// Complete the jimOrders function below.
static int[] jimOrders(int[][] orders) {
PriorityQueue<Customer> pq = new PriorityQueue<>();
for(int i = 0 ; i < orders.length ; i++) {
Customer cust = new Customer(i, orders[i][0] + orders[i][1]);
pq.offer(cust);
}
int result[] = new int[orders.length];
int idx = 0;
while(pq.isEmpty() == false) {
Customer cust = pq.poll();
result[idx++] = cust.custNum;
}
return result;
}
====================================================================================
ㅇJourney to the Moon Case 1 -- 11번 문제 시간 초과함.
static boolean[] visited;
static List<List<Integer>> groups;
static int memberCnt;
// Complete the journeyToMoon function below.
static int journeyToMoon(int n, int[][] astronaut) {
groups = new ArrayList<>();
for(int i = 0 ; i < n ; i++) {
groups.add(new ArrayList<>());
}
for(int i = 0 ; i < astronaut.length ; i++) {
int s = astronaut[i][0];
int e = astronaut[i][1];
groups.get(s).add(e);
groups.get(e).add(s);
}
visited = new boolean[n];
HashMap<Integer, Integer> gm = new HashMap<>();
int groupCnt = 0;
for(int i = 0 ; i < n ; i++) {
memberCnt = 0;
if(visited[i] == false) {
groupCnt++;
dfs(i);
//System.out.println("groupCnt : " + groupCnt + ", memberCnt : " + memberCnt);
gm.put(groupCnt, memberCnt);
}
}
//System.out.println(gm);
int[] ff = new int[gm.size()];
int idx = 0;
for(Map.Entry<Integer,Integer> entry : gm.entrySet()) {
//System.out.println(entry.getKey() + " " + entry.getValue());
ff[idx] = entry.getValue();
idx++;
}
int sum = 0;
for(int i = 0 ; i < ff.length - 1 ; i++) {
for(int x = i + 1 ; x < ff.length ; x++) {
sum = sum + (ff[i] * ff[x]);
}
}
return sum;
}
static void dfs(int m) {
//System.out.println(">> m : " + m);
memberCnt++;
visited[m] = true;
List<Integer> cur = groups.get(m);
for(int i = 0 ; i < cur.size() ; i++) {
if (visited[cur.get(i)] == false) {
dfs(cur.get(i));
}
}
}
ㅇJourney to the Moon Case 2 -- 11번 문제 정답 틀림.... -_-..
static int journeyToMoon(int n, int[][] astronaut) {
int[] astr = new int[n];
Arrays.fill(astr, -1);
// 부모-자식관계 만들기(연결된건 그룹으로 묶는다)
for(int i = 0 ; i < astronaut.length ; i++) {
int pa = astronaut[i][0];
int ch = astronaut[i][1];
if (astr[pa] == -1) {
astr[pa] = pa;
}
if (astr[ch] == -1) {
astr[ch] = ch;
}
int updP = astr[ch];
astr[ch] = astr[pa];
for(int x = 0 ; x < n ; x++) {
if(astr[x] == updP) {
astr[x] = astr[pa];
}
}
}
System.out.println(Arrays.toString(astr));
HashMap<Integer, Integer> gm = new HashMap<>();
for(int i = 0 ; i < astr.length ; i++){
if(astr[i] == -1) {
gm.put(i, 1);
} else {
int cnt = gm.getOrDefault(astr[i], 0);
cnt++;
gm.put(astr[i], cnt);
}
}
System.out.println(gm);
int[] ff = new int[gm.size()];
int idx = 0;
int noLink = 0;
for(Map.Entry<Integer,Integer> entry : gm.entrySet()) {
//System.out.println(entry.getKey() + " " + entry.getValue());
if(entry.getValue() == -1) {
continue;
}
ff[idx] = entry.getValue();
idx++;
}
int sum = 0;
for(int i = 0 ; i < ff.length - 1 ; i++) {
for(int x = i + 1 ; x < ff.length ; x++) {
sum = sum + (ff[i] * ff[x]);
}
}
return sum;
}
====================================================================================
ㅇ Special Subtree
// 첨에 너무 어렵게 생각했다. 그냥 최소 경로로 방문만 하면 된다.
// 다익스트라가 최단경로이기 때문에 이미 노드간 최소 거리로 이동을 한다.
// 그리고 방문 한 곳은 visit 처리 해 주고, 최단 경로값 더하기만 하면 됨
static class Node implements Comparable<Node> {
int idx;
int dist;
Node(int i, int d){
this.idx = i;
this.dist = d;
}
public int compareTo(Node o) {
return this.dist - o.dist;
}
}
static int prims(int n, int[][] edges, int start) {
boolean[] visited = new boolean[n + 1];
List<List<Node>> paths = new ArrayList<>();
for(int i = 0 ; i <= n ; i++) {
paths.add(new ArrayList<Node>());
}
Node nd;
for(int i = 0 ; i < edges.length ; i++) {
int st = edges[i][0];
int ed = edges[i][1];
int dt = edges[i][2];
nd = new Node(ed, dt);
paths.get(st).add(nd);
nd = new Node(st, dt);
paths.get(ed).add(nd);
}
Arrays.fill(visited, false);
PriorityQueue<Node> pq = new PriorityQueue<Node>();
pq.offer(new Node(start, 0));
int totVisitCost = 0;
while(pq.isEmpty() == false) {
Node curNd = pq.poll();
int curIdx = curNd.idx;
int curDist = curNd.dist;
if (visited[curIdx] == true) continue;
for(int i = 0 ; i < paths.get(curIdx).size() ; i++) {
Node nextNd = paths.get(curIdx).get(i);
int nextIdx = nextNd.idx;
int nextDist = nextNd.dist;
if(visited[nextNd.idx] == false) {
pq.offer(nextNd);
}
}
totVisitCost = totVisitCost + curDist;
visited[curIdx] = true;
}
return totVisitCost;
}
====================================================================================
ㅇLargest Permutation
static int[] largestPermutation(int k, int[] arr) {
//int[] arr = {6,7,5,4,1,2,3,9,10,8};
//k = 4;
// 좌측은 사이즈 크기의 숫자가 있어야 함.
int targetNum = arr.length;
int chgCnt = 0;
HashMap<Integer, Integer> hmap = new HashMap<>();
for(int i = 0 ; i < arr.length ; i ++) {
hmap.put(arr[i], i);
}
for(int i = 0 ; i < arr.length ; i ++) {
if(arr[i] != targetNum){
//System.out.println(i + " " + targetNum);
arr[hmap.get(targetNum)] = arr[i];
int prevPos = hmap.get(targetNum);
// hmap.put(targetNum, i); // 이미 지나간거는 굳이 바꿀 필요는 없다.
hmap.put(arr[i], prevPos);
arr[i] = targetNum;
chgCnt++;
//System.out.println(Arrays.toString(arr));
//System.out.println(hmap);
if(k == chgCnt) break;
}
targetNum--;
}
return arr;
}
====================================================================================
ㅇIce Cream Parlor
4
1 4 5 3 2
-> 1 4
static int[] icecreamParlor(int m, int[] arr) {
System.out.println("-----------");
int totCost = 0;
int result[] = new int[2];
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i = 0 ; i < arr.length ; i++) {
int cost = arr[i];
if(cost < m) {
// money = 4, cost = 2 인 경우 null인 경우 넣는걸 먼저하면, 바로 끝나 버린다
if(hm.get(m - cost) != null) {
result[0] = hm.get(m - cost) + 1;
result[1] = i + 1;
break;
}
if(hm.get(cost) == null) {
hm.put(cost, i);
}
}
}
return result;
}
// 2중 for문은 안 쓰는게 좋다. 성능 저하. O(n^2)
static int[] icecreamParlor(int m, int[] arr) {
int totCost = 0;
int result[] = new int[2];
for(int i = 0 ; i < arr.length - 1; i++) {
int costA = arr[i];
for(int x = i + 1 ; x < arr.length ; x++) {
int costB = arr[x];
if(m == costA + costB) {
result[0] = i + 1;
result[1] = x + 1;
}
}
}
return result;
}
반응형
댓글