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