추억 점수
귀찮은 문제다... 반복문 3중첩은 피하고 싶다.
나의 풀이
function sol0(name, yearning, photo) {
var answer = [];
const nLength = name.length
const pLength = photo.length
for (let i = 0 ; i < pLength ; i++) {
answer[i] = 0
}
for (let i = 0; i < nLength ; i++) {
const nameNow = name[i]
for (let j = 0 ; j < pLength ; j++) {
const kLength = photo[j].length
for (let k = 0 ; k < kLength ; k++) {
if ( photo[j][k] === nameNow)
answer[j] += yearning[i]
}
}
}
return answer;
}3중첩밖에 생각이 안나서 이렇게 해버렸다.
시간 복잡도는 정신이 아찔하다...
다른 사람의 풀이
function sol1(name, yearning, photo) {
return photo.map((v)=> v.reduce((a, c)=> a += yearning[name.indexOf(c)] ?? 0, 0))
}photo.map((v)=> : photo 배열안의 요소들에게 이하의 함수를 실핸한다.
v.reduce((a, c)=> : photo 배열안의 요소 = 그안의 작은 배열들의 내용물 c에 대해 a를 쌓는다.
a += yearning[name.indexOf(c)] ?? 0, 0)) : 초기값0, 값이 무효할경우(nullorunidentified) 0 반환
*name.indexOf(c) : name배열에 존재하는 이름이면
a에 해당 이름과 같은 인덱스 넘버의 yearning의 값을 더한다.
시간 복잡도는 이다. (N부터 시작하는것이 일반적이나 내 코드의 시간복잡도와 비교하기 위해서 M부터 시작했다.)
for문으로 풀어 쓰다가 깨달았다.
아... 반복은 photo안에서하는데 그걸 name의 요소별로 하고 그걸 정의하려해서 3중 반복이 되었구나.
하나하나 반복 시키지말고 name과 photo안의 배열에 겹치는게 있는지 봐야했구나.
function sok01(name, yearning, photo) {
var answer = [];
const pLength = photo.length
for (let i = 0 ; i < pLength ; i++){
const pILength = photo[i].length
let sum = 0
for (let j = 0 ; j < pILength ; j++) {
const indexName = name.indexOf(photo[i][j]);
if (indexName !== -1) {
sum += yearning[indexName]
}
}
answer.push(sum)
}
return answer;
}속도 비교
당연히 횟수만 증가시켜서는 꼴로 증가했다.
name과 photo내의 요소들을 9배 증가 시켜도 아무런 차이가 없다.
yearning값의 길이를 10배 증가시키니 변화가 생기긴했는데 너무 오락가락한다. 심지어 값을 증가시켰는데 더 빨라지는 경우도 있다??
photo의 값을 10배 증가 시키니 정상적(?)으로 증가하는 모습이다.
보다시피 모든 입력값을 10배 증가시킨것은 photo만 10배 증가 시킨것과 같다!
yearning이 이상하게 널뛰기해서 전부 곱한 경우에도 널뛰기 할줄 알았는데 아니어서 의외였다.
- 잠정결론 : 시간 복잡도는 중요하지만 N^3이 아니라 NML과 같이 여러개가 복잡하게 얽힌 경우에는 생각만큼 크게 증가하지 않을 수 도 있다.
시간 복잡도는 절대적인 요소가 아니고, 코드에 사용된 메서드와 구현 방식등도 중요하다.
짝지어 제거하기
문자열을 배열로 바꾸고 요소들의 값을 비교해야겠다.
들어가기전에
문자열을 배열로 바꾸는 법은 세가지가 있다.
모두 복잡도를 가지기 때문에 입력값이 10배 증가하면 10배 이하로 늘어났다.
반복 횟수에서도 마찬가지이다.
str.split("")이 [...str], Array.from(str)보다 2.2~2.5배 빨랐고 나머지 둘의 속도는 비슷했다.
심지어 반복이나 입력량이 늘어나도 증가량이 항상 가장 적었다.
split이 나머지 둘 보다 응용성도 뛰어남을 고려하면 나머지 둘을 사용할 필요가 없어보인다.
이게 실제로 짠 코드에도 그대로 반영되는지 보겠다.
나의 코드
function solution(s){
let str = s.split("");
let newStr = []
let i = 0
while (true) {
if (str[i] === str[i+1]) {
newStr = str.splice(i, i+1)
}
if (newStr === str) {
return 1
} else if (newStr === []) {
return 0
} else if ( i >= str.length ) {
i = 0
str = newStr
} else {
i++
}
}
}newStr === str 에서 오류가 생겼다. 배열의 내용물이 아니라 참조를 봤기 때문이다. 현재 조건에서는 길이만 봐도 될듯하다.
해당 방식으로 구현하다가 도저히 되지 않아서 GPT를 사용하였다.
GPT 답안
function solution(s) {
let stack = [];
for (let char of s) {
if (stack.length > 0 && stack[stack.length - 1] === char) {
stack.pop();
} else {
stack.push(char);
}
}
return stack.length === 0 ? 1 : 0;
}char는 s의 문자열을 0번부터 탐색
stack에는 s의 문자열이 -1번째부터 담긴다. = unidentifed부터 시작
만약 stack에 이번에 담을 문자와 char가 같다면 연속된 두개의 문자가 있는 것이므로 stack에 담지 않고 마지막 값을 뺀다. = return값에서 연속된 같은 값이 사라진다.
만약 이번에 중복된 값을 제거해서 떨어져있던 중복값이 만난 경우 1221 > 11 에도 정상적으로 현재 넣어야할 값과 남아있는 마지막 값을 비교해서 판단한다.
모든 루프가 끝나면 stack의 길이를 기준으로 1과 0을 리턴한다.
속도 변화
시간복잡도가 이기 때문에 정직하게 증가한다.
항상 N의 길이만큼 반복해야하기 때문에 최악의 경우가 나왔다.
값 전체를 참조하지는 않기 때문에 최악의 경우로 가지는 않았다. 아마 입력값을 이쁘게 조절하면 그다지 길게 증가할 것 같지 않다.
가장 예쁜 값을 입력했는데 역시 시간이 덜 늘어난다.
원래는 문자열을 배열로 바꾸는 방법들의 속도도 비교할 예정이었는데, 풀이 방법이 바뀌어서 그럴 필요가 없어졌다.
공부하며 느낀 점
- 시간 복잡도는 중요하지만 절대적이지는 않다.
- 입력되는 값들이 얼마나 잘 정리되어 있느냐
- 시간 복잡도에 관여하는 변수가 여럿이고 하나만 변하는 경우에는 이라고 생각해도 될것이다.
- 반복문의 중첩수가 같더라도, 데이터를 처리하는 방식에 따라서 시간 복잡도에 따라 최악의로 늘어날수도 아닐수도있다.
- 문자열을 단순히 배열로 바꾸기만 할때에는
str.split("")이[...str],Array.from(str)보다 약 2.5배 빠르다. - 반복문의 사용이 단순히 1씩 순서대로 증가하거나, 특정 조건을 만족하기 전에는 무한 루프를 돌리는 방법만이 있는것이 아니다.
참조한 페이지
문자열을 배열로 바꾸기
[JavaScript]문자열을 배열로 변환하는 방법
