Algorithm Study #5 (Sort And Its Application)

Jake Seo·2019년 3월 9일
0

java algorithm study

목록 보기
14/18

Card

  • boj/11652
  • Junkyu has cards which contain a number between -2^62 and 2^62
  • Which kind of card does Junkyu have the most?
  • It can be solved after sorted
  • After sorting cards, it can be solved in O(N) time complexity
  • solution using map
    	```java
    	    import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      import java.util.HashMap;
      import java.util.Map;
    
      public class Main {
          public static void main(String args[]) throws IOException {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              int n = Integer.parseInt(br.readLine());
              HashMap<String, Integer> map = new HashMap();
    
              for(int i=0; i<n; i++){
                  String key = br.readLine();
                  if(map.get(key) == null) map.put(key, 0);
                  map.put(key, map.get(key) + 1);
              }
    
              int maxCnt = 0;
              String maxNum = "";
    
              for(Map.Entry<String, Integer> entry: map.entrySet()){
                  if(entry.getValue() > maxCnt){
                      maxCnt = entry.getValue();
                      maxNum = entry.getKey();
                  }
                  else if(entry.getValue() == maxCnt){
                      maxNum = Long.toString(Math.min(Long.parseLong(entry.getKey()), Long.parseLong(maxNum)));
                  }
              }
    
              System.out.print(maxNum);
          }
      }
    	```

K-th Element

  • boj.kr/11004
	import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.PriorityQueue;
    import java.util.StringTokenizer;
    
    public class Main {
        public static void main(String args[]) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st0 = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st0.nextToken());
            int k = Integer.parseInt(st0.nextToken());
            int[] nArr = new int[n];
    
            StringTokenizer st = new StringTokenizer(br.readLine());
            PriorityQueue pq = new PriorityQueue();
    
            for(int i=0; i<n; i++) {
                //nArr[i] = Integer.parseInt(st.nextToken());
                pq.add(Integer.parseInt(st.nextToken()));
            }
    
            for(int i=0; i<k-1; i++){
                pq.poll();
            }
    
            System.out.print(pq.poll());
        }
    }

Bubble sort

  • boj.kr/1377
  • it can't be solved if you just implement bubble sort.
    - thinking about time complexity
    • to know how many loops will require to sort things
    • if we know the result of this sort, we can know the answer
      • how many times it is changed.
        • we should focus on thing which must go to front place.
  • solution
	import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    public class Main {
        public static class Pair implements Comparable<Pair>{
            int val;
            int index;
    
            Pair(int val, int index){
                this.val = val;
                this.index = index;
            }
    
    
            @Override
            public int compareTo(Pair o) {
                return Integer.compare(this.val, o.val);
            }
        }
        public static void main(String args[]) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            Pair[] pArr = new Pair[n];
    
            for(int i=0; i<n; i++)
                pArr[i] = new Pair(Integer.parseInt(br.readLine()), i);
    
            Arrays.sort(pArr);
    
            int max = 0;
    
            for(int i=0; i<n; i++)
                max = Math.max(max, pArr[i].index - i);
    
            System.out.print(max + 1);
        }
    }
profile
풀스택 웹개발자로 일하고 있는 Jake Seo입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. 프론트엔드: Javascript, React 백엔드: Spring Framework에 관심이 있습니다.

0개의 댓글