[코딩테스트] 프로그래머스 javascript 2단계 - 올바른 괄호,괄호 회전하기

올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

시간 초과 코드

 

채점 결과

정확성: 69.5

효율성: 0.0

합계: 69.5 / 100.0

function solution(s){
    const arr = s.split('')
    let stack = []
    for (let i=0;i<arr.length;i++){
        stack.push(arr[i])
        let len = stack.length
        if(stack.slice(len-2,len).join('')==='()'){
            stack.splice(-2)
        }
    }
    
    return stack.length ? false : true
    

}

 

 

배열을 사용해서 시간 초과가 나와 숫자를 세는 것으로 코드를 변경했다.

문제풀이

function solution(s){
    const arr =s.split('')
    let l = 0
    let r = 0
    for (let i=0;i<arr.length;i++){
        if (arr[i]==='('){
            l++;
        }
        if (arr[i]===')'){
            r++;
        }
        if (l<r) return false;
    }
    return l===r ? true : false
     
}

- 괄호의 개수를 세고 l<r 일 시 false

- 최종 개수가 같은지 확인한다.

 

참고로 변수 선언을 한 줄에 같이 하면 시간초과가 난다.

function solution(s){
   const arr = s.split('')
   let r = 0;  l =0
   
   for(let i=0;i<arr.length;i++){
       if(arr[i]==='(') {l++;}
       if(arr[i]===')') {r++;}
       if(l<r) {return false}
   }
    return l===r?true:false
}

따라서 변수 선언은 각각 해주는 것이 좋다.

이 문제는 아래 풀이처럼 스택으로 풀 수 있다.

 

 

 괄호 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

문제풀이

- 0. 문자열을 for문으로 substring을 이용해 바꾼다.

- 1. 스택을 생성해서 괄호를 넣는다.

- 2. 스택의 마지막이 ([{인지 확인하고 현재 괄호랑 매칭이 되는지 확인한다. 

- 3. 매칭이 되지 않으면 false로 변경한다.

 

이 문제는 stack을 이용해서 푸는 것이 알고리즘과 자료구조상 좋다.

또한 문자열의 길이가 홀수라면 항상 성립이 되지 않으므로 앞에서 적어두어야 한다.

 

 

function solution(s) {
    var answer = 0;
    let stack = [] 
    let test = true
    if (s.length%2) return 0
    for (let j =0; j<s.length;j++){
        test = true;
        
        let str = s.substring(j) + s.substring(0,j)
        for(let i =0; i<str.length;i++) {
            if(str[i]==="[" ||str[i]==="(" || str[i]==="{") {
                stack.push(str[i])
            }
            else {
                const left = stack.pop()
                if(left==="("&&str[i]===")") continue;
                if(left==="{"&&str[i]==="}") continue;
                if(left==="["&&str[i]==="]") continue;
                test = false;break;
            }
        }
        if(test) answer++
    }

     
     
    
    return answer;
}

 

 

햄버거 만들기

 

https://school.programmers.co.kr/learn/courses/30/lessons/133502

프로그래머스

문제 설명

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

 

시간 초과 코드

- 시간 초과 코드 (6개)

: 1231을 찾아 replace를 한다. 

- replace 메서드가 연산 시간이 많이 걸린다.

function solution(ingredient) {
    //1231
    var answer = 0;
    let burgur = '1231'
    let index = ingredient.indexOf(1)
    let str = ingredient.join('').substring(index)
    
    while (str.includes(burgur)) {
        answer++;
        str = str.replace(burgur,'')
    }
    
    return answer;
}

 

문제풀이

- 1. 스택을 생성해서 재료를 넣는다.

- 2. 스택의 마지막 4개가 1231일 경우 stack을 4개 잘라내고 count를 추가한다.

 

이 문제는 stack을 이용해서 푸는 것이 알고리즘과 자료구조상 좋다.

 

function solution(ingredient) {
    let stack = []
    let count  =0 ;
    for(let i=0;i<ingredient.length;i++){
        stack.push(ingredient[i])
        let index = stack.length-1
        if (stack[index] ===1 &&
            stack[index-1]===3 &&
            stack[index-2]===2 &&
            stack[index-3]===1) {
            count++;
            stack.splice(-4)
        }
    }
    
    return count 
    
}