프로그래머스 160586번
https://school.programmers.co.kr/learn/courses/30/lessons/160586
먼저 문제를 풀은 방법은, keymap
배열에 각 순서별로 문자들이 나오는데,
targets
에서 만들때 가장 먼저나오는 문자를 우선으로 사용하면 되기 때문에
keymap
을 순회하면서 나오는 문자와 순서를 저장하기 위해 (문자열, keymap의 순서)로 Key
객체를 만든다.
그리고 Key
객체에 이미 contains
를 통해 존재할경우 Math.min()
메소드를 사용해서 각 문자별 최단 위치를 저장해놓으면 된다.
여기서 Key
타입의 List에서 알파벳을 기준으로 contains()
메소드를 사용하기 위해 equals 메소드를 @Override를 해줘야하므로 구현했다.
@Override
public boolean equals(Object obj) {
if(this == obj) return true;
if(obj == null || getClass() != obj.getClass()) return false;
Key key = (Key) obj;
return Objects.equals(alp, key.alp);
}
public int[] solution(String[] keymap, String[] targets) {
int keymapLen = keymap.length;
List<Key> list = new ArrayList<>();
for(int i=0; i<keymapLen; i++) {
char[] temp = keymap[i].toCharArray();
int len = temp.length;
for(int j=0; j<len; j++) {
char ch = temp[j];
if(list.contains(new Key(ch, 1))) {
int idx = list.indexOf(new Key(ch, 1));
list.get(idx).min = Math.min(j + 1, list.get(idx).min);
} else {
list.add(new Key(ch , j + 1));
}
}
}
list 결과
[Key {alp :A, min : 1}
, Key {alp :B, min : 1}
, Key {alp :C, min : 2}
, Key {alp :D, min : 5}
, Key {alp :E, min : 3}
, Key {alp :F, min : 4}
]
int[] ans = new int[targetLen];
for(int i=0; i<targetLen; i++) {
String str = targets[i];
int len = str.length();
int sum = 0;
for(int j=0; j<len; j++) {
char ch = str.charAt(j);
if(!list.contains(new Key(ch, 1))) {
sum = -1;
break;
} else {
sum += list.get(list.indexOf(new Key(ch, 1))).min;
}
}
ans[i] = sum;
}
이제 여기서 list에 있는 값을 sum
에 합해준다. 없을 경우에는 -1을 넣어주면 된다.
import java.util.*;
class Solution {
static class Key {
char alp;
int min;
public Key(char alp, int min) {
this.alp = alp;
this.min = min;
}
@Override
public String toString() {
return "Key {alp :" + alp + ", min : " + min + "} \n";
}
@Override
public boolean equals(Object obj) {
if(this == obj) return true;
if(obj == null || getClass() != obj.getClass()) return false;
Key key = (Key) obj;
return Objects.equals(alp, key.alp);
}
} // End of Key class
public int[] solution(String[] keymap, String[] targets) {
int keymapLen = keymap.length;
List<Key> list = new ArrayList<>();
for(int i=0; i<keymapLen; i++) {
char[] temp = keymap[i].toCharArray();
int len = temp.length;
for(int j=0; j<len; j++) {
char ch = temp[j];
if(list.contains(new Key(ch, 1))) {
int idx = list.indexOf(new Key(ch, 1));
list.get(idx).min = Math.min(j + 1, list.get(idx).min);
} else {
list.add(new Key(ch , j + 1));
}
}
}
int targetLen = targets.length;
int[] ans = new int[targetLen];
for(int i=0; i<targetLen; i++) {
String str = targets[i];
int len = str.length();
int sum = 0;
for(int j=0; j<len; j++) {
char ch = str.charAt(j);
if(!list.contains(new Key(ch, 1))) {
sum = -1;
break;
} else {
sum += list.get(list.indexOf(new Key(ch, 1))).min;
}
}
ans[i] = sum;
}
return ans;
} // End of solution()
} // End of Solution class