태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

그러하다...

ㅇ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;
    }
    
    

 

+ Recent posts