[Java] 백준 sorting - 브론즈모음

 

알고리즘 공부 중 내가 정렬에 익숙하지 않다는 걸 알아냈다!

comparator도 기억이 잘 안났고, 이름은 오름차순 정렬하면서 성적은 내림차순 정렬하는 등 두 번 이상 정렬하는 것도 헷갈렸다. 그래서 이번에 소팅관련 문제를 싹 풀고 익숙해져보려고 한다!

 

2757 세수정렬(브론즈4)

https://www.acmicpc.net/problem/2752

2752번: 세수정렬

• 세 개의 수를 정렬하는 방법을 찾는다
• 그냥 sort쓰면 될듯

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=  new StringTokenizer(br.readLine());
int[] arr = new int[3];

for (int i =0; i<3; i++)
  arr[i] = Integer.parseInt(st.nextToken());

Arrays.sort(arr);

StringBuffer sb = new StringBuffer();
for (int i =0; i<3; i++)
  sb.append(arr[i] + " ");

System.out.println(sb.toString().strip());

 

 

28114 팀명 정하기(브3)

https://www.acmicpc.net/problem/28114

28114번: 팀명 정하기

• 중복도 전혀 없고, 그냥 리스트 정렬만 잘 하면 되는 문제
• 학번기준 정렬, 이름+백준 문제 푼 개수 기준 정렬만 잘하면 된다
• 정렬에 익숙하지 않으면 브론즈인데도 어렵다 ㅠ

 

1. 학번을 받아 학번리스트에 저장
2. 이름과 백준문제 개수를 받아 map에 저장
3. 학번리스트를 오름차순 정렬
4. map을 value기준 내림차순 정렬
5. 학번리스트에 %100한 나머지를 이어붙이고, map의 key쌍을 받아 앞자리만 이어붙임

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<Integer> numList = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();

//입력받기
for (int cnt = 0; cnt<3; cnt++) {
  StringTokenizer st = new StringTokenizer(br.readLine());
  int baekCnt = Integer.parseInt(st.nextToken());
  int schoolNum = Integer.parseInt(st.nextToken());
  map.put(st.nextToken(), baekCnt);
  numList.add(schoolNum);
}

//학번정렬
Collections.sort(numList);
StringBuffer sb = new StringBuffer();

//이름+백준문제 수 정렬
TreeMap<String, Integer> treeMap = new TreeMap<>(Comparator.reverseOrder());
treeMap.putAll(map);


for (Integer num: numList) 
  sb.append(num%100);

sb.append("\n");

for (String key: treeMap.keySet())
  sb.append(key.charAt(0));

System.out.println(sb);

• treeMap 사용법이 아직 안익숙하다
• 내림차순 정렬을 위해 comparator를 구현했었지만 저렇게 reverseOrder를 사용하는 게 더 편한 것 같다

 

 

28417 스케이트보드(브론즈3)

https://www.acmicpc.net/problem/28417

28417번: 스케이트보드

 

• 런의 최고점수는 그냥 비교를 통해 구하면 될 것 같고
• 트릭은 max값은 정렬할 필요까진 없고 max값과 그 다음 큰 값을 구하면 될듯
• 점수들을 다 저장해서 최댓값 반환
• 정렬보단 최댓값 잘 찾기 문제 느낌이다

 

풀이

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int manCnt = Integer.parseInt(br.readLine());
int maxSum = -1;

for (int i =0; i<manCnt; i++) {
  StringTokenizer st = new StringTokenizer(br.readLine());
  int maxRun = Integer.parseInt(st.nextToken());
  int nextRun = Integer.parseInt(st.nextToken());
  maxRun = (nextRun>maxRun)?nextRun:maxRun;

  List<Integer> trik = new ArrayList<>();
  int maxTrik = -1;
  for (int j =0; j<5; j++) {
    int trikScore = Integer.parseInt(st.nextToken());
    if (trikScore > maxTrik) {
      trik.add(maxTrik);
      maxTrik = trikScore;
    } else {
      trik.add(trikScore);
    }
  }

  int sum = maxRun + maxTrik + Collections.max(trik);
  if (sum > maxSum)
    maxSum = sum;
}

System.out.println(maxSum);

• 최댓값 열심히 구해서 풀었다 ㅋㅋ

 

2750 수 정렬하기(브론즈2)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

• 오름차순 정렬이다
• 연습을 위해 Comparator를 사용할 예정

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numCnt = Integer.parseInt(br.readLine());
Integer[] nums = new Integer[numCnt];

for (int i = 0; i<numCnt; i++)
  nums[i] = Integer.parseInt(br.readLine());

Arrays.sort(nums, new Comparator<Integer>() {
  @Override
  public int compare(Integer o1, Integer o2) {
    return o1 - o2; //오름차순 정렬
  }
});

StringBuffer sb = new StringBuffer();
for (int a: nums) {
  sb.append(a);
  sb.append("\n");
}

System.out.print(sb);

• 일단 다 받고 Integer[] 배열에 저장함
• Arrays.sort함수를 호출
  • 디폴트 오름차순 정렬이지만 그냥 Compartator를 구현해봤음
  • 중복이 없으니 그냥 빼기만 해도 충분
  • 디폴트와 똑같이 동작함

 

 

2693 N번째 큰 수(브론즈1)

https://www.acmicpc.net/problem/2693

2693번: N번째 큰 수

 

• 3번째 큰 값을 구하는 문제다 ㅋㅋㅋ 
• 정렬해도 되고 3번 슥 훑으면서 최댓값 3개를 뽑아도 될 듯
• 귀찮으니 내림차순 정렬해서 풀자

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tcCnt = Integer.parseInt(br.readLine());
StringBuffer sb = new StringBuffer();

for (int t=0; t<tcCnt; t++) {
  StringTokenizer st = new StringTokenizer(br.readLine());
  Integer[] arr = new Integer[10];
  for (int i =0; i<10; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
  }

  Arrays.sort(arr, Comparator.reverseOrder());

  sb.append(arr[2] + "\n");
}

System.out.print(sb);

 

 

 

이제 실버로 넘어가려고 한다!