계좌 이체 최소 거래 횟수
목표 : 서로 송금한 계좌 이체 내역들을 최소의 거래 횟수로 줄이기
해결방법 : DFS + 백트래킹로 해결했다.
- 각 사람의 순 입출금 잔액을 계산해서 map에 저장
- 잔액이 0이 아닌 사람들만 추려 List로 구성
- DFS + 백트래킹을 이용하여 상쇄시킬 수 있는 사람끼리 거래를 시도하며 최소 거래 횟수를 계산
코드
import java.util.*;
class Solution {
public int solution(int[][] trans) {
Map<Integer, Integer> map = new HashMap<>();
// 1. 입출금 잔액 계산
for(int[] tran : trans) {
int from = tran[0];
int to = tran[1];
int amount = tran[2];
map.put(from, map.getOrDefault(from, 0) - amount);
map.put(to, map.getOrDefault(to, 0) + amount);
}
// 2. 잔액 ≠ 0인 사용자만 리스트로 추림
List<Integer> list = new ArrayList<>();
for(int key : map.keySet()) {
if (map.get(key) != 0) list.add(map.get(key));
}
// 3. DFS로 최소 거래 횟수 계산
return dfs(0, list);
}
int dfs(int idx, List<Integer> list) {
while (idx < list.size() && list.get(idx) == 0) idx++;
if (idx == list.size()) return 0;
int min = Integer.MAX_VALUE;
for(int i=idx+1; i<list.size(); i++) {
// 부호가 다른 쌍만 거래 가능
if ((list.get(idx) > 0 && list.get(i) < 0) || (list.get(idx) < 0 && list.get(i) > 0)) {
list.set(i, list.get(i) + list.get(idx));
min = Math.min(min, 1 + dfs(idx + 1, list));
list.set(i, list.get(i) - list.get(idx));
}
}
return min;
}
}문자열 한 글자 차이 판단
목표 : 두 문자열이 한 글자의 삽입, 삭제, 수정 중 하나만 차이날 경우 true 반환
해결방법 : 조건문과 투포인터로 해결했다.
- 길이 비교로 케이스 분리
- 길이가 같을 경우: 수정 1회 가능 -> 문자 비교로 다른 개수 1개 확인
- 길이 차이 1: 삽입 또는 삭제 가능 -> 투 포인터로 다른 지점에서 한 번만 건너뜀
- 그 외는 모두 false
코드
class Solution {
public boolean solution(String s, String t) {
int sLen = s.length();
int tLen = t.length();
if (sLen == tLen) {
return isOneDiff(s, t);
} else if (sLen == tLen + 1) {
return isOneEdit(s, t);
} else if (sLen + 1 == tLen) {
return isOneEdit(t, s);
}
return false;
}
// 수정이 1번만 일어났는 지 확인
boolean isOneDiff(String s, String t) {
int diff = 0;
for (int i=0; i<s.length(); i++) {
if (s.charAt(i) != t.charAt(i)) {
diff++;
if (diff > 1) return false;
}
}
return true;
}
// 삽입 또는 삭제가 1번만 일어났는지 확인
boolean isOneEdit(String longStr, String shortStr) {
int i = 0, j = 0;
boolean diff = false;
while (i < longStr.length() && j < shortStr.length()) {
if (longStr.charAt(i) == shortStr.charAt(j)) {
i++;
j++;
} else {
if (diff) return false;
diff = true;
i++;
}
}
return true;
}
}문장 이어붙이기
목표 : 구문 목록에서 문장 끝 단어와 다음 문장 시작 단어가 같을 경우 두 문장을 이어 붙인다.
해결방법 : Set + 반복문으로 해결했다.
구문을 순회하며 앞 구문 끝 단어어와 뒷 구문 첫 단어가 같은 경우 겹치는 단어를 한 번만 사용해 문장을 이어붙인다. 중복이 없어야 되기 때문에 Set을 사용해 중복 제거 후 List로 사전 순으로 정렬해 반환했다.
코드
import java.util.*;
class Solution {
public String[] solution(String[] phrases) {
Set<String> set = new HashSet<>();
for(String first : phrases) {
for(String second : phrases) {
String[] firstWords = first.split(" ");
String[] secondWords = second.split(" ");
String lastWord = firstWords[firstWords.length - 1];
String firstWord = secondWords[0];
// 마지막 단어와 첫 단어가 같을 때 이어붙이기
if (lastWord.equals(firstWord)) {
StringBuilder sb = new StringBuilder();
sb.append(first);
for(int i=1; i<secondWords.length; i++) {
sb.append(" ").append(secondWords[i]);
}
set.add(sb.toString());
}
}
}
List<String> list = new ArrayList<>(set);
return list.stream().sorted().toArray(String[]::new);
}
}문장 유사도
목표 : 두 문장의 단어들을 비교하여 직접 또는 간접적으로 유사한 단어쌍일 경우 유사도를 구하기
해결방법 : Union - Find로 해결했다.
직접 연결되는 단어 뿐만 아니라 간접으로 연결된 단어도 유사하다고 판단해야하므로 유사 그룹을 하나로 묶는 Union - Find가 적합하다고 생각했다.
- 단어쌍을 기반으로 유사 그룹을 Union-Find으로 구성
- 각 단어를 find로 부모를 조회
- 유사 단어를 그래프로 연결해 간접 유사도까지 처리
s[i] == t[i]또는find(s[i]) == find(t[i])이면 유사도 +1
코드
import java.util.*;
class Solution {
public int solution(String s, String t, String[][] similarWords) {
int answer = 0;
Map<String, String> map = new HashMap<>();
String[] sWords = s.split(" ");
String[] tWords = t.split(" ");
// 초기 부모 설정
for(String[] pair : similarWords) {
for(String word : pair) {
map.putIfAbsent(word, word);
}
}
// Union 처리
for(String[] pair : similarWords) {
union(map, pair[0], pair[1]);
}
// 유사도 비교
for(int i=0; i<sWords.length; i++) {
String a = sWords[i];
String b = tWords[i];
if (a.equals(b)) answer++;
else {
String parentA = find(map, a);
String parentB = find(map, b);
if (parentA != null && parentB != null && parentA.equals(parentB)) {
answer++;
}
}
}
return answer;
}
String find(Map<String, String> map, String word) {
if (!map.containsKey(word)) return word;
if (!word.equals(map.get(word))) {
map.put(word, find(map, map.get(word)));
}
return map.get(word);
}
void union(Map<String, String> map, String a, String b) {
String parentA = find(map, a);
String parentB = find(map, b);
if (parentA != null && parentB != null && !parentA.equals(parentB)) {
map.put(parentA, parentB);
}
}
}스트로보그램 숫자 생성
목표 : n자리 수 중 180도 회전해도 똑같이 보이는 스트로보그램 숫자들을 구해 사전순으로 정렬
해결방법 : DFS로 해결했다.
스트로보그램 숫자는 180도 회전했을 때도 동일한 모양을 유지해야 하기 때문에 양쪽(앞과 뒤)에서 대칭이 성립되어야 한다. 따라서 이 문제는 가운데부터 시작해서 가능한 숫자 쌍을 양쪽에 동시에 붙여가며 완성하는 방식이 적합하다고 판단했다. 이를 구현하기 위해 재귀(DFS) 구조를 사용했고 각 재귀 단계마다 양쪽 자리를 채우기 때문에 한 번의 호출로 자리 수가 2개씩 줄어들게 된다. 중간이 채워지면 가능한 쌍을 양쪽에 붙이고 가장 바깥 자리에 0이 오는 것을 방지하기 위해 리딩 제로 조건을 따로 처리했다.
- 회전해도 대칭이 유지되는 숫자 쌍을 미리 정의 (
0-0,1-1,6-9,8-8,9-6) - 재귀적으로 가운데 문자열부터 생성한 뒤 해당 문자열의 양끝에 가능한 쌍을 붙여 완전한 수를 구성
- 각 재귀 단계마다
n -= 2를 하면서 양쪽 두 자리를 동시에 채우기 때문에 한 번의 재귀에서 실제로 두 자릿수를 채움 - 종료 조건으로
n == 0(짝수 길이일 때),n == 1(홀수 길이일 때)의 경우 가능한 중간 문자열 반환 - 리딩 제로 방지를 위해 가장 바깥자리(
n == totalLength)에는'0'을 붙이지 않도록 처리- 이때 앞자리가 아니라
n == totalLength로 조건을 둔 이유는 숫자 쌍을 앞뒤로 동시에 붙이기 때문에 앞자리든 뒷자리든 하나라도 가장 바깥자리에 해당하면 해당 조건 하나로 둘 다 걸러낼 수 있기 때문이다.
- 이때 앞자리가 아니라
- 최종적으로 생성된 문자열들을 사전 순 정렬하여 배열로 반환
코드
import java.util.*;
class Solution {
char[][] pairs = {
{'0', '0'},
{'1', '1'},
{'6', '9'},
{'8', '8'},
{'9', '6'}
};
public String[] solution(int n) {
List<String> answer = strobogramNum(n, n);
return answer.stream().sorted().toArray(String[]::new);
}
List<String> strobogramNum(int n, int totalLength) {
if (n == 0) return List.of("");
if (n == 1) return List.of("0", "1", "8");
// 가운데 먼저 생성
List<String> list = strobogramNum(n - 2, totalLength);
List<String> result = new ArrayList<>();
for(String mid : list) {
for(char[] pair : pairs) {
// 가장 바깥 자리에는 0이 올 수 없음
if (n == totalLength && pair[0] == '0') continue;
// 양쪽에 쌍 붙이기
result.add(pair[0] + mid + pair[1]);
}
}
return result;
}
}
개발자가 되고 싶은 취준생