기억하고싶은것들

Given an integer array nums and an integer k, return the k most frequent elements.

You may return the answer in any order.

입력값으로 integer 배열과 integer k를 받는다. 가장 많이 등장하는 k개의 요소들을 반환하라.

어떠한 순서로 반환해도 상관없다.

가장 큰 값이나, 가장 작은 값을 찾는 문제와 비슷하게 가장 많이 등장하는 k개의 요소를 찾는 문제이므로

Heap을 이용하는 Priority Queue를 사용해서 찾으면 될 것이다.

Priority Queue를 구성하기 전에 비교하는 값이 등장하는 횟수이므로, 횟수를 비교 가능한 Map을 구성한 후에 Heap에 요소로 사용해보자.

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // 등장 횟수 Count
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> queue = 
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue()); // 내림차순
        queue.addAll(map.entrySet());

        int[] rst = new int[k];
        for (int i = 0; i < k; i++) {
            rst[i] = queue.poll().getKey();
        }
        return rst;
    }

먼저 Map을 이용하여 주어진 Nums의 요소들이 등장하는 횟수를 카운트 해준다.

후에, 해당 Map을 기준으로 Priority Queue를 구성해준다.

Queue의 비교대상은 Map의 Key가 아닌 Value이다. ( 등장 횟수 )

이제 Priority Queue가 등장 횟수 순으로 정렬이 되었으므로, 입력값이 k만큼 Queue에서 Poll 해주면 된다.

JPA의 연관관계 매핑의 다중성 중에 하나인 One To Many Mapping에 관해서 알아보고 예시를 보도록 하자.

연관관계 관련 어노테이션 중에 @OneToMany, @ManyToOne이 존재한다.

언뜻 보면 두 어노테이션은 같은 기능을 할 것 같지만 그렇지 않다. 

예시로 학생과 수업 Entity를 살펴보자.

학생은 여러 개의 수업을 수강할 수 있지만, 수업은 한 명의 학생만 수강할 수 있다. (과외라고 생각하자)

이 관계에서 주인은 foreign key를 가지고 있는 Courses가 된다.

@Getter
@NoArgsConstructor
@Entity
public class Courses {
	@Id
	@GeneratedValue(strategy = GenerationType.IDENTITY)
	private Long id;

	@Column
	private String name;

	@ManyToOne
	private Students student;

	@Builder
	public Courses(String name) {
		this.name = name;
	}

	public void update(String name, Students student) {
		this.name = name;
		this.student = student;
	}
}

@Getter
@NoArgsConstructor
@Entity
public class Students {

	@Id
	@GeneratedValue(strategy = GenerationType.IDENTITY)
	private Long id;

	@Column
	private String name;

	@Builder
	public Students(String name) {
		this.name = name;
		this.course = new HashSet<>();
	}

	public void update(String name, Courses course) {
		this.name = name;
		this.course.add(course);
	}
}

이러한 형태로 Entity를 작성하게 되면, Course에 Student_ID에 해당하는 foreign key가 생성된다.

( 대부분 연관관계의 주인이 foreign key를 가지고 있다고 생각하면 된다)

지금 현재 상태에서는 Students에서 자신이 수강하고 있는 Courses의 정보를 조회하기 어렵다.

이러한 점을 보완하기 위해 양방향 매핑으로 코드를 추가해보자.

양방향 관계

@Getter
@NoArgsConstructor
@Entity
public class Students {

	@Id
	@GeneratedValue(strategy = GenerationType.IDENTITY)
	private Long id;

	@Column
	private String name;

	@OneToMany(mappedBy = "student") //ADDED !
	private Set<Courses> course;

	@Builder
	public Students(String name) {
		this.name = name;
		this.course = new HashSet<>();
	}

	public void update(String name, Courses course) {
		this.name = name;
		this.course.add(course);
	}
}

@OneToMany 어노테이션을 가진 courseSet이 해당 매핑 관계의 주인이 아닌것을 표시하기 위해 mappedBy를 추가한다.

테스트 코드

위의 관계를 확인하는 테스트 코드를 보자.

    @Test
    public void 코스와학생매핑_OneToMany_코스가주인() {
    	
        Courses course = Courses.builder().name("METH").build();
        Courses courseEng = Courses.builder().name("ENG").build();
        Students student = Students.builder().name("Jon").build();
        
        studentsRepository.save(student);
        
        course.updateStudent(student); // Mapping Courses With Students
        courseEng.updateStudent(student); // Mapping Courses With Students
        
        coursesRepository.save(course);
        coursesRepository.save(courseEng);

        assertThat(course.getStudent().getId()).isNotNull();
    }

