프로그래밍 끄적끄적

이 문제를 풀때, 문자열을 다루는 것에 익숙하지 않아 코드 작성에 애를 먹었던 기억이 있습니다. 기본적으로 C언어나 C++을 공부하신 분들은 string클래스를 활용하시면 보다 편리하게 풀 수 있으실 겁니다. 일단 문장을 입력받아야 하기때문에 gets()함수를 이용해서 입력을 받았습니다. 그리고 문장에서 단어의 개수를 판단하는 기준은 보통 띄어쓰기를 기준으로 나누어져있기 때문에 그 기준을 이용하여 코드를 작성했습니다. 하지만 2번째 예제를 입력했을때 올바른 정답이 나오지 않았었는데, 2번째 예제를 자세히 보면 띄어쓰기로 시작을 하는 것을 볼 수 있습니다. 그 부분 때문에 단어 한개를 추가로 인식하는 오류가 발생해서 flag라는 변수를 추가했습니다.

flag함수를 활용해서 문장을 인식하는 방법은 제가 임베디드때 센서 활용을 할때 자주 쓰던 방법입니다. 운영체제 과목을 수강할 당시 Test And Set이라는 기법에서 응용한 것입니다. 즉 내가 원하는 상태일때를 알려주는 변수입니다. C++을 활용하기 때문에 bool type을 활용하여 내가 알고자 하는 상황을 감지할 수 있습니다. 쉽게말해서 이 문제의 경우 내가 지금 문장을 앞에서부터 한글자 한글자 읽어나가고 있을 때, 지금 읽고있는 글자가 알파벳인지 공백문자인지를 구별하기 위한 변수라고 생각하면 됩니다. 내가 지금 현재 읽고 있는 문자가 알파벳일 경우 flag는 true로 초기화 시켜주면, 코드 내에서 알파벳을 읽고 있을때 동작 특성을 정해줄 수 있습니다.

이렇게 flag함수를 넣어주게 되면 처음에 공백부터 시작하는 문자열이나 끝에 공백이 들어가는 문자열이 오더라도 정확하게 단어의 개수만 측정할 수 있도록 할 수 있습니다.

* Key Point

1. 문자열을 구분하려면 공백을 기준으로 구분한다.

2. 문자열 중 시작부분과 끝부분에 공백이 올때의 오류를 처리해야 한다.

3. 문자열에서 내가 읽고 있는 것이 알파벳인지 공백문자인지 구분해야 한다.

#include <iostream>
#include <stdio.h>

#define MAX 1000001     // 입력받을 수 있는 문자열의 최대 크기
using namespace std;

int main() {
	char str[MAX];      // 입력 받은 문자열을 저장하는 변수
	int index = 0;         // 배열을 탐색할 위치 변수
	int answer = 0;         // 단어의 개수
	bool flag = false;      // 띄어쓰기 구분을 위한 flag

	gets(str);      // 문자열을 입력

	while (str[index] != '\0') {
		if (str[index] != ' ')
			flag = true;        // 처음에 띄어쓰기로 시작한 부분때문에 문장이 시작한 것을 알기 위한 장치
		else if(str[index] == ' ' && flag ) {
			flag = false;
			answer++;
		}       // 띄어쓰기를 기준으로 단어의 개수를 세도록 설정
		index++;
	}
	if(flag)
		answer++;       // 띄어쓰기를 기준으로 했기 때문에 마지막 단어를 세기 위한 작업

	printf("%d\n", answer);

}

문제를 읽어보면 알겠지만 3x2k의 수만큼 별을 찍어내려간다고 합니다. 3, 6, 12... 이런식으로 내려가게 됩니다. 처음에는 기본적인 별찍기 문제와 동일하게 생각해서 해당 좌측에 공백문자를 출력한 후 별을 찍는 방식의 for문을 생각했었는데 도저히 규칙을 생각해낼 수가 없었습니다. 그래서 생각해낸 방법이 바로 공백의 문자를 가지고 있는 문자열을 생성하고 그 위에 입력받은 N의 값만큼 별모양을 찍어내면 되는 것 입니다.

그러려면 일단 아래와 같은 별 한 세트를 찍는 함수를 만들었습니다. 좌측에 보이는 별을 한세트로 봤습니다. 왜냐하면 가장 작은 수가 3줄을 찍어내는 것이기 때문입니다.

