여러 시행착오를 거치 문제.
결과적으로는 첫 번째로 짠 게 제일 잘 돌아가는 코드가 되었지만,
다음에 시도한 코드에 조금 나은 요소가 있어서 완전히 마무리하진 않았지만 모든 코드를 업로드.
문제
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.
각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
S = 3, E = 3인 경우 1은 팰린드롬이다.
S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.
출력
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
첫 번째 코드. 비트연산을 이용하여 결과를 저장했다. i부터 j까지가 팰린드롬인지를 array의 (i,j)component에 저장하는 것이 1차적 아이디어지만,
입력이 2000개라서 하나씩 저장하려니 부담이 커서 비트에 결과를 저정하기로 했다.
int 하나에 32bit( 4byte * 8bit) 이므로 2000개( 약 2048개)를 저장하기 위해서는 array size를 64로 잡으면 충분했다.
하지만 연산 과정에서 팰린드롬을 판단하는 과정을 조금 비효율적으로 짜긴 했지만, 적당한 메모리와 시간 내에서 채점은 통과
결과를 저장하는 방법은, 바깥쪽에서부터 팰린드롬을 판단하면서 안으로 들어오고, 팰린드롬이 되는 최대 영역을 따로 지정하여, 안쪽은 모두 되고, 안되기 시작하면 그 바깥은 모두 팰린드롬이 아님을 이용하여 결과를 저장. 이후 코드에서 사용한 방법이 더 직관적인 듯.
참고로 이후 코드에선 안에서 밖으로 나가면서 팰린드롬을 판단했다.
일단 첫 번째 코드는 아래.
#include <iostream>
#include<stdio.h>
int main()
{
std::ios::sync_with_stdio(false);
int length, from, to, from_max, to_max, cur_from, cur_to, m;
int inputs[2000];
int results[2000][64]; // restore results bit-wise: every integer has 32 bits that can restore 32 results
for (int i = 0; i < 2000; i++) {
for (int j = 0; j < 64; j++){
results[i][j]=0;
}
}
std::cin >> length;
for (int i = 0; i < length; i++) {
std::cin >> inputs[i];
}
from = 0;
for (to = length - 1; to > 0; to--) {
cur_from = from;
from_max = cur_from;
cur_to = to;
to_max = cur_to;
while (cur_from < cur_to) {
if (inputs[cur_from] != inputs[cur_to]) {
cur_from++;
cur_to--;
from_max = cur_from;
to_max = cur_to;
continue;
}
cur_from++;
cur_to--;
}
while (from_max <= to_max) {
results[from_max][to_max / 32] |= (1 << (to_max % 32));
from_max++;
to_max--;
}
}
to = length - 1;
for (from = length-1; from > 0; from--){
cur_from = from;
from_max = cur_from;
cur_to = to;
to_max = cur_to;
while (cur_from < cur_to) {
if (inputs[cur_from] != inputs[cur_to]) {
cur_from++;
cur_to--;
from_max = cur_from;
to_max = cur_to;
continue;
}
cur_from++;
cur_to--;
}
while (from_max <= to_max) {
results[from_max][to_max / 32] |= (1 << (to_max % 32));
from_max++;
to_max--;
}
}
results[0][0] |= 1;
std::cin >> m;
for (int i = 0; i < m; i++) {
std::cin >> from >> to;
if (results[from - 1][(to - 1) / 32] & (1 << ((to - 1) % 32))) {
//std::cout << '1' << '\n';
printf("%d\n", 1);
}
else {
//std::cout << '0' << '\n';
printf("%d\n", 0);
}
}
return 0;
}
추가 이슈: 입력이 1M개여서 출력하는데 그만큼 시간이 오래 걸렸다. std::cout으로는 시간을 맞출 수 없어서 stdio.h를 include하고 printf를 이용하여 print했더니 시간 내에 출력이 가능했다.
두 번째 코드.
비트연산을 사용하지 않고 그냥 2-dim array에 결과를 저장. 메모리 사용에 큰 차이가 있는건 아니었지만 컴파일하는 도중에 문제가 생겨 다른 메모리 동적 할당을 사용할 필요성이 생긴 코드.
#include<iostream>
#include<stdio.h>
int main() {
int n, m, from, to;
std::cin >> n;
int inputs[2000];
for (int i = 0; i < n; i++) {
std::cin >> inputs[i];
}
bool palind[2000][2000];
for (int i = 0; i < n; i++) {
palind[i][i] = 1;
for (int j = 1; i + j < n && i - j >= 0; j++) {
palind[i - j][i + j] = palind[i - j + 1][i + j - 1] * (inputs[i - j] == inputs[i + j]);
}
}
for (int i = 0; i + 1 < n; i++) {
palind[i][i + 1] = inputs[i] == inputs[i + 1];
for (int j = 1; i + j + 1 < n && i - j >=0; j++) {
palind[i - j][i + j + 1] = palind[i - j + 1][i + j] * (inputs[i - j] == inputs[i + j + 1]);
}
}
std::cin >> m;
for (int i = 0; i < m; i++) {
scanf("%d %d", &from, &to);
//std::cin >> from >> to;
printf("%d\n", palind[from - 1][to - 1]);
}
return 0;
}
컴파일은 되는데 이상한 리턴값을 뱉고 프로그램을 종료해 버리길래 찾다 보니 buffer overflow가 일어날 때 뱉는 리턴값이라고 한다.
가장 큰 변수가 bool palind[2000][2000]이어서 테스트만 하기 위해 [200][200]으로 바꾸어 테스트해 보니 잘 돌아가는 것을 보아
변수의 메모리가 너무 커서 unsafe(?)한 것이 문제인 듯. 메모리 동적 할당을 통해 해결해야 하는 듯 하다.
그러나 동적 할당을 하면 주소를 1dim array처럼 이용해야 할 것 같은데 2-dim-array-like사용을 위해서는 (i,j) compnent를
i*2000 +j 로의 접근으로 사용해야 할 듯 하다.
여담으로 online judge에서는 런타임 에러 없이 정답으로 채점되었다.
동적 할당을 이용한 마지막 코드.
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
int main() {
int n, m, from, to;
std::cin >> n;
int inputs[2000];
for (int i = 0; i < n; i++) {
std::cin >> inputs[i];
}
bool *palind = (bool*) malloc(2000*2000);
for (int i = 0; i < n; i++) {
*(palind + i*2000 + i) = true;
for (int j = 1; i + j < n && i - j >= 0; j++) {
*(palind + (i - j)*2000 + i + j) = *(palind + (i - j + 1)*2000 + i + j - 1) * (inputs[i - j] == inputs[i + j]);
}
}
for (int i = 0; i + 1 < n; i++) {
*(palind+ i*2000 + i + 1) = inputs[i] == inputs[i + 1];
for (int j = 1; i + j + 1 < n && i - j >=0; j++) {
*(palind + (i - j)*2000 + i + j + 1) = *(palind + (i - j + 1)*2000 + i + j) * (inputs[i - j] == inputs[i + j + 1]);
}
}
std::cin >> m;
for (int i = 0; i < m; i++) {
//scanf("%d %d", &from, &to);
std::cin >> from >> to;
printf("%d\n", *(palind + (from - 1)*2000 + to - 1));
}
free(palind);
return 0;
}