[백준] 1022-소용돌이 예쁘게 출력하기(C++)

문제링크: https://www.acmicpc.net/problem/1022

1022번: 소용돌이 예쁘게 출력하기

 

구현문제였습니다.  회오리 모양으로 값이 증가하기에 구현하기 조금 까다로운 문제였습니다.

 

직관적으로 구현할때 흔히 할 수 있는 실수는 

 

1. 10001 * 10001 의 배열을 만들고 값들을 모두 저장한 후 결과를 도출하는 것입니다.

 

당연히 메모리 초과입니다.. 

 

2. 두번째 저지를 수 있는 실수는 재귀함수로 구현하는 것입니다.  5000번의 재귀가 호출하며 함수 호출과 매개변수 생성 등으로 시간초과를 가지게 됩니다. 

 

 

 

우선 정답 코드를 먼저 보여드리겠습니다. 

직관적이기 떄문에 쉽게 이해하실 수 있을거라고 생각합니다. 

#include <iostream>
#include <algorithm> // max 함수 사용
#include <cmath> // abs 함수 사용
using namespace std;

int r1, c1, r2, c2;
int map[50][5] = { 0 };
void solve() {
	int MAX = max(max(abs(r1), abs(c1)), max(abs(r2), abs(c2))); // max값을 찾는다.
	int val = 1; //소용돌이에서 값
	if (0 >= r1 && 0 >= c1 && 0 <= r2 && 0 <= c2)
		map[0 - r1][0 - c1] = val;

	int cnt = 0; // 현재의 카운트를 측정
	int y = 0, x = 0; // 좌표를 나타냄

	for (int i = 1; i <= MAX + 1; i++) {

		for (int i = 1; i <= 1 + cnt * 2; i++) {
			val++;
			x++;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}
		for (int i = 1; i <= 1 + cnt * 2; i++) {
			val++;
			y--;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}
		for (int i = 1; i <= 2 + cnt * 2; i++) {
			val++;
			x--;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}
		for (int i = 1; i <= 2 + cnt * 2; i++) {
			val++;
			y++;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}

		cnt++;
	}



}

int main() {
	cin >> r1 >> c1 >> r2 >> c2;
	solve();

	int h = abs(r2 - r1);
	int w = abs(c2 - c1);

	int MAX = 0;
	
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			MAX = max(MAX, map[i][j]);
		}
	}
	
	//int MAX = max(max(map[0][0], map[0][w - 1]), max(map[h - 1][0], map[h - 1][w - 1])  ); // max값을 찾는다.
	int max_degree = 0;
	for (int i = 1; i <= MAX; i *= 10) {
		max_degree++;
	}
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			int current_degree = 0;
			for (int k = 1; k <= map[i][j]; k *= 10)
				current_degree++;
			for (int k = current_degree; k < max_degree; k++)
				cout << ' ';

			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}

}

solve함수에서 회오리로 이동하는 값들을 계산하면 반복문을 실행하고, 만약 (r1,c1)과 (r2,c2) 값 사이에 있다면 배열에 저장합니다.

 

그 이후에는 반복문을 통해 최대값의 자릿수를  max_degree에 저장하고 모든 값의 자릿수를 max_degree에 맞춰 적절히 공백을 넣어주면 됩니다. 

 

막상 짜고나면 간단해보이지만 코딩할 때는 어려운게 정석인 문제...

 

 

좀 더 효율적인 방법이 많을거 같아서 코드를 찾아봤습니다.

 

#include<cstdio>
int a[50][50], r1, c1, r2, c2, m, s;
int main() {
	scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
	for (int i = r1; i <= r2; i++) {
		for (int j = c1; j <= c2; j++) {
			int x = i - r1, y = j - c1;
			if (i - j < 0) {
				if (i + j < 0) a[x][y] = 4 * i*i + i + 1 - j;
				else a[x][y] = 4 * j*j - 3 * j + 1 - i;
			}
			else {
				if (i + j < 0) a[x][y] = 4 * j*j - j + 1 + i;
				else a[x][y] = 4 * i*i + 3 * i + 1 + j;
			}
			if (a[x][y] > m) m = a[x][y];
		}
	}
	for (; m; m /= 10) s++;
	for (int i = 0; i <= r2 - r1; i++) {
		for (int j = 0; j <= c2 - c1; j++) printf("%*d ", s, a[i][j]);
		puts("");
	}
	return 0;
}

 

너무 간결하게 예쁜코드네요.

애초에 회오리가 규칙있게 값이 증가하기에 경우마다 값을 계산해서 O(200)만에 해결한 방법입니다. 

 

저렇게 짤 수 있으면 정말 잘하시는거겠지만 좋은 코드의 조건을 여러가지가 있을 수 있습니다.

어떤 사람에게는 직관적이고 이해하기 쉬운 코드일수도, 다른 사람에게는 짧고 시간이 짧게 드는 것일 수도 있습니다.

사람마다 기준이 다르기에 어떤게 옳다고 볼 수는 없습니다. 

 

꼭 직접 보지않고 구현해보세요. 구현문제의 핵심은 연습입니다.

 

화이팅 :)