이제 두번째로 직면한 문제는 정확한 위치에 별을 찍는것이 문제인데, 이것은 시작점의 좌표만 정해주면 규칙적으로 찍어내면 됩니다. 이를 구현하기 위해서는 재귀호출함수를 활용해야하는데, 재귀 함수를 모르시는 분이 있을 수도 있어서 간략하게 설명하고 넘어가겠습니다.

* 재귀 호출 함수(Recursive call)

함수 안에서 함수 자기 자신을 호출하는 방식을 재귀 호출(Recursive call)이라고 합니다. 재귀 호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용하게 쓰입니다. 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다. 재귀 함수의 경우 하나의 함수가 끝나기 전에 본인 자신을 호출하기 때문에 스택(Stack)에 계속 함수를 호출하여 공간을 차지하게 됩니다. 그렇기 때문에 반드시 재귀 함수를 종료하는 시점을 만들어주는 구문이 필요합니다. 그렇지 않으면 제한된 메모리 용량을 초과해 스택 오버플로우(Stack overflow)현상이 발생하게 됩니다.

이 재귀 호출 함수를 활용하여 문제를 풀어보도록 하겠습니다. 가장 먼저 N이 늘어나는 규칙을 보면 2의 배수 씩 늘어나는 것을 볼 수 있습니다. 여기서 첫번째 3을 입력했을때 가장 위에 위치하는 별은 3번째에 찍히게 됩니다. 두번째 N인 6이 들어왔을 경우, 가장 최상단에 찍히는 별은 6번째 찍히게 됩니다. 그 다음줄에 찍히는 두개의 삼각형 별은 3번째와 8번째에 삼각형의 가장 위의 별이 찍히게 됩니다. 즉, 가장 위의 삼각형을 그리는 함수, 아래의 두개의 삼각형을 그리는 함수를 재귀 호출 함수를 활용하여 3개를 작성하면 됩니다. 여기서 종료 구문은 삼각형의 모양을 그리고 나서 함수를 종료하게 만들면 됩니다. 가장 작은 단위는 N이 3일때이므로 입력받은 N을 2씩 나눠가며 재귀 호출을 하면 됩니다. 삼각형이 추가되는 모형을 보면 N이 6일때는 3의 아래에 삼각형을 두개씩 추가하는 모습이고, 12일때는 6에 6을 아래에 두개 더 추가하는 모습입니다. 플로우 차트로 표현해보면 아래와 같은 모습이지 않을까 싶습니다. 재귀 호출 함수기때문에 직관적으로 표현하긴 어렵지만 대강 표현하게 된다면 저렇게 될 것입니다.

위의 플로우 차트만으로는 설명이 조금 부족하지만 이해를 돕기 위해서 첨부했습니다. 재귀 함수는 N의 값과 x좌표와 y좌표가 계속 업데이트 되면서 새로운 자기 자신 함수를 호출합니다.

재귀 호출 함수를 활용하여 풀이대로 진행을 하게 되면 문제가 원하는 결과 값을 얻을 수 있습니다. 마지막으로 코드와 실행 결과를 보고 포스팅을 마치도록 하겠습니다.

#include <iostream>
#include <memory.h>
char space[3072][6144];		// 별을 찍을 공간 생성 k값이 최대 10까지인 것을 고려하여 배열 크기 생성)

void star(int N, int x, int y) {
	if (N == 3) {
		space[y][x] = '*';
		space[y + 1][x - 1] = '*';
		space[y + 1][x + 1] = '*';
		space[y + 2][x - 2] = '*';
		space[y + 2][x - 1] = '*';
		space[y + 2][x] = '*';
		space[y + 2][x + 1] = '*';
		space[y + 2][x + 2] = '*';
		return;
	}		// 별 한세트를 찍는 구문
	
	star(N / 2, x, y);		// 벌의 윗부분을 찍는 재귀 호출
	star(N / 2,x - (N / 2), y + (N / 2));	// 별의 좌하단 삼각형을 찍는 재귀 호출
	star(N / 2, x + (N / 2), y + (N / 2));	// 별의 우하단 삼각형을 찍는 재귀 호출
}
int main() {
	int N;
	int i, j;

	scanf("%d", &N);

	memset(space, ' ', sizeof(space));		// for문보다 memset으로 배열을 초기화 해주면 시간을 단축 할 수 있다고 한다.

	star(N, N - 1, 0);		// 입력받은 N을 넣어 함수 실행

	for (i = 0; i < N; i++) {
		for (j = 0; j < N * 2; j++) {
			printf("%c", space[i][j]);
		}
		printf("\n");
	}			// 별이 그려진 배열 출력
}