문제요약
사용자가 컴퓨터 키보드로 텍스트를 입력한다 생각했을때, 키 입력 문자열을 보고 결과 문자열이 무엇인지 출력하여라
1. 입력값으로는 테스트 케이스 별 문자열이 주어진다.
ex) <<BP<A>>Cd-
2. < 는 뒤로 커서이동, > 는 앞으로 커서이동, -는 커서 뒤 문자하나 삭제 한다.
3. 출력값 : ex) BAPC
문제 링크 : https://www.acmicpc.net/problem/5397
첫번째 풀이 - 자바스크립트의 splice를 이용 (통과 못합니다.)
array.splice(index, num)라는 메서드는 배열의 중간 index로 부터num까지의 배열을 잘라내거나 조작할 수 있다.array.splice(index, 0, 'A')를 통해 배열의 중간 index 사이에 문자를 새로 끼워둘 수 있다.
- index = 0, answer = [ ];
- 텍스트 문자가 올때는 answer 배열 내 index에 splice 메서드를 통해 하나씩 요소를 넣으면서 index를 1씩 증가시킨다.
<가 오면 index에 -1 을 하고 splice 메서드를 통해 요소를 삽입한다.>가 오면 index에 +1 을 하고 splice 메서드를 통해 요소를 삽입한다.-가 오면 index 바로 뒤 요소을 splice를 통해 삭제한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const T = input.shift();
for (let i = 0; i<T; i++) {
password(input[i].split(''))
}
function password(str) {
let answer = [];
let idx = 0;
str.forEach((kp) => {
// console.log('현재 입력', kp);
// console.log('현재 커서위치', idx);
if (kp == '-') {
answer.splice(idx-1,1);
}
else if (kp == '>') {
idx == answer.length || idx ++;
}
else if (kp == '<') {
idx == 0 || idx --;
}
else {
answer.splice(idx, 0, kp)
idx ++;
// console.log(answer);
}
})
console.log(answer.join(''));
}주어진 테스트 케이스 또한 잘 통과하길래 무난히 한 문제 풀었다 생각했는데,
아주 오만한 생각이었다.
무엇이 문제이냐.
splice 메서드는 는 O(n)의 시간 복잡도를 가지는 녀석.
편리한 만큼 대가를 치뤄야했다.
splice 메서드는 배열을 조작한 후 index를 재정렬하는 과정이 필요함으로 O(n)의 시간복잡도를 가지게 된다. 해당 문제에서 요구하는 시간제한은 1초에 불과한데, 주어진 문자열의 길이만큼 splice 메서드를 실행시키니 내 정답은 O(n^2)의 시간복잡도를 가진 알고리즘이 되었다.
다른 방법을 통해 더 효율적인 해결방안을 찾아야 했다.
두번째 풀이 : 2개의 array를 이용한 풀이 (front, back)
여러 삽질을 거듭하다, 답을 발견했다.
커서가 등장하는 문제에 경우
커서에 앞, 뒤를 각각 다른 배열을 선언 한 후 앞쪽 배열의 요소를 뒤쪽 배열에 갇다 붙힘으로써 커서의 이동과 동일한 효과를 낼 수 있다.
반대로 커서가 뒤로 이동하는 경우
해당 그림 처럼 Front 배열은 pop(), push()를 사용하고, Back 배열은 shift(), 와 unshift()를 통해 커서의 이동을 구현할 수 있었다.
제출 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const T = input.shift();
for (let i = 0; i<T; i++) {
password(input[i].split(''))
}
function password(str) {
let front = [];
let back = [];
str.forEach((kp) => {
if (kp == '-') {
front.length == 0 || front.pop();
}
else if (kp == '>') {
back.length == 0 || front.push(back.shift());
}
else if (kp == '<') {
front.length == 0 || back.unshift(front.pop());
}
else {
front.push(kp);
}
// console.log('front: ',front);
// console.log('back: ',back);
})
console.log(front.join('')+back.join(''));
}근데 위 풀이도 시간초과가 나온다.
알아보니, 배열 메소드 중
- pop(): 시간복잡도 - O(1)
- push(): 시간복잡도 - O(1)
- shift(): 시간복잡도 - O(n)
- unshift(): 시간복잡도 - O(n)
shift 와 unshift 또한 꽤나 시간복잡도가 높은 메서드라 사용하면 안됐었던 것.
최종 풀이 : Back배열은 뒤집어도 똑같다.
커서를 설명하기 위한 그림에 스스로 함정에 빠졌다. 그림 속 Back 배열에 경우 커서의 위치를 설명하기 위해 배열에 앞부분 부터 삽입이 진행되고 앞쪽에서 빠져야하는 걸로 생각했는데 사실, 단순한 push(), pop() 으로 같은 기능을 구현할 수 있으며, 최종적으로 출력시 reverse() 를 통해 거꾸로 출력하면 같은 효과를 낼 수 있으면서 더 효율적인 알고리즘을 짤 수 있었다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const T = input.shift();
for (let i = 0; i<T; i++) {
password(input[i].split(''))
}
function password(str) {
let front = [];
let back = [];
str.forEach((kp) => {
if (kp == '-') {
front.length == 0 || front.pop();
}
else if (kp == '>') {
back.length == 0 || front.push(back.pop());
}
else if (kp == '<') {
front.length == 0 || back.push(front.pop());
}
else {
front.push(kp);
}
// console.log('front: ',front);
// console.log('back: ',back);
})
console.log(front.join('')+back.reverse().join(''));
}요약
- 커서를 이용하여 풀어야하는 문제는 front, back 두 개의 배열을 이용하여 푼다.
- 배열 메서드의 시간복잡도를 생각하고 써야한다.
- O(n) splice, shift, unshift
- O(1) pop, push
