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.IOException;
import java.util.HashMap;
import java.util.Map;

public class Main {
public static void main(String args[]) throws IOException {
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.IOException;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
public static void main(String args[]) throws IOException {
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());
}

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.IOException;
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 {
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);
}
}