백준 10799문제 - 쇠막대기

• 문제

 

 

• 접근방법

처음엔 입력값으로 막대와 레이져 모양을 문자열로 받고 레이져가 나올 경우의 나누어지는 막대값을 세아리면 된다.

레이져가 나올때 마다 막대의 개수가 각각 다를 수 있기때문에 현재의 막대 개수를 순차적으로 삽입 삭제가 유용한 스택을 사용하면 되겠다고 생각했다.

 

 

• 논리 흐름(알고리즘)

처음에는 입력값을 문자열로 받고 이를 스택에 저장하면서 ')' 가 나오면 레이져일테니까 스택에 저장되어있는 '(' 수를 더해주면 되겠다고 생각했으나, ')' 가 나올때 레이져일 경우와 막대일 경우로 2가지로 나누어진다고 깨달았다.

만약 ')' 가 등장했을 때 레이져일 경우 '(' 가 저장되어있는 수를 결과값에 더해주고

')'가 등장했을 때 막대가 끊기면서 결과값에 +1을 더해준다. 이 때 막대 안에는 무조건 레이져가 하나 이상 포함되기 때문에 다른 예외처리는 생각 안해도 된다. 그림으로 표현하자면 다음과 같다.

레이져인지 막대인지 구별하기 위한 스택(is_laser)을 만들고 여기에는 현재의 모양을 그대로 유지하기 때문에 삽입연산만 필요하다. 

문자열 하나씩 저장해주고 '('가 등장했을 때 이 스택의 top이 '('이면 '()'이기 때문에 레이져, ')' 이면 '))' 이기 때문에 막대임을 구별할 수 있다.

 

위의 스택을 이용해 만약 레이져가 등장했을 때 '('의 개수만큼 레이져가 막대를 자르기 때문에 레이져의 '('를 제외(pop)한 '('의 개수를 저장하는 스택(cur_shape)을 만들었다. 

만약 레이져가 아닌 막대일 경우에는 최소 막대 안에 1개 이상의 레이져가 존재하기 때문에 막대가 끝나면서 꽁지가 하나 잘리기 때문에 결과값에 +1을 해준다.

 

 

 

• 배운점

문제를 접하고 활용할 자료구조를 먼저 생각하니 논리의 흐름과 자료구조의 활용이 딱딱 떨어지면서 어렵지 않게 풀 수 있었다.

이를통해 다시한번 자료구조의 중요성을 느꼈고 이번 스터디를 통해 자료구조의 개념을 완벽하게 정리하고 문제를 보고 자유자제로 접근방법을 떠올릴 수 있도록 공부하는것이 목표가 되었다.