🤔 문제
🔗
정수 n과 삭제된 주문들을 담은 1차원 문자열 배열 bans가 매개변수로 주어질 때, 삭제가 완료된 주문서의 n번째 주문을 return 하도록 solution 함수를 완성해 주세요.
👊 풀이과정
배열로 주어진 일부 주문이 삭제된 후, 특정 순서에 해당하는 주문을 찾는 문제이다.
진법 개념을 사용했는데, 알파벳 개수는 26개이므로 26진법으로 풀이하며, 이하 '알파벳26진법'이라고 칭하겠다.
주문 a의 순서는 1, b는 2... z는 26번째
aa는 26*1 + 1*1 = 27번째
ab는 26*1 + 1*2 = 28번째
주문 a를 1로, 주문 z를 26으로 두고 계산해보면 해당 주문의 순서는 26진법을 10진법으로 변환했을 때와 동일함을 알 수 있다.
이에 따라 필요한 기능들은 다음과 같으며, 차례대로 구현해볼 것이다.
- 주문의 알파벳을 10진법 숫자로 변환하는 메서드
- 10진법 숫자를 주문의 알파벳26진법으로 변환하는 메서드
- 1,2를 통해 주문에 해당하는 순서를 찾는 메서드
- 10진법 순서에 해당하는 주문 문자열을 찾는 메서드
그렇다면 우선 문자를 정수타입으로, 정수를 문자타입으로 바꾸는 메서드를 작성해보자.
char <-> long 타입의 자유로운 변환이 가능한 점을 이용하자.
// 문자를 정수타입으로 변환
private long charToLong(char val) {
return (long)val - 96;
}
// 정수를 문자타입으로 변환
private char longToChar(long val) {
return (char)(val + 96);
}
이제 26진법으로 작성된 주문을 10진법 숫자로 변환하는, 다시말해 주문의 순서를 리턴하는 메서드를 작성할 수 있다.
밑값과 지수값을 받아 거듭제곱해주는 Math 클래스의 pow()를 활용했다.
// 전달받은 주문의 일반적인 순서 리턴
private long getSnoOfBan(String val) {
long sno = 0;
// adz = 26^2*a + 26^1*d + 26^0*z
for(int idx = 0 ; idx < val.length() ; idx++) {
sno += Math.pow(26, val.length() - idx - 1) * charToLong(val.charAt(idx));
}
return sno;
}
다음은 특정 순서에 해당하는 주문을 찾는 메서드를 작성해야 한다.
원리는 10진법 숫자를 26진법으로 변환하는 것으로 간단해보인다.
하지만 주의할 점이 있다.
앞서 알파벳을 숫자로 변환할 때, a-z는 각각 1-26까지의 숫자로 치환되었다.
만약 52라는 10진법 숫자를 26진법으로 변환한다면 어떻게 해야할까?
(26^1*2 + 26^0*0)ㅡ b0이 되는게 맞겠지만, 알파벳26진법에 0을 치환할 수 있는 알파벳은 존재하지 않는다.
따라서 (26^1*1 + 26^0*1)ㅡ az로 다소 억지스럽게 변환해주어야 한다.
이처럼 26으로 나누어 떨어지는 수에 대한 변환규칙은 조건문을 통해 구현했다.
// 전달받은 순서에 해당하는 주문을 리턴
private String getBanOfSno(long val) {
String res = "";
while(val > 0) {
long c = val / 26;
long n = val % 26;
// 알파벳진수에서는 0이 존재하지 않음
// 따라서 나머지가 0인 경우 해당자릿수를 z(=26)로 만들고 다음지수 값을 -1해줌
// ex. 52 는 b0(26^1*2 + 26^0*0)이 아닌, az(26^1*1 + 26^0*26)으로 표현
if(c > 0 && n == 0) {
n = 26;
c -= 1;
}
res = longToChar(n) + res;
val = c;
}
return res;
}
이제 위에서 작성한 기능들을 활용해 문제를 풀어보자.
전달받은 삭제 대상 주문 배열을 문제에 명시된 기준에 따라 정렬한다.
이제 주문을 하나씩 삭제해 나갈텐데, 문제에서 주어진 n을 기준으로 앞쪽 주문이 삭제되면 인덱스가 밀리게 되므로 조건문을 통해 검증한다.
모든 대상을 삭제한 후 최종적으로 변경된 n번째 순서에 해당하는 주문을 찾아내면 된다.
public String solution(long n, String[] bans) {
// 배열을 글자수, 사전순서로 정렬
Arrays.sort(bans, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
} else {
return o1.length() - o2.length();
}
}
});
for(String ban : bans) {
long sno = getSnoOfBan(ban);
// 삭제될 문자열이 찾아야할 순번보다 순번이 같거나 작은 경우, 뒤로 밀어줌
if(sno <= n) {
n++;
}
}
return this.getBanOfSno(n);
}💻 소스코드
import java.util.*;
class Solution {
public String solution(long n, String[] bans) {
// 배열을 글자수, 사전순서로 정렬
Arrays.sort(bans, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
} else {
return o1.length() - o2.length();
}
}
});
for(String ban : bans) {
long sno = getSnoOfBan(ban);
// 삭제될 문자열이 찾아야할 순번보다 순번이 같거나 작은 경우, 뒤로 밀어줌
if(sno <= n) {
n++;
}
}
return this.getBanOfSno(n);
}
// 문자를 정수타입으로 변환
private long charToLong(char val) {
return (long)val - 96;
}
// 정수를 문자타입으로 변환
private char longToChar(long val) {
return (char)(val + 96);
}
// 전달받은 주문의 일반적인 순서 리턴
private long getSnoOfBan(String val) {
long sno = 0;
for(int idx = 0 ; idx < val.length() ; idx++) {
sno += Math.pow(26, val.length() - idx - 1) * charToLong(val.charAt(idx));
}
return sno;
}
// 전달받은 순서에 해당하는 주문을 리턴
private String getBanOfSno(long val) {
String res = "";
while(val > 0) {
long c = val / 26;
long n = val % 26;
// 알파벳진수에서는 0이 존재하지 않음
// 따라서 나머지가 0인 경우 해당자릿수를 z(=26)로 만들고 다음단계 값을 -1해줌
// ex. 52 는 b0(26*2 + 1*0)이 아닌, az(26*1 + 1*26)으로 표현
if(c > 0 && n == 0) {
n = 26;
c -= 1;
}
res = longToChar(n) + res;
val = c;
}
return res;
}
}