문자열 내 마음대로 정렬하기
올바른 괄호

공부하며 느낀 점
참조한 페이지

문자열 내 마음대로 정렬하기

sort를 쓰는 방법과 새로운 배열에 기존값들을 넣는 방법이 있을 것같다.

나의 풀이

function solution0(strings, n) {
    strings.sort((s1,s2) => {
        if (s1[n] === s2[n]){
            return s1.localeCompare(s2);
        }
        return s1[n].localeCompare(s2[n])
    });
    
    return strings;
}

n번째 글자로 sort하고 같은 경우에는 localeCompare로 사전순으로 정렬한다.

다른 사람의 풀이

function solution1(strings, n) {
    return strings.sort().sort((a,b) => a.charCodeAt(n)-b.charCodeAt(n));
}

localeCompare라는 메서드를 몰라서 이렇게 두번 했따고 하는데 속도가 더 빨랐다고한다.

function solution2(strings, n) {
    var answer = [];
    for (var i = 0; i < strings.length; i++) {
        var chu = strings[i][n];
        strings[i] = chu + strings[i];
    }
    strings.sort();
    for (var j = 0; j < strings.length; j++) {
        strings[j] = strings[j].replace(strings[j][0],"");
        answer.push(strings[j])
    }

    return answer;
}

내가 처음 생각한것과 비슷한 방법이다.
다만 내가 생각했던 방법은 배열을 이중으로 쓰는것이고 이것은 문자열을 넣는방식으로 이 방식이 더 깔끔한것같다.

속도 비교

위와 같은 조건으로 1천만회 반복하였다.

sol1 > sol0 >> sol2 순이었다.

시간복잡도를 보면 sol0,1은 sort()를 사용하므로 $O(n \log n)$의 시간복잡도를 가진다.

sol2는 $O(n)+O(n)+O(n \log n) = O(n \log n)$의 복잡도로 큰 차이가 없어야 할것같은데 실제로는 sol2가 압도적으로 느리다.

아마 replace()때문에 속도가 느려지는 걸지도 모르겠다.

올바른 괄호

1. )로 시작하면 false
2. 마지막 ) 이후에 (가 나오면 이전까지의 갯수를 비교해서 다르면 false

나의 풀이

function sol0(s){

    const countParenthesis = [];
    let count = 0

    // if (s[0] === ')') {
    //     return false
    // }


    for (let i = 0 ; i < s.length ; i++){
        const parenthesis = s[i]

        if (parenthesis === '('){
            countParenthesis.push('(')
            count ++;
        } else if (parenthesis === ')') {
            if (countParenthesis.pop() !== '('){
                return false
            }
            count --;
        }
    }  

    if (count !== 0 ){
            return false
        }

    return true;
}

원래는 주석처리 된 부분이 살아있었다.
그런데 이게 살아 있으면 너무 느리다고 불합격 처리를 내놓았다 대체 왜일까?... s가 매우 긴 문자열인 경우에 s[0] 을 찾는 시도가 for문을 돌리는것보다 느린걸까? 하지만 for문의 안에는 s[i]를 찾는다는 더 시간이 많이 걸릴 수 밖에 없는 행동이 들어가 있다.
추가 : 다음날 다시해보니 예외 코드가 있어도 잘 굴러간다. 서버 상태가 안좋았던걸까?

아마 내가 만든 예외 처리 코드가 여러개의 문자열이 주어질때는 효율적이지만 하나의 긴 문자열이 주어질때는 비효율적인것같다.

다른 사람의 풀이

function sol1(s){
    let cum = 0
    for (let paren of s) {
        cum += paren === '('? 1: -1
        if(cum < 0) {
            return false
        }
    }
    return cum === 0? true: false;
}

내가 한 예외처리 조차 필요 없는 방식이다. 굳이 괄호를 하나하나 기억할 필요도 없다.
이거 비슷하게 하려다가 왠지 안될것같아서 시도도 안했는데 해보기나 할걸 그랬다.

function sol2(s){
  var result = s.match(/(\(|\))/g);
  return result[0] == '(' && result.length % 2 == 0 ? true : false
}

내가 처음 -+를 해서 해결하려다가 그만 둔 이유를 보여주는 해법이다. 짝이 맞느냐 아니냐만 확인해서 문제가 발생할 수 있다.

아래는 정규식의 해석

/ : 정규식 시작
/g : 정규식 끝 + 전역 설정

그냥 괄호다

\( : ( 괄호표시
| : or 의 의미
\) : ) 괄호표시

속도 비교

위는 랜덤한 값을 하나 만들어서 1천만회 반복했을 때의 시간

이번 것은 랜던함 값들의 배열을 만든 후 1천만회 반복햇을 때의 시간이다.

내가 만든 예외 처리 if문은 같은 값을 여러번 반복하든 여러개의 값을 주든 차이가 없었다.

공부하며 느낀 점

1. 시간 복잡도는 가장 스케일이 큰 것을 기준으로 하는 줄알았는데 꼭 그렇게만 보는것도 아닌 것같다.
2. 예외처리를 한다고 무조건 빨라지는 것이 아니다.
   최소한 내가 해본 방법 내에서는 큰 차이가 없었다.

참조한 페이지

시간 복잡도
Javascript Array.sort의 시간복잡도
sort() 함수는 왜 시간복잡도가 nlogn인가요?
Algorithms: How do I sum O(n) and O(nlog(n)) together?