저 커밋 하나에 내용이 너무 많아서 여전히 읽기 힘들다 ㅜㅜ 커밋 작게하는 습관을 들여야하는데 생각보다 쉽지않다
database 연결할 때 접속 계정과 패스워드가 필요한데, Github에 올릴 때는 그걸 빼고 올려야 하는데 같이 올려버렸다... 이번 경우에는 EC2 인스턴스를 중지 후 재시작 함으로써 hostname이 변경 되었기 때문에 크게 상관 없겠지만 이런 정보는 별도의 파일로 만들어서 .gitignore에 해당 파일을 추가하거나 환경 변수로 구성하는 방법으로 보완해야겠다는 생각이 들었다.
항상 Gradle을 쓸 때 IDE를 이용해서 빌드 및 실행을 했었는데 CMD로는 어떻게 할까?
그리고 IDE에서는 실행 할 때 알아서 빌드까지 진행해 주었는데 구분 동작은 어떻게 되는지 알아보자.
Gradle에 대한 세세한 정보는 여기서 다루지 않는다. 단순히 Gradle로 빌드하고 실행하는 것만 다룬다.
# Gradle Project Structure
settings.gradle: 프로젝트의 구성을 정의하는 설정 파일
build.gradle: 프로젝트 빌드 스크립트가 포함된 파일, Groovy나 Kotlin DSL을 사용
src/main: 메인 소스 코드 및 리소스가 있는 디렉토리
src/test: 테스트 소스 코드 및 리소스가 있는 디렉토리
build/: 필드 프로세스에서 생성되는 출력파일이 있는 디렉토리. 컴파일 된 class파일 빌드된 jar파일
# Gradle Wrapper
원래는 Gradle 빌드를 하려면 Gradle 설치를 따로 해야한다고 한다. 근데 옛날에 스프링부트로 개발할 때는 설치 없이도 잘 됐는데??
알고보니 Gradle Wrapper라는 것이 있다고 한다.
Gradle Wrapper는 미리 지정된 버전의 Gradle을 호출하도록 하는 스크립트다. Gradle 빌드를 사용하기 위해서는 알맞은 버전이 설치되어 있는데 매번 버전 업데이트를 하는 것이 비효율적이기 때문에 Gradle에서 프로젝트 생성시 내장 Gradle를 넣어주도록 했다.
Gradle 프로젝트 생성하면 기본적으로 생성되어 있는 gradlew이나 gradlew.bat 파일을 이용한다.
gradle-wrapper.properties: gradle wrapper 설정 파일. gradle 버전 및 다운로드 링크 기록
gradle-wrapper.jar: gradle wrapper 실행에 필요한 jar파일. gradle 래퍼 스크립트인 gradlew파일이 gradle을 다운로드하고 실행하는데 사용
gradlew/gradlew.bat: Unix / Windows 시스템에서의 Gradle Wrapper 스크립트. 프로젝트를 빌드하고 관리하는데 필요한 Gradle 실행 파일을 다운로드하고 실행
# Gradle 명령어를 이용하여 빌드
cmd로 빌드할 때는 gradlew / gardlew.bat 파일이 있는 root directory로 이동
gradle clean
IDE(IntelliJ)
CMD
gradle build
IDE(IntelliJ)
CMD
# .jar파일 실행
CMD에서 java -jar {projectName}.jar 파일을 실행하기 위해서는 build.gradle 파일에 다음과 같이 작성해야한다.
jar {
manifest {
attributes 'Main-Class': 'com.kh.Main'
}
from {
configurations.runtimeClasspath.collect {
it.isDirectory() ? it : zipTree(it)
}
}
duplicatesStrategy = DuplicatesStrategy.EXCLUDE
}
manifest 부분: JAR파일 내의 manifest 파일에 대한 속성을 지정, 버전, 주요 클래스, 클래스 경로 등의 정보가 포함됨
from 부분: Dependency가 필요할 때 추가함
DuplicateStrategey 부분: 중복 파일이 발견되면 하나만 JAR에 포함하고 나머지는 제외
원래는 프로젝트 개발진행하면서 블로그도 같이 쓰려고했는데, 개발 중간에서야 작성하게 됐다 ㅎㅎ;
# Gradle 빌드 툴 사용
학원에서 현재까지 진행된 프로젝트를 각자 발표한다고 했다. 발표하는 것은 문제가 아닌데, 개발 환경이 달라서 조금 문제가 됐다. 내 로컬 개발 IDE는 IntelliJ (Community)인데, 학원에서 진행하는 IDE는 Eclipse를 사용했다. 내 기억으로는 IntelliJ에서 생성한 프로젝트랑 Eclipse랑 호환이 안돼서 추가적인 세팅이 필요한 것으로 알고있다.
그래서 구글링하면서 세팅을 만져봤는데.. 내가 잘 못 한건지 계속 안되더라 ㅜㅜ 그래서 그냥 IntelliJ에서 작성한 코드들 다 복사해서 Eclipse에 새로 프로젝트 생성해서 붙여넣기 할까 생각했었는데, Git 설정도 문제가 될 것 같아서 그 방법은 관뒀다. Eclipse와 내 Remote Git을 연결해서 clone할까 생각도 했는데 그것도 내가 잘 못해서 그러는지 계속 안되더라 ㅜㅜ
그래서 "빌드 툴인 Gradle을 사용해서 jar파일로 만들고 발표할 로컬에서 Gradle을 이용해서 실행하면 되지 않을까?" 라는 생각으로 Gradle을 사용해보았다.
간단히 build.gradle파일과 settings.gradle파일 추가하면 IntelliJ가 자동으로 인식해서 Gradle Project Load할거냐고 물어본다. (역시 갓텔리제이... 똥클립스..)
CRUD까지 추가하고 든 생각이 Timer 자체는 View에서 처리하는 작업인데, 객체로 구현할 필요가 있을까? 라는 점이었다. 구글링을 해서 여느 플래너 어플리케이션을 봐도 서버쪽에서 Timer를 처리하지는 않았다.
그래서 Timer 객체를 Plan 객체로 수정하고 들어갈 필드들을 다시 생각해보았다. 예시 어플리케이션으로 선택한 뽀모도로 타이머를 보니 제목, 뽀모도로 수, 마감일, 프로젝트, 미리알림, 반복, 하위작업, 노트가 있었다.
여기서 하위 작업을 추가하는 건 뭔가 어려워 보이고.. 당장 쉽게 구현할 수 있는 것은 제목, 뽀모도로 수, 노트, 완료 여부 정도라고 생각하여 Timer → Plan 객체로 수정하고 hour, minute, second 필드를 삭제하고 timerCount와 clear라는 필드를 추가했다.
이 지점의 커밋들을 보니 학원에서 작업하다가 집에서 이어서 작성하려고 완전한 상태가 아닌데도 커밋하고 푸시한 커밋들이 있었다. 혼자 작업하다보니 이런 커밋들이 구별도 가고 크게 상관없겠지만, 협업하는 경우는 어떻게 해야하는지 궁금해졌다.
회사에서 작업하다가 완전하지 않은 상태인데 나머지는 집가서 마저 작업하려고 한다면(퇴근하고 집에가서 일을 더 한다는게 이상하게 느껴지긴 하는데;) 그 완전하지 않은 상태로 푸시하고 집에서 풀 이후에 작업하는게 맞는걸까? 아니면 다른 방법이 있을까?? 궁금해졌다.
이전에 자바로 웹 어플리케이션을 개발할 때는 바로 스프링 부트를 사용했는데, 지금 프로젝트 방향은 기본 프로젝트 → Gradle 프로젝트로 바꾸게 됐다. 그러면서 프로젝트 구조에 대한 이해도 늘었고 이전에는 막연하게 IntelliJ에서 Gradle 알아서 사용해준 느낌이었는데, Gradle 명령어나 CMD에서 사용하는 법도 공부 할 수 있어서 좋았다.
기능을 추가할 때 마다 테스트 코드를 작성했다. TDD로 구현한 것 까지는 아니지만, 테스트가 있어야 공격적인 리팩토링이 가능하기 때문에 작성했다.
근데 작성할 수록 View에 대한 테스트 코드를 작성하는것에 대해 회의감을 느꼈다. '이렇게 까지 View 테스트 코드를 작성해야 하나?" 라는 생각이 들었다. 그도 그럴 것이, View 부분은 비즈니스 로직 없이 단순히 콘솔에 보여주는 화면만 구성하는데 이것을 위한 테스트 코드까지 작성하는 것은 시간 낭비라는 생각이 계속 나를 지배했다. 그럼에도 불구하고 '테스트 코드 작성 연습하고 공부하자'라는 생각으로 작성했다.
Controller에서 getList()메서드로 List필드를 가져오고, 그 List에대한 메서드를 호출하는 것 보다. Controller에게 물어보는 메서드를 작성하는것이 더 올바른 캡슐화라고 생각해서 size(), isEmpty() 메서드를 작성했다. 근데 지금와서 보니 이 메서드들은 테스트 코드에서만 사용하는 메서드가 돼버려서 잘 못 작성한것 같다.
민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.
그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는 지나가던 행인들이 흘리고 간 금품들이 떨어져 있어, 그 길을 지나게 되면 일정한 양의 금품을 획득하게 된다. 한 번 지나간 길을 다시 방문하더라도 금품을 갈취당하거나 획득한다.
골목길의 연결 상태와, 각 골목길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이 주어졌을 때, 민승이가 최대한 유리한 경로를 따라 집에서 코레스코 콘도까지 가기 위해서는 어떻게 해야 하는지 출력하는 프로그램을 작성하시오.
보유 중인 금품의 양이 음수가 될 수 있다. 최대한 유리한 경로 또는 최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로이다.
입력
첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어진다. 이는 u번 교차점에서 v번 교차점으로 이동할 수 있는 골목길이 나있다는 의미이다. 즉, 주어지는 골목길들은 기본적으로 모두 일방통행로이다. w (0 ≤ |w| ≤ 1,000)는 이 길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이다. 음수는 갈취, 양수는 획득을 뜻한다.
골목길의 교차점 번호는 1이상 n이하의 정수이다. 민승이네 집은 1번 교차점에 있고, 이곳 코레스코 콘도는 n번 교차점에 있다.
출력
최적의 경로를 구할 수 있다면 민승이네 집부터 코레스코 콘도까지 가는 동안 거치게 되는 교차점들의 번호를 공백 하나를 사이에 두고 차례로 출력하면 된다. 그런데, 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다. 어떠한 경우에 그런 상황이 발생하는지 생각해 보자. 그러한 경우에는 -1을 출력하도록 한다.
최적의 경로가 여러 개 존재할 때는 아무거나 출력해도 된다.
2. 어떻게 풀까
최단 경로 알고리즘을 이용해서 해결 할 수 있다.
이 문제의 경우 최솟값을 구하는게 아니라 최댓값을 구하는 것이므로 음수 사이클을 찾는 것이 아니라 양수 사이클을 찾아야 한다.
사이클이 형성되는지 확인 해야하므로 벨만 포드 알고리즘을 이용하여 해결했다.
사이클이 존재하더라도 사이클이 목적지에 영향을 주지 않는다면 상관없다.
이 점을 간과해서 틀렸다. ㅜ
3. 코드 (Java)
package baekjoon.shortest_path.골목길_20220318;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer tokenizer;
private static int vertexCount;
private static int edgeCount;
private static int[][] edges;
private static int[] distanceFromSource;
private static int[] predecessor;
public static void main(String[] args) throws IOException {
tokenizer = new StringTokenizer(READER.readLine());
vertexCount = Integer.parseInt(tokenizer.nextToken());
edgeCount = Integer.parseInt(tokenizer.nextToken());
init();
bellmanFord();
if (distanceFromSource[vertexCount] == Integer.MIN_VALUE) {
System.out.println(-1);
return;
}
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
if (distanceFromSource[from] == Integer.MIN_VALUE) {
continue;
}
if (isCycle(from, to, weight) && isCycleOnPath(to)) {
System.out.println(-1);
return;
}
}
printShortestPath();
}
private static void init() throws IOException {
edges = new int[edgeCount][];
for (int i = 0; i < edgeCount; i++) {
tokenizer = new StringTokenizer(READER.readLine());
int from = Integer.parseInt(tokenizer.nextToken());
int to = Integer.parseInt(tokenizer.nextToken());
int weight = Integer.parseInt(tokenizer.nextToken());
edges[i] = new int[]{from, to, weight};
}
distanceFromSource = new int[vertexCount + 1];
predecessor = new int[vertexCount + 1];
for (int i = 1; i <= vertexCount; i++) {
distanceFromSource[i] = Integer.MIN_VALUE;
predecessor[i] = -1;
}
distanceFromSource[1] = 0;
}
private static void bellmanFord() {
for (int i = 0; i < vertexCount - 1; i++) {
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
if (distanceFromSource[from] == Integer.MIN_VALUE) {
continue;
}
if (distanceFromSource[to] < distanceFromSource[from] + weight) {
distanceFromSource[to] = distanceFromSource[from] + weight;
predecessor[to] = from;
}
}
}
}
private static boolean isCycle(int from, int to, int weight) {
return distanceFromSource[to] < distanceFromSource[from] + weight;
}
private static boolean isCycleOnPath(int targetVertex) {
boolean[] visit = new boolean[vertexCount + 1];
Queue<Integer> queue = new LinkedList<>();
queue.add(targetVertex);
while (!queue.isEmpty()) {
int currentVertex = queue.poll();
if (visit[currentVertex]) {
continue;
}
visit[currentVertex] = true;
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
if (from == currentVertex && !visit[to]) {
queue.add(to);
}
}
}
return visit[vertexCount];
}
private static void printShortestPath() {
StringBuilder sb = new StringBuilder();
int index = vertexCount;
sb.append(vertexCount);
while (predecessor[index] != -1) {
sb.insert(0, predecessor[index] + " ");
index = predecessor[index];
}
System.out.print(sb.toString());
}
}
bellmanFord() 메소드를 통해 출발 노드부터 목적지 노드까지의 최단 경로를 구했다.
목적지 노드까지의 경로가 없거나, 경로상에 양수 사이클이 존재할 경우 -1를 출력하도록 했다.
경로 상에 양수 사이클이 존재하는지 검사했다.
사이클이 존재하는 지 검증
벨만 포드 알고리즘 이후에도 distanceFromSource가 갱신이 되는지 확인했다.
사이클이 존재하고, 그 사이클이 경로상에 존재하는지 검증
사이클이 존재하는 노드에서 목적지 노드까지의 경로가 있는지 BFS를 이용하여 확인했다.
이 부분을 간과해서 틀렸다.
predecessor과 backtracking을 이용해서 최단 경로를 출력했다.
처음에는 StringBuilder에 append()로 하나씩 추가한 후 reverse()로 마무리를 했었는데 계속 실패가 나와서 insert()로 바꾸었다.
벨만 포드 알고리즘을 알고 있다면 쉽게 풀 수 있긴 한데, 음수(문제는 양수)사이클이 출발 노드에서 목적지 노드까지의 경로에 포함되는지 검사하는 로직이 반드시 필요하다는것을 간과했다.
인자로 주어지는 begin에서 시작해서 words에 주어진 단어들과 비교하면서 알파벳 하나만 바꿔서 그 단어가 될 수 있는지 확인한다.
words내에 방문한 단어들을 방문 표시하고, 모든 단어들을 방문하거나 target과 같은 단어를 방문하고 난 뒤에는 다시 방문 표시를 지워주어야 한다. 이게 무슨소리냐.. 말로 설명하니 어려우니까 그림으로 대체
visit가 다음과 같이 이루어진다고 가정하자. 방문한 word에 visit을 표시cog까지 도착했을 때 distance는 6이다. 이제 dog로 돌아갈 때 visit 표시를 한 cog를 다시 unvisit로 표시하지 않으면 → cog로 갈 수가 없다dog → log → cog로 갈 때보다, → cog로 가는 경로가 더 빠르다. 가장 빠른 길을 찾고 있기 때문에 갱신을 위해서 visit을 다시 unvisit로 바꿔주는 작업이 반드시 필요하다.
아니 그럼 visit을 굳이 둘 필요 없지않냐? 라고 생각할 수도 있는데.... 그러면 무한루프에 hot → dot → hot → dot ... 이런식으로 무한루프에 빠지니까 visit또한 반드시 필요하다.
hit에서 hot으로, hot에서 dog로 알파벳 하나를 바꿔서 만들 수 있는 단어라는 것을 우리는 직관적으로 알 수 있지만 이것을 코드로는 어떻게 구현할까?
단어와 단어 한 글자씩 비교하면서 다른 글자라면 count를 증가시키고, 그 count가 1이라면 알파벳 하나를 바꿔 만들 수 있는 단어가 된다고 판단하면 되겠다.
3. 코드 (Java)
package programmers.level3.단어변환_20220125;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int result = Integer.MAX_VALUE;
public Map<String, Boolean> visit;
public int solution(String begin, String target, String[] words) {
visit = new HashMap<>();
for (String word : words) {
visit.put(word, false);
}
dfs(begin, target, words, 0);
return result == Integer.MAX_VALUE ? 0 : result;
}
private void dfs(String currentWord, String targetWord, String[] words, int distance) {
if (currentWord.equals(targetWord)) {
result = Math.min(result, distance);
return;
}
for (String word : words) {
if (!visit.get(word) && getCharDifferenceCount(currentWord, word) == 1) {
visit.replace(word, true);
dfs(word, targetWord, words, distance + 1);
visit.replace(word, false);
}
}
}
private int getCharDifferenceCount(String a, String b) {
if (a.length() != b.length()) {
return -1;
}
int result = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
result++;
}
}
return result;
}
}
사실 틀렸었다.
애매하게 테스트3만 틀려서 더 멘붕옴;
이유를 생각해봤는데.... 알파벳을 한 번 바꿔서 일치하는지 체크하는 부분에서 실수를 저질렀다.
for (String word : words) {
String erase = currentWord.replaceAll("[" + word + "]", "");
if (!visit.get(word) && erase.length() == 1) {
visit.replace(word, true);
dfs(word, targetWord, words, distance + 1);
visit.replace(word, false);
}
}
내 생각은 이랬다. "hot"에서 정규표현식을 이용하여 "[hit]"에 매치되는 부분을 지우면 "o"만 남게되고 그러면 알파벳 차이가 1개이니까 조건에 부합하겠구나! 나 천잰듯?
천재가 아니라 멍청이었다.
만약 단어가 "hto"였다면 어떨까? "hto" → "hit"가 되려면 알파벳을 2개 바꿔야한다. (t → i, o → t) 근데 저 코드대로라면 erase는 역시 "o"만 남게되고 조건에 맞으니까 if문을 통과하게 된다.
아니.. 개 허술한 코드였는데.. 다 틀려야지 하나만 틀리니까 더 찾기 힘들잖아.....................
그래서 정공법으로 코드 수정한 결과가 getCharDifferenceCount() 메소드를 이용한 것이었다.
그나마 다행인 것은 구글링해서 뭐가 틀렸는지 확인한 것이 아니라 스스로 틀린 부분을 생각해낸 부분이라는점..?
세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진 열쇠들을 모두 찾는 것이다. 그리고 열쇠가 있는 곳들과 로봇이 출발하는 위치에 로봇이 복제할 수 있는 장치를 장착해 두었다.
N*N의 정사각형 미로와 M개의 흩어진 열쇠의 위치, 그리고 이 로봇의 시작 위치가 주어져 있을 때, 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 하는 프로그램을 작성하여라. 로봇은 상하좌우 네 방향으로 움직이며, 로봇이 열쇠가 있는 위치에 도달했을 때 열쇠를 찾은 것으로 한다. (복제된 로봇이어도 상관없다) 하나의 칸에 동시에 여러 개의 로봇이 위치할 수 있으며, 로봇이 한 번 지나간 자리라도 다른 로봇 또는 자기 자신이 다시 지나갈 수 있다. 복제에는 시간이 들지 않으며, 로봇이 움직이는 횟수의 합은 분열된 로봇 각각이 움직인 횟수의 총 합을 말한다. 복제된 로봇이 열쇠를 모두 찾은 후 같은 위치로 모일 필요는 없다.
입력
첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어진다. 1은 미로의 벽을 의미하고, 0은 지나다닐 수 있는 길, S는 로봇이 출발하는 위치, K는 열쇠의 위치가 주어진다. S는 1개, K는 M개가 주어진다. S와 K에서만 복제를 할 수 있음에 유의한다. 미로는 벽으로 둘러쌓여 있는 형태이다. 즉, 모든 테두리는 벽이다.
출력
첫째 줄에 모든 로봇이 움직인 횟수의 총 합을 출력한다. 모든 열쇠를 찾는 것이 불가능한 경우 횟수 대신 첫째 줄에 -1을 출력하면 된다.
2. 어떻게 풀까
각 Key와 Start 지점에서 로봇이 복제 될 수 있다는 것은 A지점에서 출발해서 B지점으로 가는 거리가 Start 지점에서 B지점으로 가는 거리가 더 가까울 수 있다는 뜻이다.
그렇다는 것은..? 각 지점을 정점이라고 가정하고 각 정점끼리 간선이 이어져 있고 이 간선들을 이용해서 최소 신장 트리를 만들라는 얘기가 될 것이다.
최소 신장 트리를 만들 수 없는 경우에는 -1을 출력하면 될 것이고, 최소 신장 트리가 만들어질 경우에는 그 가중치의 최솟값을 출력하면 되겠다.
그렇다면 정점은 입력으로 주어진 map의 좌표를 이용해서 저장하면 될 것이고... 각 정점간의 간선을 어떻게 만들것인가.. map에서 상하좌우로만 움직일 수 있고, 각 좌표간 거리는 1이라고 했으니까 BFS를 이용해서 각 정점간의 거리를 구하고 그것을 이용해서 간선을 구현하면 되겠다.
드가보자
3. 코드 (자바, 통과한 코드)
package baekjoon.mst.복제로봇_20220120;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
private static BufferedReader reader;
private static int[] pointY = {0, 0, 1, -1};
private static int[] pointX = {1, -1, 0, 0};
private static List<int[]> edges;
private static Vertex[] vertices;
private static int[] parents;
public static void main(String[] args) throws IOException {
reader = new BufferedReader(new InputStreamReader(System.in));
edges = new ArrayList<>();
String[] parts = reader.readLine().split(" ");
int mapSize = Integer.parseInt(parts[0]);
int vertexCount = Integer.parseInt(parts[1]) + 1;
vertices = new Vertex[vertexCount];
char[][] maps = buildMapsAndAddVertex(mapSize);
for (Vertex vertex : vertices) {
getEdgesUsingBFS(maps, vertex);
}
parents = makeSet();
int result = kruskal();
System.out.println(isMST() ? result : -1);
}
private static char[][] buildMapsAndAddVertex(int mapSize) throws IOException {
char[][] maps = new char[mapSize][mapSize];
int vertexIndex = 0;
for (int i = 0; i < mapSize; i++) {
String line = reader.readLine();
for (int j = 0; j < mapSize; j++) {
maps[i][j] = line.charAt(j);
if (isSourceOrKey(maps[i][j])) {
vertices[vertexIndex] = new Vertex(i, j, vertexIndex++);
}
}
}
return maps;
}
private static boolean isSourceOrKey(char c) {
return c == 'S' || c == 'K';
}
private static void getEdgesUsingBFS(char[][] maps, Vertex sourceVertex) {
Queue<int[]> queue = new LinkedList<>();
boolean[][] visit = new boolean[maps.length][maps.length];
visit[sourceVertex.y][sourceVertex.x] = true;
queue.add(new int[]{sourceVertex.y, sourceVertex.x, 0});
while (!queue.isEmpty()) {
int[] current = queue.poll();
int currentY = current[0];
int currentX = current[1];
int distanceFromSourceVertex = current[2];
for (int i = 0; i < 4; i++) {
int nextY = currentY + pointY[i];
int nextX = currentX + pointX[i];
if (!visit[nextY][nextX] && isValidPoint(maps, nextY, nextX)) {
visit[nextY][nextX] = true;
queue.add(new int[]{nextY, nextX, distanceFromSourceVertex + 1});
if (isSourceOrKey(maps[nextY][nextX])) {
for (Vertex destinationVertex : vertices) {
if (destinationVertex.y == nextY && destinationVertex.x == nextX) {
edges.add(new int[]{sourceVertex.id, destinationVertex.id, distanceFromSourceVertex + 1});
break;
}
}
}
}
}
}
}
private static boolean isValidPoint(char[][] maps, int nextY, int nextX) {
return (nextY >= 0 && nextY < maps.length)
&& (nextX >= 0 && nextX < maps.length)
&& (maps[nextY][nextX] != '1');
}
private static int kruskal() {
edges.sort(Comparator.comparingInt(x -> x[2]));
int result = 0;
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
if (find(parents, from) != find(parents, to)) {
union(parents, from, to);
result += weight;
}
}
return result;
}
private static int[] makeSet() {
int[] parents = new int[vertices.length];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
return parents;
}
private static int find(int[] parents, int x) {
if (parents[x] == x) {
return x;
}
return parents[x] = find(parents, parents[x]);
}
private static void union(int[] parents, int x, int y) {
x = find(parents, x);
y = find(parents, y);
if (x == y) {
return;
}
if (x < y) {
parents[y] = x;
} else {
parents[x] = y;
}
}
private static boolean isMST() {
for (int i = 0; i < vertices.length; i++) {
if (find(parents, i) != 0) {
return false;
}
}
return true;
}
private static class Vertex {
int y;
int x;
int id;
public Vertex(int y, int x, int id) {
this.y = y;
this.x = x;
this.id = id;
}
}
}
부가 설명 없이 코드만 보고 이해할 수 있는 코드...라고 믿고 부가 설명은 달지 않는다. (이해가 안되신다면 댓글 감사하겠습니다..)
근데 틀렸었다.
무수한 틀렸습니다...
틀린 이유를 코드를 보면서 골똘히 생각해봤는데 두 부분에서 버그가 있었다.
if (isSourceOrKey(maps[nextY][nextX])) {
for (Vertex destinationVertex : vertices) {
int destinationVertexId = -1;
if (destinationVertex.y == nextY && destinationVertex.x == nextX) {
destinationVertexId = destinationVertex.id;
break;
}
edges.add(
new int[]{sourceVertex.id, destinationVertex.id, distanceFromSourceVertex + 1});
}
}
BFS를 이용해서 각 Vertex간의 거리를 구하고 탐색하는 좌표가 Vertex에 해당하면 Edge를 만들어 저장하는 부분이다. 여기서 edges.add() 부분이 if (destinationVertex.y == nextY && destinationVertex.x == nextX) 안에 있어야 했다. 그렇지 않으면 index가 -1인 상태로 edges에 추가되어서 버그가 발생할 수 있다.
parents = makeSet();
int result = kruskal();
System.out.println(!edges.isEmpty() ? result : -1);
모든 Key에 닿을 수 있는 경우 가중치의 최솟값을 출력하고 그렇지 않은 경우 -1을 리턴하는 부분이다. 여기서 edges가 비어있는 경우를 모든 Key에 닿을 수 없는 경우로 생각하고 작성했는데, 생각해보니 edges 있어도 모든 Key에 닿을 수 있는 경우가 있을 수 있다. 그래서 find() 메소드로 모든 vertex들이 같은 집합인지 체크하는 isMST() 메소드를 작성하여 수정했다.
In this Kata, you will sort elements in an array by decreasing frequency of elements. If two elements have the same frequency, sort them by increasing value.
Solution.sortByFrequency(new int[]{2, 3, 5, 3, 7, 9, 5, 3, 7});
// Returns {3, 3, 3, 5, 5, 7, 7, 2, 9}
// We sort by highest frequency to lowest frequency.
// If two elements have same frequency, we sort by increasing value.
근데 counting순서로 정렬을 할 수 있나..?? sort() 메소드 쓰기전에 배열의 값들 counting을 해야할 것 같음
일단 Map에 (int, count)으로 데이터를 모으고 얘네를 count순으로 정렬하고 배열에 담는 식으로 하면 될 것 같음
드가자
코드
자바 코드
package codewars._6kyu.Simple_frequency_sort_20220117;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.stream.Collectors;
public class Solution {
public static int[] sortByFrequency(int[] array) {
Map<Integer, Integer> countingMap = getCountingMap(array);
List<Entry<Integer, Integer>> entryList = getSortedEntryList(countingMap);
List<Integer> result = getListSortedByFrequency(entryList);
return result.stream().mapToInt(x -> x).toArray();
}
private static Map<Integer, Integer> getCountingMap(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
for (int target : array) {
map.put(target, map.getOrDefault(target, 0) + 1);
}
return map;
}
private static List<Entry<Integer, Integer>> getSortedEntryList(
Map<Integer, Integer> countingMap) {
List<Entry<Integer, Integer>> entryList = new ArrayList<>(countingMap.entrySet());
entryList.sort((o1, o2) -> {
if (o1.getValue().equals(o2.getValue())) {
return o1.getKey() - o2.getKey();
}
return o2.getValue() - o1.getValue();
});
return entryList;
}
private static List<Integer> getListSortedByFrequency(List<Entry<Integer, Integer>> entryList) {
List<Integer> result = new ArrayList<>();
for (Entry<Integer, Integer> entry : entryList) {
int key = entry.getKey();
int value = entry.getValue();
for (int i = 0; i < value; i++) {
result.add(key);
}
}
return result;
}
public int[] sortByFrequencyBestPracticeSolution(int[] array) {
Map<Integer, Long> integerCountMap =
Arrays.stream(array)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
return Arrays
.stream(array)
.boxed()
.sorted(Comparator.<Integer, Long>comparing(integerCountMap::get)
.reversed()
.thenComparing(Comparator.naturalOrder()))
.mapToInt(Integer::intValue)
.toArray();
}
}
Map으로 (int, count) 데이터를 만들고, EntrySet list를 통해 value(count) 순으로 정렬 (count가 같다면 key 오름차순), 그리고 result list에 하나씩 담아 배열로 변환하여 리턴
근데 Best Practice를 보니까 Stream으로 신박하게 해결했다. 참고하면 좋을듯?
Collectors.groupingBy(), Function.identity(), Collectors.counting(), Comparator.<Integer, long>comparing() 메소드들은 처음 보는 메소드들인데 알아두면 Stream에서 요긴하게 쓸 수 있을듯
파이썬 코드
def solve(arr):
int_count_map = {}
for integer in arr:
int_count_map.setdefault(integer, 0)
int_count_map[integer] = int_count_map.get(integer) + 1
sorted_by_value_dict = sorted(int_count_map.items(), key=lambda x: x[1], reverse=True)
result = []
for items in sorted_by_value_dict:
key = items[0]
value = items[1]
for i in range(value):
result.append(key)
return result
def solve_best_practice(arr):
return sorted(sorted(arr), key=lambda n: arr.count(n), reverse=True)
파이썬으로도 풀어보자 해서 억지로 풀긴했다. 근데 BestPractice보니까 헛웃음이 나더라
