Problem 문제풀이
오랜만에 하루 종일 한 문제만 붙잡고 풀었던 것같다. 결국 timer가 50,000,000보다 커지면
종료하는 방식으로 풀 수 있었는데 timer 없이도 문제를 풀 수 있었다면 얼마나 좋았을까하는
아쉬움이 남는 문제였다.
전략
-
초기화를 해준다. 삼성의 경우 여러 testcase를 풀며 변수들의 재사용을 강제한다. 따라서초기화가 중요하다. -
[와]는 모두 쌍을 이루고 있다. 이것을 이해 못해서 시간을 정말 많이 잡아먹었다.-
ex) [[]][][][] -> (0,3), (1,2), (4,5), (6,7), (8,9)
-
괄호하면 stack이 떠오를 정도로 이 둘은 아주 친밀한 관계이다.
아님 말구 -
Map을 이용해서 서로 연결해주자.
-
-
인터프리터를 구현하자.
-
주어진 명령어를 수행하며 무한루프를 체크한다.
가장 먼저 [과 ]의 쌍을 지어주자.
map과 stack을 사용해서 둘을 연결할 것이다.
stack<int>openPos;
map<int, int>connected;
cin >> sm >> sc >> si >> op >> str;
for (int i = 0; i < sc; i++)
{
if (op[i] == '[')
{
openPos.push(i);
}
else if (op[i] == ']')
{
int prev = openPos.top();
connected.insert({ prev,i });
connected.insert({ i,prev });
openPos.pop();
}
}
이제 인터프리터를 구현해보자. 명령어가 한 번 수행될 때마다 timer는 1씩 증가한다.
memory의 index를 가리키는 것을 memory_ptr
명령어의 index를 가리키는 것을 op_ptr
입력 문자열의 index를 가리키는 것을 str_ptr이라 하자.
op_ptr의 max값을 last_selected에 저장하자.
만약 무한루프에 빠지게 된다면 last_selected가 무한루프의 원인이 된 ]일 것이다.
while (op_ptr < sc && timer < 50000000)
{
if (op[op_ptr] == '+')
{
if (memory[memory_ptr] == 255)
{
memory[memory_ptr] = 0;
}
else
{
memory[memory_ptr]++;
}
}
else if (op[op_ptr] == '-')
{
if (memory[memory_ptr] == 0)
{
memory[memory_ptr] = 255;
}
else
{
memory[memory_ptr]--;
}
}
else if (op[op_ptr] == '<')
{
memory_ptr = (memory_ptr + sm - 1) % sm;
}
else if (op[op_ptr] == '>')
{
memory_ptr = (memory_ptr + 1) % sm;
}
else if (op[op_ptr] == '[')
{
if (memory[memory_ptr] == 0)
{
op_ptr = connected[op_ptr];
timer++;
continue;
}
}
else if (op[op_ptr] == ']')
{
if (memory[memory_ptr] != 0)
{
op_ptr = connected[op_ptr];
timer++;
continue;
}
}
else if (op[op_ptr] == ',')
{
if (str_ptr == si)
{
memory[memory_ptr] = 255;
}
else
{
memory[memory_ptr] = str[str_ptr++];
}
}
op_ptr++;
timer++;
if (last_selected < op_ptr)
{
last_selected = op_ptr;
}
}
while문을 빠져나오기 위해서는 둘 중 하나의 조건을 만족해야한다.
-
모든 명령을 수행하였다. (op_ptr>=sc)
-
timer가 50000000보다 커졌다. (Loop 존재)
if (op_ptr < sc)
{
cout << "Loops " << connected[last_selected] << ' ' << last_selected << '\n';
}
else
{
cout << "Terminates\n";
}
connected.clear();
다 사용한 map은 clear해주자. 혹~~~시 나중에 문제가 될 수도 있다
하루종일 이 문제밖에 못 푸니까 기운이 빠진다… ㅠ.ㅠ 전체 코드를 남기며 마무리한다.
#include <iostream>
#include <map>
#include <stack>
using namespace std;
int t, sm, sc, si;
unsigned char memory[100001];
string str, op;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--)
{
int timer = 0;
int memory_ptr = 0;
int op_ptr = 0;
int str_ptr = 0;
int last_selected = 0;
stack<int>openPos;
map<int, int>connected;
cin >> sm >> sc >> si >> op >> str;
for (int i = 0; i < sc; i++)
{
if (op[i] == '[')
{
openPos.push(i);
}
else if (op[i] == ']')
{
int prev = openPos.top();
connected.insert({ prev,i });
connected.insert({ i,prev });
openPos.pop();
}
}
for (int i = 0; i < sm; i++)
{
memory[i] = 0;
}
while (op_ptr < sc && timer < 50000000)
{
if (op[op_ptr] == '+')
{
if (memory[memory_ptr] == 255)
{
memory[memory_ptr] = 0;
}
else
{
memory[memory_ptr]++;
}
}
else if (op[op_ptr] == '-')
{
if (memory[memory_ptr] == 0)
{
memory[memory_ptr] = 255;
}
else
{
memory[memory_ptr]--;
}
}
else if (op[op_ptr] == '<')
{
memory_ptr = (memory_ptr + sm - 1) % sm;
}
else if (op[op_ptr] == '>')
{
memory_ptr = (memory_ptr + 1) % sm;
}
else if (op[op_ptr] == '[')
{
if (memory[memory_ptr] == 0)
{
op_ptr = connected[op_ptr];
timer++;
continue;
}
}
else if (op[op_ptr] == ']')
{
if (memory[memory_ptr] != 0)
{
op_ptr = connected[op_ptr];
timer++;
continue;
}
}
else if (op[op_ptr] == ',')
{
if (str_ptr == si)
{
memory[memory_ptr] = 255;
}
else
{
memory[memory_ptr] = str[str_ptr++];
}
}
op_ptr++;
timer++;
if (last_selected < op_ptr)
{
last_selected = op_ptr;
}
}
if (op_ptr < sc)
{
cout << "Loops " << connected[last_selected] << ' ' << last_selected << '\n';
}
else
{
cout << "Terminates\n";
}
connected.clear();
}
return 0;
}