문제

https://algospot.com/judge/problem/read/ZEROONE

풀이

그냥 문제대로 구현하면 푸는 문제인줄 알고 풀었다가 엄청 많이 틀렸다. 문자열의 최대 길이가 L이라했을때 별 다른 방법 없이 코드를 작성하면 전체 수행시간이 $O(NL)$이라 시간 초과가 나게 된다. 그러므로 수행 시간의 상한을 $O(N * lg(L))$ 정도라 생각하고 풀어야 한다.

수열의 값은 0과 1밖에 없고 최대값과 최소값이 같다는 뜻은 해당 구간 i,j의 모든 원소가 같다는 뜻이므로 구간마다 그룹을 나누어 배열에 저장하면 전체 수행 시간을 $O(N)$으로 줄일 수 있다.

예를들어 수열 000110010가 있다 할때 그룹화하여 000112234로 저장한뒤 그룹 배열의 i와 j번째 값이 같은지만 비교해주면 되기 때문이다.

#include <stdio.h>
int main() {
	int t,i,j,tmp;
	int diff[1000001]={0};
	char s[1000001];
	scanf("%s",s);
	for(i=1;s[i]!='\0';i++){
		diff[i] = diff[i-1];
		if(s[i-1] != s[i]) diff[i]++;
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&i,&j);
		printf("%s\n",diff[i] == diff[j]?"Yes":"No");
	}
	return 0;
}

문제

https://www.acmicpc.net/problem/9358

풀이

주어진 수열의 첫번째 수와 N번째 수를 더해 새 수열에 넣고, 두번째 수와 N-1번째 수를 더해 다시 새 수열에 넣고.. 이 작업을 수열의 길이가 2가 될 때까지 반복한 후 왼쪽 수가 큰지 오른쪽 수가 큰지 비교하는 문제이다.

이 문제는 양방향 큐, 즉 Deque(Double Ended Queue, [덱])를 사용하면 쉽게 풀수 있다. 새 수열을 만드는 과정에서 왼쪽 수(front)와 오른쪽 수(back)를 쉽게 큐에서 꺼낼수(pop) 있어 전체적인 코드가 짧아지고 구현이 간편해진다.

#include <cstdio>
#include <deque>
using namespace std;

int main() {
	int t,i,j,x,n;
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d",&n);
		deque<int> dq;
		for(j=0;j<n;j++){
			scanf("%d",&x);
			dq.push_back(x);
		}
		while(1){
			if(dq.size() == 2) break;
			deque<int> cur;
			while(!dq.empty()){
				cur.push_back(dq.front()+dq.back());
				dq.pop_front();
				if(!dq.empty()) dq.pop_back();
			}
			while(!cur.empty()){
				dq.push_back(cur.front());
				cur.pop_front();
			}
		}
		printf("Case #%d: %s\n",i,dq[0]>dq[1]?"Alice":"Bob");
	}
	return 0;
}

문제

https://algospot.com/judge/problem/read/HAMMINGCODE

풀이

단순한 구현문제. 입력이 7자리의 바이너리이므로 char로 받은뒤 int 배열에 넣고 xor을 사용해 syndrome 값을 구했다.

#include <stdio.h>
int main(void) {
	int t;
	scanf("%d",&t);
	while(t--){
		int i, syn = 0,encoded[8];
		char c;
		for(i=1;i<=7;i++){
			scanf(" %c",&c);
			encoded[i] = c-'0';
		}
		syn += ((encoded[1] ^ encoded[3]) ^ encoded[5]) ^ encoded[7];
		syn += 2 * (((encoded[2] ^ encoded[3]) ^ encoded[6]) ^ encoded[7]);
		syn += 4 * (((encoded[4] ^ encoded[5]) ^ encoded[6]) ^ encoded[7]);
		encoded[syn] ^= 1;
		printf("%d%d%d%d\n",encoded[3],encoded[5],encoded[6],encoded[7]);
		
	}
	return 0;
}