주어지는 명령어를 수행했을 때 정상적으로 종료되는지, 무한 루프에 빠지는지 출력하는 문제입니다.
구현 문제입니다.
문제에 있는 그대로 구현해 주시면 되는데 제일 중요한 괄호를 신경 써서 구현해 주시면 됩니다.
괄호 명령어를 하게 되면 다른 괄호로 이동하기 때문에 연결된 괄호를 서로 이어주는 작업을 해야 합니다.
스택을 이용하여 괄호를 연결해 줬는데 여는 괄호는 스택에 push 해주고 닫는 괄호가 나오면 스택 탑에 있는 인덱스를 꺼내서 서로 연결해 주었습니다.
idx[인덱스] = 괄호 명령어 적용 시 연결된 괄호 인덱스
닫는 괄호가 나올 때 스택을 이용하여 idx[닫는 괄호 인덱스] = 여는 괄호 인덱스, idx[여는 괄호 인덱스] = 닫는 괄호 인덱스 를 저장해 주면 됩니다.
이제 명령어를 차례대로 실행하면서 처리를 해주시면 됩니다.
5000만번의 연산 안에 끝나면 “Terminates”, 5000만번이 넘어가게 되면 무한 루프 처리를 해주시고 무한 루프가 도는 괄호를 출력하시면 됩니다.
무한 루프가 도는 괄호를 구하는 방법은 명령어를 실행하면서 닫는 괄호 인덱스의 최댓값을 저장해 주시면 됩니다. 닫는 괄호 다음 명령어로 한 번이라도 가지 못했으면 앞으로 되돌아가고 있다는 것이고 그 안에서 무한 루프가 돌고 있다는 것입니다. 그래서 괄호 인덱스 최댓값을 저장하고 그에 맞는 괄호 인덱스를 출력해 주시면 됩니다.
재채점이 되었길래 문제를 다시 읽어봤는데 9달만에 문제를 잘못 본 것을 깨닫고 다시 풀었습니다.
프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.
5000만번의 연산 후에도 종료가 되지 않았다면 해당 무한 루프는 한 번 실행이 완료되었습니다. 이미 무한 루프 안으로 들어온 상태인데 무한 루프의 최대 명령어 수는 5000만이므로 한번 더 5000만번 연산을 하며 포인터 인덱스의 최솟값이 무한 루프의 왼쪽 괄호이므로 무한 루프 쌍을 구할 수 있습니다.
문제를 보자마자 구현하기 정말 싫어서 조금 미루다가 풀었습니다 ㅎㅎ…
구현 문제도 난이도 있는 걸 많이 풀어봐야겠네요!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define MAX 50000000
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int n, m, k;
cin >> n >> m >> k;
string a, b;
cin >> a >> b;
int idx[4100], arr[100005] = {};
stack <int> st;
FOR(i, 0, m - 1) {
if (a[i] == '[') st.push(i);
if (a[i] == ']') {
idx[i] = st.top();
idx[st.top()] = i;
st.pop();
}
}
int p = 0, c = 0, cnt = 0, chk = 1e9, flag = 0;
FOR(i, 0, m - 1) {
if (a[i] == '-') arr[p] = (arr[p] + 255) % 256;
else if (a[i] == '+') arr[p] = (arr[p] + 1) % 256;
else if (a[i] == '<') p = (p - 1 + n) % n;
else if (a[i] == '>') p = (p + 1) % n;
else if (a[i] == '[' && !arr[p]) i = idx[i];
else if (a[i] == ']' && arr[p]) i = idx[i];
else if (a[i] == ',') arr[p] = (c == k ? 255 : (int)b[c++]);
if (cnt > MAX) chk = min(chk, i);
if (cnt > MAX * 2) flag = 1;
if (++cnt && flag) {
cout << "Loops " << chk << ' ' << idx[chk] << '\n';
break;
}
}
if (!flag) cout << "Terminates\n";
}
return 0;
}