211019 화 Algorithms TIL

블록 이동하기

• 문제
• 코드
• 동빈북파이썬

동빈북 풀이

• 동빈북 풀이를 대략 보고 풀었다.
  • 동빈북 풀이에서 얻은 것은 이동 가능한 모든 위치를 List로 반환하는 함수를 만들어 그 리스트이 값들 중 visited 하지 않은 것이 있다면 그대로 queue에 넣는 것이다
  • 또 하나 얻은 것은 board를 변형하면 범위체크를 따로 하지 않아도 된다는 것이다.
• 최단거리 && 모든 간선 길이가 동일하면 BFS라는 것을 외우자.
  • 난 처음에 일단 DFS라는 생각이 들었다.
  • 근데 함수 호출 반복이 무서워서 노드를 따로 만들어 BFS로 풀어보자는 생각이 들었다.
  • 동빈북 풀이 보니까 이것은 전형적인 BFS 문제였다.
• 상하이동이 가능하다는 것은 동빈북 풀이를 보고 알았다.
• 동빈북은 파이썬에서 풀었기 때문에 튜플로 set을 넣어서 해결했다. 그래서 앞뒤라는 순서가 바뀌어도 {(1,1), (1,2)} 과 {(1,2), (1,1)}이 같은 것으로 처리 된다.
  • 그래서 안에 로직을 보면 다 - 앞, 뒤가 바뀐다고 해도 해결되는 로직으로 짜 두었다.

나 공부

• hashSet을 쓰면 hashcode와 equals 오버라이딩이 함께 되어야 한다. 둘 중 하나만 오버라이딩 하면 안된다.

국영수

• 동빈북 실버4
• 문제
• 자바-코드
• 파이썬-코드
• 0317 재풀이
  • 이에 대한 설명
• String.compareTo() 기억

류호석님 풀이 보고 배운 점

• 나는 정렬 기준을 아래와 같이 작성했는데

 @Override
        public int compareTo(Data other) {
            if (this.kook == other.kook) {
                if (this.young == other.young) {
                    if (this.soo == other.soo) {
                        return this.name.compareTo(other.name);
                    }
                    return other.soo - this.soo;
                }
                return this.young - other.young;
            }
            return other.kook - this.kook;
        }

• 류호석님 코드가 가독성이 더 좋아 보인다

  @Override
        public int compareTo(Elem other) {
            if (korean != other.korean) return other.korean - korean;
            if (english != other.english) return english - other.english;
            if (math != other.math) return other.math - math;
            return name.compareTo(other.name);
        }

동빈북 풀이를 보니 역순 출력은 - 를 안붙이고 앞 뒤의 순서를 바꿔줘도 된다.

• 내 풀이

package ch14_sort_questions;

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

//https://www.acmicpc.net/problem/10825
public class Q23_KookYoungSoo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numOfStudents = sc.nextInt();
        Score[] scores = new Score[numOfStudents];
        for (int i = 0; i < numOfStudents; i++) {
            scores[i] = new Score(sc.next(), sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(scores, new Comparator<Score>() {
            @Override
            public int compare(Score score1, Score score2) {
                if (score1.korean == score2.korean) {
                    if (score1.english == score2.english) {
                        if (score1.math == score2.math) {
                            return score1.student.compareTo(score2.student);
                        }
                        return -(score1.math - score2.math);
                    }
                    return score1.english - score2.english;
                }
                return -(score1.korean - score2.korean);
            }
        });

        for (Score score : scores) {
            System.out.println(score.student);
        }
    }

    static class Score {
        String student;
        int korean;
        int english;
        int math;

        public Score(String student, int korean, int english, int math) {
            this.student = student;
            this.korean = korean;
            this.english = english;
            this.math = math;
        }
    }
}

• 동빈북

class Student implements Comparable<Student> {

    private String name;
    private int kor;
    private int eng;
    private int m;

    public Student(String name, int kor, int eng, int m) {
        this.name = name;
        this.kor = kor;
        this.eng = eng;
        this.m = m;
    }

    /*
    [ 정렬 기준 ]
    1) 두 번째 원소를 기준으로 내림차순 정렬
    2) 두 번째 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
    3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
    4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
    */

    public String getName() {
        return this.name;
    }

    // 정렬 기준은 '점수가 낮은 순서'
    @Override
    public int compareTo(Student other) {
        if (this.kor == other.kor && this.eng == other.eng && this.m == other.m) {
            return this.name.compareTo(other.name);
        }
        if (this.kor == other.kor && this.eng == other.eng) {
            return Integer.compare(other.m, this.m);
        }
        if (this.kor == other.kor) {
            return Integer.compare(this.eng, other.eng);
        }
        return Integer.compare(other.kor, this.kor);
    }
}

public class Main {

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

        ArrayList<Student> students = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String name = sc.next();
            int kor = sc.nextInt();
            int eng = sc.nextInt();
            int m = sc.nextInt();
            students.add(new Student(name, kor, eng, m));
        }

        Collections.sort(students);

        // 정렬된 학생 정보에서 이름만 출력
        for (int i = 0; i < n; i++) {
            System.out.println(students.get(i).getName());
        }
    }
}

안테나

• 문제
• 자바-코드
• 파이썬-코드

동빈북 풀이

• 이 문제의 핵심은 정확히 중간값에 해당하는 위치의 집에 안테나를 설치했을 때 그 답이 최소가 되다는 것이다.
• 그리고 작은 값을 출력한다고 해서 n-1 을 2로 나눈 값이다
• 만약 5개라고 하면 인덱스는 0, 1, 2, 3, 4 일텐데 여기서는 인덱스 2의 값을 뽑아야 한다. 그래서 ( 5 - 1 ) // 2 인 값을 하는 것
• 4개라고 한다면 1, 2이라는 인덱스 (4 -1) // 2

실패율

• 문제
• 코드-자바
• 코드-파이썬 : 동빈북에서 아주 조금 변형
• 동빈북코드
• 지난 번 풀었을 때와 달리 동빈북 스타일로 푼 것 같다.

카드 정렬하기

• 백준, 골드4
• 코드-자바
• 코드-파이썬 == 동빈북
• 문제
• 동빈북 파이썬
• 저번에 그래도 파이썬으로 푼 것이 기억이 나나봄
• 동빈북 풀이로 풀었는데
• 애초에 더미가 1개일 때 0으로 풀어야 하는데 그 카드 수를 해서 좀 고생함