Algorithm Study #5 (Sort And Its Application)

jakeseo_me·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
        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라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글