[JAVA] 백준 sorting - 실버모음2

 

이전글

https://fladi.tistory.com/329

[JAVA] 백준 sorting - 실버모음

 

 

1302 베스트설러(실버4)

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

1302번: 베스트셀러

 

• map으로 저장한 후 최댓값인 책 제목을 저장하고, 사전순으로 앞서는 애를 저장하면 될 것 같다
• 정렬은 안해도 될듯

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int bookNum = Integer.parseInt(br.readLine());
    Map<String, Integer> map = new HashMap<>();
    for (int b = 0; b<bookNum; b++) {
      String bookTitle = br.readLine();
      Integer tmp = map.get(bookTitle);
      if (tmp == null)
        map.put(bookTitle, 1);
      else
        map.put(bookTitle, tmp+1);
    }

    int maxSell = 0;
    String maxBookName = "";
    for (String key: map.keySet()) {
      if (map.get(key) > maxSell) {
        maxSell = map.get(key);
        maxBookName = key;
      } else if (map.get(key) == maxSell) {
        if (maxBookName.compareTo(key) > 0) //사전순으로 뒤에꺼가 더 앞섬, 뺀다고 생각하자
          maxBookName = key;
      }
    }

    System.out.println(maxBookName);
  }
}

• map에다 책제목을 key로 하여 책 개수를 value로 넣는다
• 가장 높은 판매량인 maxSell을 저장하고, 가장 높은 판매량인 책제목을 maxBookName에 저장한다
• map을 돌면서 가장 높은 판매량을 찾아 maxSell, maxBookName에 저장한다
  • 판매량이 maxSell과 같을 경우 사전순으로 앞선 애가 maxBookName에 들아가야한다
  • 이는 compareTo 메서드를 사용하여 구분한다

 

정렬안한 풀이

 

물론 TreeMap으로 정렬해서 풀 수도 있다

 

 

 

2108 통계학

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

2108번: 통계학

 

• 그냥 구하라는 대로 구하면 된다
• 산술평균은 전체 합에 개수를 나누고, 반올림 해준다
• 중앙값은 정렬해서 중간 인덱스를 뽑는다
• 최빈값은 해시에 빈도수를 저장해서 큰 값을 구한다
• 범위는 정렬한 리스트에서 최댓값과 최솟값을 뽑아 차이를 구한다 

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    int sum = 0;
    int[] arr = new int[cnt];
    Map<Integer, Integer> map = new HashMap<>();
    int range;

    for (int i =0; i<cnt; i++) {
      int num = Integer.parseInt(br.readLine());
      sum += num;
      if (map.get(num) == null)
        map.put(num, 1);
      else
        map.put(num, map.get(num) + 1);

      arr[i] = num;
    }

    Arrays.sort(arr);

    range = arr[cnt-1] - arr[0];
    int avg = (int)Math.round((double)sum/cnt);
    List<Integer> mode = new ArrayList<>();
    int medium = arr[cnt/2];
    for (int num: map.keySet()) {
      if (mode.size() == 0) {
        mode.add(num);
        continue;
      }

      if (map.get(mode.get(0)) < map.get(num)) {
        mode = new ArrayList<>();
        mode.add(num);
      } else if (map.get(mode.get(0)) == map.get(num)) {
        mode.add(num);
      }
    }

    Collections.sort(mode);

    System.out.println(avg);
    System.out.println(medium);
    System.out.println((mode.size() == 1)? mode.get(0): mode.get(1));
    System.out.println(range);
  }
}

 

 

 

18870 좌표 압축(실버2)

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

18870번: 좌표 압축

 

• 중복을 제거하여 내림차순으로 정렬하고, 정렬했을 때의 내 인덱스가 원래의 결과이다. 
• 차근차근 설명하면 다음과 같이 구현가능
  • 리스트에 일단 받는다(원본)
  • set에 담아 중복을 없애고, 정렬한다
  • 정렬된 값의  (값, 인덱스) 를 map에 저장한다
  • 원본에 있는 값들을 키값으로 map에서 조회하여 인덱스를 출력한다

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    List<Integer> arr = new ArrayList<>();
    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i=0; i<cnt; i++)
      arr.add(Integer.parseInt(st.nextToken()));

    TreeSet set = new TreeSet(arr);
    Map<Integer, Integer> map = new HashMap<>();

    int idx = 0;
    for (Object num: set) {
      int tmp = (Integer)num;
      map.put(tmp, idx);
      idx++;
    }

    StringBuffer sb = new StringBuffer();
    for (int a: arr) {
      sb.append(map.get(a));
      sb.append(" ");
    }

    System.out.println(sb);
  }
}

1. 원본 배열을 받는다
2. treeSet으로 중복을 없애고, 정렬한다
3. set에 정렬된 값을 키로하고, value를 인덱스로 하여 map에 저장한다
4. 원본 배열의 값을 key로 인덱스를 찾아 출력한다

 

잘 생각해보면 어렵진 않다. 하지만 set으로 만들고 인덱스를 저장하는 방법을 사람마다 다르게 풀었을 것 같다.

