문제 이해하기
소문자 영어 알파벳으로 이루어진 문자열 str과 배열의 배열 arr이 주어져 있다고 가정해 보겠습니다. 각 요소는 arr[i] = [direction, amount] 형태를 가집니다.
- direction은 0(왼쪽 시프트) 또는 1(오른쪽 시프트)입니다.
- amount는 문자열을 시프트할 횟수입니다.
- 왼쪽으로 1 시프트란 첫 번째 문자를 제거하여 맨 뒤에 붙이는 것을 의미합니다.
- 마찬가지로 오른쪽으로 1 시프트란 마지막 문자를 제거하여 맨 앞에 추가하는 것을 의미합니다.
우리는 첫 번째 인자로 문자열을, 두 번째 인자로 시프트 정보가 담긴 배열을 받는 JavaScript 함수를 작성해야 합니다. 함수는 배열을 순회하며 필요한 시프트 연산을 수행한 뒤, 최종 결과 문자열을 반환합니다.
예시
입력 문자열과 배열이 다음과 같다고 해보겠습니다.
const str = 'abc';
const arr = [[0, 1], [1, 2]];
기대하는 출력 결과는 다음과 같습니다.
const output = 'cab';
그 이유는 다음과 같습니다.
- [0,1]은 왼쪽으로 1 시프트를 의미합니다. "abc" → "bca"
- [1,2]는 오른쪽으로 2 시프트를 의미합니다. "bca" → "cab"
효율적인 접근 방법
명령 하나하나마다 매번 문자열을 잘라내고 이어붙이는 대신, 왼쪽 시프트 총량과 오른쪽 시프트 총량을 각각 누적한 후 서로 상쇄하는 것이 훨씬 효율적입니다. 최종적으로 남은 시프트 양을 문자열 길이로 나눈 나머지만큼 한 번에 처리하면 되기 때문입니다. 이 방식을 사용하면 불필요한 반복 연산을 줄여 전체 시간 복잡도를 O(n) 수준으로 유지할 수 있습니다.
구현 코드
const str = 'abc';
const arr = [[0, 1], [1, 2]];
const performShifts = (str = '', arr = []) => {
if(str.length < 2){
return str;
};
let right = 0
let left = 0;
for(let sub of arr){
if(sub[0] == 0){
left += sub[1];
}else{
right += sub[1];
};
};
if(right === left){
return str;
}
if(right > left){
right = right - left;
right = right % str.length;
return str.substring(str.length - right) + str.substring(0,
str.length - right);
}else{
left = left - right;
left = left % str.length;
return str.substring(left) + str.substring(0,left);
};
};
console.log(performShifts(str, arr));
출력 결과
콘솔에는 다음과 같이 출력됩니다.
cab
코드 설명
핵심 로직을 단계별로 살펴보면 다음과 같습니다.
- 문자열 길이가 2 미만이면 시프트를 해도 결과가 동일하므로 그대로 반환합니다.
- 배열을 순회하면서 direction 값에 따라 왼쪽 시프트 총량(left)과 오른쪽 시프트 총량(right)을 각각 누적합니다.
- 두 값이 같으면 모든 시프트가 상쇄되므로 원본 문자열을 그대로 반환합니다.
- 오른쪽 시프트가 더 크면 두 값의 차이를 구하고, 문자열 길이로 나눈 나머지를 이용해 substring으로 새 문자열을 조합합니다.
- 왼쪽 시프트가 더 큰 경우에도 동일한 방식으로 처리합니다.
이처럼 시프트 명령을 일괄 누적하고 나머지 연산으로 정리하면, 명령이 아무리 많아도 문자열 조합은 단 한 번만 수행되므로 성능 면에서 큰 이점을 얻을 수 있습니다.