[Programmers] 키패드 누르기
·
Algorithm/Algorithm (문제풀이)
문제 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 해결 방법 (1) 키패드간 거리가 '직선'이 아니라 상하좌우로 제한됨 -> X,Y 좌표계 도입! (2) [1,4,7]-> L, [3,6,9] -> R 고정이고 [2,5,8,0] 만 거리 계산이 필요함. // 거리가 같다면 hand 값 따지기 (3) 입력값은 모두 '숫자'지만 초기 왼,오른손은 '*', '#' character -> 어차피 정수로 변..
[Programmers] 체육복
·
Algorithm/Algorithm (문제풀이)
1. 문제 2. 아이디어 0. 이 문제의 답은(전체 학생수 - 잃어버린 학생수)로 구하자. -> lost 배열의 원소를 제거하는 방식으로 풀어가자. 1. 도난당한애 == 여벌있는애 일 경우부터 삭제하고 시작하자. ∵ 어차피 여벌있으면서 도난당한애는 다른애한테 빌려주지 못한다. 2. 앞번호 먼저 검사 뒷번호 후검사를 하자. // Mistake 3. 주의사항 for(index in lostList.indices) { // 잃어버린 애, 가져온애가 같으면 양쪽 리스트에서 둘다 삭제 if (reserveList.remove(lostList[index])) lostList.removeAt(index) } for loop에서 index를 활용하여 '정순'으로 순환하면서 컬렉션의 원소를 제거하는 경우 원소가 제거된 ..
Union Find
·
Algorithm/Algorithm (이론)
Disjoint Set 서로 중복되지 않는 부분집합만으로 이뤄진 자료구조 = 서로소 집합 자료구조 Union-Find Disjoint Set을 표현할 때 사용하는 알고리즘. 2가지 자료구조로 구현할 수 있다. (Array, Tree) When to use? (1) Detect cycle in a undirected graph (2) Check relationship between sets (3) Kruskal Algrotihm * condition : The graph doesn't contain any self-loops Key For each edge, make subsets using both the vertices of the edge If both the vertices are in the sa..