그래서 조금 찾아보았다!

 

 

★ 다른 풀이 https://st-lab.tistory.com/279

1. 원본 배열을 받는다
2. 원본 배열을 정렬한 정렬배열을 만든다
3. 슥 훑으면서 순위를 매긴 후 map에 저장한다
4. 원본 배열을 순회하면서 해당 값을 key로 value를 받아와 출력한다

 

내 방법은 정렬과 동시에 중복을 없앴는데, 이 분은 정렬 후 순위를 매기는 방식을 사용하셨다. 이렇게 풀 수도 있구나!

 

 

 

 

1931 회의실 배정(실버1)

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

1931번: 회의실 배정

 

• 생각이 바로 안나서 많이 어려웠다
• 브루트포스를 했다간 시간이 너무 많이 걸릴 것 같아서 그리디 느낌으로 풀어야할 것 같다
• 시간 간격을 정렬하여 그리디하게 풀기에는 반례가 있음
  • ex) 1-5, 3-6, 4-8 의 경우 3-6을 먼저 뽑으면 안됨
• 시작시간으로 오름차순 정렬하여 뽑는건 답이 안나옴
  • ex) 1-9, 2-3, 3-4
• 그럼 끝나는 시간 기준 오름차순 정렬하여 그리디하게 풀어야할 것 같다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    //시작시간, 끝 시간 저장
    int[][] arr = new int[cnt][2];

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

    Arrays.sort(arr, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        //마감시간 기준 정렬
        if (o1[1] == o2[1])
          return o1[0] - o2[0]; //시작시간 오름차순 정렬해야함
        else
          return o1[1] - o2[1]; //끝나는 시간 오름차순 정렬해야함
      }
    });

    int finishTime = 0;
    int result = 0;

    for (int i =0; i<arr.length; i++) {
      if (arr[i][0] >= finishTime) {
        finishTime = arr[i][1];

        result++;
      }
    }

    System.out.println(result);
  }
}

• 끝나는 시간을 오름차순으로 정렬한다
  • 만약 같을 경우 시작시간 기준 오름차순으로 정렬한다 (이유는 밑에 설명)
• 끝나는 시간을 기록하면서 배정 가능한만큼 모두 배정한다
• result 출력

 

★ 주의점: 시작 시간 오름차순 정렬이유

• 끝나는 시간이 같을 경우 상관없게 설정했더니 계속 틀렸다고 나왔다
• 시작시간을 오름차순 정렬해야 맞다고 나온다
• 이유에 대한 예시를 들어보면 다음과 같다
  • (1 5) (2 5) (3 5) (4 5) (5 5)
  • 이 경우 오름차순 정렬 시 (1 5) (5 5)가 결과에 들어가게 된다
  • 만약 내림차순 정렬 시 (5 5) 하나만 들어가게 되어 답이 틀리게 된다. 1 5도 들어갈 수 있기 때문이다

 

시작 시간을 고려하지 않은 업보..

 

 

 

1946 신입 사원(실버1)

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

1946번: 신입 사원

 

• 조금 헷갈려서 순차적으로 동작방식을 적어봤다.
• 서류 1등의 면접등수 minPaperRank 저장
• 서류 1등의 면접등수보다 면접등수가 높고, 서류가 1등 다음으로 높은 애를 찾아 minPaperRank에 저장
• while 면접 1등의 서류등수까지 ㄱㄱ

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());

    for (int t = 0; t<tcCnt; t++) {
      int cnt = Integer.parseInt(br.readLine());
      int[][] arr = new int[cnt][2];

      for (int i =0; i<cnt; i++) {
        String[] input = br.readLine().split(" ");
        arr[i][0] = Integer.parseInt(input[0]);
        arr[i][1] = Integer.parseInt(input[1]);
      }

      Arrays.sort(arr, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
          return o1[0] - o2[0];
        }
      }); //서류등수순으로 정렬

      int minInterviewRank = arr[0][1];

      int result = 1;
      for (int i =1; i<arr.length; i++) {
        if (arr[i][1] < minInterviewRank) {
          result++;
          minInterviewRank = arr[i][1];
        }

        if (arr[i][0] == 1)
          break;
      }

      System.out.println(result);
    }
  }
}

• 각 인원의 서류등수와 면접등수를 받고, 서류등수 순으로 오름차순 정렬한다
  • 중복은 없으니 고려하지 않음
• 서류등수 1등의 면접등수를 minInterviewRank에 저장한다
• 서류등수 2등부터 쭉 훑으면서 면접등수가 minInterviewRank보다 높은 애를 찾는다
  • 높은 애를 찾았으면 그 애의 면접등수를 minInterviewRank에 저장하고, result를 하나 늘린다
  • 이 과정을 인터뷰점수 1등의 서류등수가 될 때까지 반복한다

 

 

 

 

 

오늘의 교훈

• 사소한 것도 잘 생각하기
• 경계선 데이터 반례 미리 잘 생각하고 코드짜기