JPA의 연관관계 매핑의 다중성 중에 하나인 One To One Mapping에 관해서 알아보고 예시를 보도록 하자.

언뜻 생각하면 일대일 관계에는 방향성과 관계의 주인이 존재하지 않을 것 같지만,

OneToOne 매핑에서도 방향성과 연관관계의 주인이 존재한다.

예시로 학생과 수업 Entity를 살펴보자.

학생은 한 개의 수업만 수강할 수 있고, 수업은 한 명의 학생만 수강할 수 있다.

이 관계에서 주인을 학생으로 설정해 보자.

( 연관 관계의 주인은 foreign key를 가지고 있다 )

@Getter
@NoArgsConstructor
@Entity
public class Students {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    
    @Column
    private String name;
    
    @OneToOne
    private Courses course;

    @Builder
    public Students(String name) {
        this.name = name;
    }

    public void update(String name, Courses course) {
    	this.name = name;
    	this.course = course;
    }
}

@Getter
@NoArgsConstructor
@Entity
public class Courses {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    
    @Column
    private String name;

}

주인 테이블에 외래키를 가지고 있는 형태

일대일 관계에서 주인을 설정하는 방법으로는 @OneToOne 어노테이션을 붙여주는 것이다. ( Students )

양방향 관계

이 상태에서 양방향으로 방향을 지정하고 싶은 경우에는

양방향에 해당하는 Entity에 똑같이 @OneToOne 어노테이션을 붙이고

mappedBy라는 설정을 추가하면 된다. ( Courses )

@Getter
@NoArgsConstructor
@Entity
public class Courses {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    
    @Column
    private String name;
    
    @OneToOne(mappedBy = "course") // 양방향
    private Students student;
}

테스트 코드

위의 관계를 확인하는 테스트 코드를 보자.

    @Test
    public void 코스와학생매핑_oneToone() {
    	String studentName = "jun";
    	String courseName = "meth";
    	
    	Courses course = Courses.builder().name(courseName).build();
    	Students student = Students.builder().name(studentName).build();
    	
    	coursesRepository.save(course);
    	student.update(studentName, course);
    	studentsRepository.save(student);
    	
    	Students ss = studentsRepository.findById(student.getId()).get();
    	assertThat(ss.getCourse().getName().equals(courseName));
    	
    }

There are n rooms labeled from 0 to n - 1 and you start in the room 0.

All the rooms labeled from 1 to n are initially locked and you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it

and you can use them to open locked rooms and enter them.

You can visit the same room any number of times and the goal is to visit all the nrooms.

Given an array rooms where rooms [i] is the set of keys that you can obtain if you visited room i,

return true if you can visit all the rooms, or falseotherwise.

0부터 n-1까지의 이름 지어진 방이 있고, 0번째 방부터 시작된다.

1부터 n까지의 모든 방은 초반에 잠겨 있고, 열쇠가 없이는 들어갈 수 없다.

특정 방에 방문했을 때, 열쇠 꾸러미를 발견할 수 있고 그 열쇠 꾸러미를 이용해 잠긴 방을 방문할 수 있다.

방문했던 방에는 몇 번이고 중복해서 방문할 수 있고, 최종 목표는 모든 방에 방문하는 것이다.

방들의 배열이 주어지고, 해당 방에는 열쇠 꾸러미 정보를 가지고 있다.

만약 주어진 정보로 모든 방들을 방문할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환하라.

주어진 방들과 열쇠들의 정보는 tree 형태로 형상화할 수 있다.

주어진 트리를 방문하며, 방문한 방들의 정보를 저장하고 모든 트리의 노드를 순회했을 때 저장한 방문한 방들의 모든 정보가 주어진 방들의 길이와 같으면 모든 방을 방문한 것이다.

recursive 한 형태로 순환을 하고, Depth First Search를 이용하여 tree를 방문하여 보자.

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        List<Integer> visited = new ArrayList<>(); // 방문한 방들의 정보를 저장

        recursiveVisit(visited, rooms, 0); // 0번 방부터 시작

        if (visited.size() == rooms.size()) { // 주어진 방의 갯수와 방문한 방의 갯수 비교 
            return true;
        }
        return false;
    }

    private void recursiveVisit(List<Integer> visited, List<List<Integer>> rooms, int i) {

        visited.add(i);
        List<Integer> list = rooms.get(i);

        for (int idx : list) {
            if (!visited.contains(idx)) { // 이미 방문한 방은 다시 방문할 필요가 없다
                recursiveVisit(visited, rooms, idx);
            }
        }
    }