▷ 문제 : Bigger is greater (Medium)
Bigger is Greater | HackerRank
Rearrange the letters of a string to construct another string such that the new string is lexicographically greater than the original.
www.hackerrank.com
▷ 해결 날짜 : 2022.04.21
▷ 소요 시간 : 1시간 30분
▷ 풀이 과정 :
반환값으로 주어진 문자열의 다음으로 사전순으로 높은 문자열 또는 no answer을 출력하면 되는 문제다.
예를 들어 abcd 가 주어졌다면 출력으로 abdc를 반환해야한다는 의미이다.
몇가지 주의사항이 있는데,
1. 원래 단어보다 커야 한다.
2. 1번 조건을 충족하는 가장 작은 단어여야 한다.
이 조건을 가지고 구현에 들어가 보면
- 우선 'dkhc'라는 문자열을 입력 받았다고 하면.
- 뒤에서부터 하나씩 스캔하여 바뀌는 부분을 검색한다. h > c, k > h, d < k 이므로 바뀌는 부분은 d인 0번 인덱스이다.
- 그 다음은 0번 이후로 나오는 값들 중에서 d보다 큰 값 중에 가장 작은 수의 위치를 찾아내야 한다. (h이므로 2인덱스)
- 이렇게 changedIdx 와 minIdx를 구했으면 그 둘을 교체해주고 교체해준 index 이후로 나오는 나머지 값들을 사전순으로 정렬 시켜줘야 한다. 그 이유는 문제 상단에 가보면 '사전순으로 정렬된' 이며, 주의사항을 지키려면 결국 사전순이여야 하기 때문이다.
- 이 과정을 통해 나오는 결과값은 'hcdk' 이다.
아 물론 구현과정에서 이중 for문을 통해 더 깔끔하게 구할수도 있었겠지만,
알다시피 시간복잡도가 이중 for문의 경우 O(n^2)이기때문에 반복문은 하나씩만 돌려 시간복잡도 O(n)을 가져가도록 하자.
▷ 구현
function biggerIsGreater(w) {
// Write your code here
const str = w.split('');
let changedIdx = -1;
let minIdx = -1;
for(let i = str.length - 1 ; i > 0 ; i--){
if(str[i] > str[i - 1]){
changedIdx = i - 1;
break;
}
}
for(let i = changedIdx + 1 ; i < str.length ; i++){
if(str[changedIdx] < str[i]){
if(minIdx >= 0 && str[minIdx] > str[i]) minIdx = i;
else if(minIdx < 0) minIdx = i;
}
}
let result = 'no answer';
if(changedIdx >= 0){
[str[changedIdx], str[minIdx]] = [str[minIdx], str[changedIdx]];
result = [...str.slice(0, changedIdx + 1), ...str.slice(changedIdx + 1).sort()].join('');
}
return result;
}
▷ 복기 :
저 사전순에서 헤매서 생각보다 시간을 오래 잡아먹었다... 어렵다 어려워
댓글