스택 - 프로그래머스 쇠막대기

그림과 같이 쇠막대기와 레이저(점선)이 주어질 때, 잘린 쇠막대기 조각의 총 개수를 구하는 문제이다.

 

문제를 보자마자 드는 생각 -> 모든 막대기에 대해 몇 개의 레이저가 발사되는지 세어서 총 몇 조각이 되는지 합한다.

 

결과 -> 정답은 맞았지만 시간 복잡도에서 통과하지못함. 모든 막대기의 시작과 끝 인덱스를 저장하는데 O(n) + 모든 막대기들의 시작과 끝 인덱스 사이에 레이저가 있는지 확인하는데 O(nlogn) 시간이 걸린다. (n은 입력된 문자열의 길이)

 

스택을 이용한 풀이법 -> 문자열을 순회하며 막대기의 시작점인 경우 스택에 추가하고 레이저인 경우 스택의 원소 만큼 쇠막대기 조각의 수를 더한다. 쇠막대기의 끝점인 경우 쇠막대기 조각에 +1을 한다.

 

결과 -> O(n)시간에 코드 실행.