Zvimbalius
면접 대비시간 제한1초메모리 제한1024 MB
네 방향 명령으로 이루어진 길이 N의 문자열에서 드론이 출발점으로 돌아오도록 바꿔야 하는 명령의 최소 개수를 구하고, 불가능하면 NEGALIMA를 출력합니다.
문제
Vytis에게 새 장난감이 있다. 원격으로 조종하는 무인 비행기로, 드론 또는 zvimbalius라고도 부른다. 드론은 무인 헬리콥터이며 받은 명령에 따라 날아간다.
Vytis의 드론은 네 가지 명령 S, P, R, V를 이해한다. 각각 드론을 북쪽, 남쪽, 동쪽, 서쪽으로 1미터 날게 한다.
Vytis는 장난감을 시험하려고 명령 N개를 입력했다. 입력을 마치고 보니 드론이 모든 명령을 수행한 뒤 시작점으로 돌아오지 못할 수도 있었다. 명령을 고치는 일은 쉽지 않다. 드론 소프트웨어는 이미 입력한 명령을 추가하거나 삭제하지 못하고, 명령은 하나씩만 바꿀 수 있다. Vytis는 모든 명령을 수행한 뒤 드론이 시작점으로 돌아오도록 가능한 한 적은 수의 명령을 바꾸려 한다.
드론이 시작점으로 돌아오려면 바꿔야 하는 명령의 최소 개수를 구하시오.
입력
첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄에는 공백 없이 이어 붙인 N개의 명령 문자열 k1k2...kN이 주어진다. ki는 i번째 명령이며, 위에서 설명한 문자 중 하나이다.
출력
드론이 시작점으로 돌아오도록 바꿔야 하는 명령의 최소 개수를 정수 하나로 출력한다.
명령을 어떻게 바꿔도 드론이 시작점으로 돌아올 수 없으면 NEGALIMA를 출력한다.
제한
1 ≤ N ≤ 100 000