[알고리즘] #쇠막대기

출처 : https://programmers.co.kr/learn/courses/30/lessons/42585

알고리즘 연습 - 쇠막대기 | 프로그래머스

 

문제 설명

여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다.

- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다. - 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

아래 그림은 위 조건을 만족하는 예를 보여줍니다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향입니다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있습니다.

(a) 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현합니다. 또한 모든 '()'는 반드시 레이저를 표현합니다. (b) 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현됩니다.

위 예의 괄호 표현은 그림 위에 주어져 있습니다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘리는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘리고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘립니다.

쇠막대기와 레이저의 배치를 표현한 문자열 arrangement가 매개변수로 주어질 때, 잘린 쇠막대기 조각의 총 개수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• arrangement의 길이는 최대 100,000입니다.
• arrangement의 여는 괄호와 닫는 괄호는 항상 쌍을 이룹니다.

입출력 예

arrangementreturn

()(((()())(())()))(())

17

입출력 예 설명

문제에 나온 예와 같습니다.

 

 

 

 

---

#최초 풀이

이 문제는 보자마자 stack을 이용해서 풀어야겠다고 생각했다.

 

1. String으로 받은 문자열을 Character Array로 변환한다.

2. 위 Character Array의 Index를 저장하는 Stack<Integer>를 생성한다.

3. 변환한 Array를 for문을 돌면서, '('일 때와 ')'를 나눠서 분기처리한다.

3-1. '('인 경우

-> stack에 push.

3-2. ')'인 경우

-> stack에서 pop. 이 때, pop한 값과 현재 index의 차이가 1이면 레이저이고 아니면 막대기이다.

4. 막대기 사이에 있는 레이저 갯수를 구한 뒤, 그 값에 1을 더한 값을 answer에 더해준다.

-> answer += '막대 사이에 있는 레이저 갯수' + 1;

 

 

소스코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

class Solution {
    public int solution(String arrangement) {
        if(arrangement == null || arrangement.equals("")) {
        	return 0;
        }
        
        // convert string to character array
        char[] charArr = arrangement.toCharArray();

        List<HashMap> arrList = new ArrayList<>();		// 쇠막대 idx 리스트 
        List<Integer> laserList = new ArrayList<>();	// 레이저인 idx 리스트(시작 idx만 저장)
        Stack<Integer> stack = new Stack<Integer>();	// 레이저인지 쇠막대인지 구분하기 위한 stack
        
        for(int i=0; i<charArr.length; i++) {
        	if(charArr[i] == '(') {
        		stack.push(i);
        	} else {
        		int startIdx = stack.pop();
        		if(i - startIdx == 1) {					//레이저인 경우 
        			laserList.add(i);
        		} else {								// 막대인 경우 
        			HashMap<String, Object> item = new HashMap();
        			item.put("startIdx", startIdx);
        			item.put("endIdx", i);
        			arrList.add(item);
        		}
        	}
        }
        
        int answer = 0;
        for(int i=0; i<arrList.size(); i++) {
        	// 막대 사이 레이저 갯수 구하기 
        	int startIdx = Integer.parseInt(arrList.get(i).get("startIdx").toString());
        	int endIdx = Integer.parseInt(arrList.get(i).get("endIdx").toString());
        	int cnt = 0;
        	
        	for(int j=0; j<laserList.size(); j++) {
        		if(laserList.get(j) > startIdx && laserList.get(j) < endIdx) {
        			cnt++;
        		}
        	}
        	
        	if(cnt > 0) {
        		answer += cnt+1;
        	}
        }
        return answer;
    }
}

테스트는 모두 통과했지만, 소요시간 무엇..?

코드를 다시 보니까 굳이 for문을 2번 돌릴 필요가 없었다. 게다가 두 번째 for문은 이중 for문...

 

 

---

#불필요한 코드를 없애고 수정한 두 번째 풀이.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
class Solution {
    public int solution(String arrangement) {
        if(arrangement == null || arrangement.equals("")) {
        	return 0;
        }
        
        // convert string to character array
        char[] charArr = arrangement.toCharArray();
        List<Integer> laserList = new ArrayList<>();	// 레이저인 idx 리스트(시작 idx만 저장)
        Stack<Integer> stack = new Stack<Integer>();	// 레이저인지 쇠막대인지 구분하기 위한 stack
        
        int answer = 0;
        for(int i=0; i<charArr.length; i++) {
        	if(charArr[i] == '(') {
        		stack.push(i);
        	} else {
        		int startIdx = stack.pop();
        		if(i - startIdx == 1) {	//레이저인 경우 
        			laserList.add(i);
        		} else {	// 막대인 경우 
        			int cnt=0;
        			for(int j=0; j<laserList.size(); j++) {
                		if(laserList.get(j) > startIdx && laserList.get(j) < i) {
                			cnt++;
                		}
                	}
                	if(cnt > 0) {
                		answer += cnt+1;
                	}
        		}
        	}
        }
        return answer;
    }
}

정확성 테스트

테스트 1 〉	통과 (888.03ms, 50.5MB)
테스트 2 〉	통과 (1.70ms, 45MB)
테스트 3 〉	통과 (711.92ms, 48.3MB)
테스트 4 〉	통과 (19.04ms, 45.8MB)
테스트 5 〉	통과 (32.94ms, 48.9MB)
테스트 6 〉	통과 (33.13ms, 45.9MB)
테스트 7 〉	통과 (349.22ms, 47.5MB)
테스트 8 〉	통과 (313.14ms, 50.9MB)
테스트 9 〉	통과 (434.75ms, 47.2MB)
테스트 10 〉	통과 (359.16ms, 47.6MB)
테스트 11 〉	통과 (251.82ms, 49.2MB)
테스트 12 〉	통과 (221.28ms, 47.6MB)
테스트 13 〉	통과 (278.03ms, 50.8MB)
테스트 14 〉	통과 (469.46ms, 47.9MB)
테스트 15 〉	통과 (534.82ms, 47.6MB)
테스트 16 〉	통과 (622.50ms, 47.8MB)
테스트 17 〉	통과 (783.94ms, 50.6MB)
테스트 18 〉	통과 (831.95ms, 47.9MB)
테스트 19 〉	통과 (805.84ms, 48MB)
테스트 20 〉	통과 (827.97ms, 51.6MB)

 

확실히 전보다 소요시간이 절반 이상으로 줄었다.

시간 제한을 두고 풀다보니까 문제를 푸는 거에 급급해서 효율성을 제대로 고려하지 못했던 것 같다.

계속 연습하다보면 처음 풀 때 고려하게 되겠지?

 

 

 

+ JavaScript 풀이

function solution(arrangement) {
    // convert string to character array
    let charArr = [];
    charArr = arrangement.split('');
    
    let stack = [];
    let laserList = [];
    let answer = 0;
    for(let i=0; i<charArr.length; i++) {
        if(charArr[i] == '(') {
            stack.push(i);
        } else {
            let startIdx = stack.pop();
            if(i - startIdx == 1) {	//레이저인 경우 
                laserList.push(i);
            } else {	// 막대인 경우         			
                let cnt=0;
                for(let j=0; j<laserList.length; j++) {
                    if(laserList[j] > startIdx && laserList[j] < i) {
                        cnt++;
                    }
                }
                if(cnt > 0) {
                    answer += cnt+1;
                }
            }
        }
    }
    return answer;
}