[240224] 알고리즘 리부트 15일차 - 백준 10814, 1302 자바

[Part1-Chapter05-Clip03]

- 백준 10814 나이 순 정렬

 

 

 

 

나이를 비교하는 것은 간편했으나 관건은 가입한 순서를 반영하는 것이기에 입력하는 순서인 인덱스를 객체의 속성으로 포함해 클래스로 만들었다. 이렇게 구현하니 하나의 객체의 속성들을 비교하기만 하면 되어서 간편하게 정렬을 구현할 수 있었다. 

 

package BaekJoon.sort;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class BJ10814 {
    public static class MemberInfo {
        int registerOrder;
        int age;
        String name;

        public MemberInfo(int x, int y, String str) {
            this.registerOrder = x;
            this.age = y;
            this.name = str;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        MemberInfo[] memberList = new MemberInfo[n];

        for (int i = 0; i < n; i++) {
            int thisAge = sc.nextInt();
            String thisName = sc.next();
            memberList[i] = new MemberInfo(i, thisAge, thisName);
        }


        Arrays.sort(memberList, (o1, o2) -> {
            if (o1.age == o2.age) { // 같으면 가입 순
                return o1.registerOrder - o2.registerOrder;
            } else { // 나이 오름차순
                return o1.age - o2.age;
            }
        });

        StringBuilder sb = new StringBuilder();

        for(int i =0; i<n; i++) {
            sb.append(memberList[i].age + " "+memberList[i].name+"\n");
        }

        System.out.println(sb);
    }
}

 

이 두번째 풀이는 5달 전의 내 코드인데 시간은 더 걸렸지만 코드 길이는 훨씬 간결한 것을 볼 수 있다.  난 아래와 같은 생각을 어떻게 했던 걸까. 일단 자료구조를 잘 활용한 것 같다. 배열을 선언하는데 각각의 원소를 문자열로 이루어진 어레이리스트로 선언했다. 그리고 배열의 인덱스를 나이로 활용해 최대 201의 길이를 가진 배열을 선언했고 나이가 같더라도 가입 순서대로 어레이리스트에 입력을 받게 처리했다. 그리고 반복문을 돌면서 각 배열의 원소인 어레이리스트 크기가 0이 아니라면 그 안에서 순서대로(즉, 가입 순서이다) 출력하면 된다. 아마 이중 반복문을 돌기 때문에 시간은 더 많이 소요되었던 것으로 보인다.  

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        ArrayList<String>[] ages = new ArrayList[201];

        for (int i = 0; i < ages.length; i++) {
            ages[i] = new ArrayList<String>();
        }

        int num = sc.nextInt();

        for (int i = 0; i < num; i++) {
            int age = sc.nextInt();
            String name = sc.next();
            ages[age].add(name);
        }

        for (int i = 0; i < ages.length; i++) {

            if (ages[i].size() != 0) {
                for (int j = 0; j < ages[i].size(); j++) {
                    System.out.println(i + " " + ages[i].get(j));
                }
            }
        }
    }
}

 

 

[Part1-Chapter05-Clip-05]

- 백준 1302 베스트셀러

 

 

 

 

해시 맵으로 판매권수와 책제목을 담았다. 나는 맵을 정렬해야 한다는 생각에 갇혔었는데 매번 최대 권수를 갱신하고 해당 최대권수를 가진 책들 중에서 사전 순으로 앞선 제목을 가진 책을 뽑아주면 되는 문제였다. 여기서 아직도 의문이 드는 것은 책제목의 초기값을 무엇으로 잡아야 하는지였다. 일단 z보다 더 뒤의 문자는 없어서 이렇게 작성했지만 만약 zz라는 책 제목이 있고 zzz라는 책 제목이 있으면 답은 zz가 나와야 하는데 존재하지도 않는 z가 답이 되어버리는 것이다. 여튼 아래 코드는 정답처리는 되었지만 결함이 있다고 볼 수 있다. 

 

package BaekJoon.sort;

import java.util.*;

public class BJ1302 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        HashMap<String, Integer> books = new HashMap<>();

        int maxSelling = 0;
        String maxBook = "z";

        while (n-- > 0) {
            String thisBook = sc.next();

            if (books.containsKey(thisBook)) { // 이미 있으면 권 수 더하고
                books.replace(thisBook, books.get(thisBook) + 1);
            } else { // 없으면 map에 넣기
                books.put(thisBook, 1);
            }
            // 최대 권수 구하고
            maxSelling = Math.max(maxSelling, books.get(thisBook));
        }
        //System.out.println(maxSelling);

        for (String title : books.keySet()) { // 맵 돌면서
            if (maxSelling == books.get(title)) { // 최대 권수 가진 책이면
                //maxBook = title; // 최대 권 수 책제목에 담고
                //System.out.println("이번 책은: "+ title);
                if (maxBook.compareTo(title) > 0) { // 기존의 책보다 사전 순으로 앞서면
                    //System.out.println("선택된 책은" + title);
                    maxBook = title; // 앞서는 책으로 담아주기
                }
            }
        }

        System.out.println(maxBook);
    }
}

 

사실 맵을 사용하기전에 이렇게 해시셋과 클래스를 이용한 배열을 사용해서 문제를 풀려고 했었다. 그런데 왜 이 코드에서는 정렬이 안되는지 이해가 안된다... 고민이 더 필요하다.

package BaekJoon.sort;

import java.util.*;

public class BJ1302 {
    public static class sellingData implements Comparable<sellingData> {
        String title;
        int num;

        public sellingData(String x, int y) {
            this.title = x;
            this.num = y;
        }

        @Override
        public int compareTo(sellingData o) {
            if (this.num == o.num) { // 판매량 같을 경우 사전 순
                return this.title.compareTo(o.title);
            } else { // 판매량 높은 순
                return o.num - this.num;
            }

        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 추가 반복문 없이 해당 책이 판매 기록에 존재하는지 보기 위함
        HashSet<String> exist = new HashSet<>();
        List<sellingData> arr = new ArrayList<>();


        for (int i = 0; i < n; i++) {
            String thisBook = sc.next();
            if (exist.contains(thisBook)) {
                for (int j = 0; j < arr.size(); j++) {
                    if (arr.get(j).title.equals(thisBook)) {
                        arr.get(j).num += 1;
                        break;
                    }
                }
            } else {
                exist.add(thisBook);
                arr.add(new sellingData(thisBook, 1));
            }
        }

        //System.out.println(arr.get(0).title);

        for (int i = 0; i < arr.size(); i++) {
            System.out.print(arr.get(i).title + " ");
            System.out.println(arr.get(i).num);
        }


    }
}