📌강의 정리
문제만 읽고 이해가 안될때는 입력과 출력을 보고 다시 문제를 이해해보자.
매 문자마다 e가 어디있는지 판단하면서 코드를 작성할수는 있지만 그건 힘든일이다.
포문을 정방향으로 한번돌고 역방향으로 돌면 해결할 수 있다.
시간 복잡도는 O(N)이다.
2N처럼 계수는 생략한다.
p라는 변수를 1000으로 하고 e를 만나지않으면 ++해준다.
e를 만나면 p를 0으로 초기화해준다.
그럼 answer = 1001, 0, 1,2,3,0,1,2,3,4,0이 된다.
이 의미는 자기 왼쪽에 e와 떨어진 거리를 의미한다.
따라서 처음의 p가 1001처럼 큰값을 받은것이다.
그럼 이제 포문을 역방향으로 가면 또 같은방법으로 하면 된다.
p가 계속 ++되며 바뀌는 그 방법이다.
이때 answer를 바꿔주는데 최소값을 구해야하므로 둘을 비교하여 작은 값을 넣어두고 있는다.
for문을 돌리면서 x of s에서 x와 t가 같으면 p=0이되고 answer에 p=0을 푸시하면 된다.
반대로 같지 않다면 p++하며 p를 푸시하면 된다.
이후 인덱스번호를 이용한 for문을 써서 역방향으로 i - -로 돌면서 같으면 p=0하고 그냥 지나가고 그다음 다를경우 p++하고 answer값과 이값을 비교하여 answer[i] = Math.min(answer[i], p)를 하여 작은값을 넣어준다.
📌느낀점
내가 푼 방법과 강사님이 푼방법이 다르다.
나는 내 방법이 좋은지 알았는데 시간복잡도 측면에서 강사님의 코드가 더 좋다..
한발자국이 모자른것 같다.
중요한것은 다음에 비슷한 문제를 풀때는 좀 더 효율적인 방법을 써야한다는 것이다.
//나의 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(s, t){
let answer=[];
let a = s.split('e');
console.log(a);
a.pop();
console.log(a);
for(let i=0; i<a.length; i++){
for(let j=0; j<a[i].length; j++){
if(j<a[i].length/2) answer.push(j+1);
else if(j>=a[i].length/2){
answer.push(a[i].length-j);
}
}
answer.push(0);
}
console.log(a);
return answer;
}
let str="teachermodeqwrtye";
console.log(solution(str, 'e'));
</script>
</body>
</html>
//220605 추가 나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(s, t) {
let answer = [];
let min = Number.MAX_SAFE_INTEGER;
let cnt = 0;
let test = -7;
console.log(Math.abs(test));
for (let i = 0; i < s.length; i++) {
for (let j = 0; j < s.length; j++) {
if (s[j] === t) {
cnt = Math.abs(j - i);
if (cnt < min) min = cnt;
}
}
answer.push(min);
min = Number.MAX_SAFE_INTEGER;
}
return answer;
}
let str = "teachermode";
console.log(solution(str, "e"));
</script>
</body>
</html>//강사님 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(s, t){
let answer=[];
let p=1000;
for(let x of s){
if(x===t){
p=0;
answer.push(p);
}
else{
p++;
answer.push(p);
}
}
p=1000;
for(let i=s.length-1; i>=0; i--){
if(s[i]===t) p=0;
else{
p++;
answer[i]=Math.min(answer[i], p);
}
}
return answer;
}
let str="teachermode";
console.log(solution(str, 'e'));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 3. 문자열 탐색' 카테고리의 다른 글
| 5.문자열 압축 (0) | 2022.01.13 |
|---|---|
| 3.숫자만 추출 (0) | 2022.01.13 |
| 2.유효한 팰린드롬 (0) | 2022.01.13 |
| 1.회문 문자열 (0) | 2022.01.13 |