Algorithm Study #5 (Sort And Its Application)

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