BOJ 1022

29 Jan 2020 • ProblemSolving

소용돌이 예쁘게 출력하기

문제출처

1.설계(20)

  • 문제 해석

    • 중심좌표(0,0)를 기준으로 반시계방향으로 돌면서 숫자를 채운 후, (r1,c1) ~ (r2,c2) 좌표의 숫자들을 출력하는 문제입니다.
    • 숫자들을 출력할 때, 각 끝자리 수가 알맞게 정렬되도록 출력해야 합니다.
    • -5000 <= r1,c1,r2,c2 <= 5000, 0 <= r2-r1 <= 49, 0 <= c2 - c1 <= 4

  • 설계

    • 첫번째로 그리는 방법을 생각해야 합니다. dir배열을 주어 (오른쪽,위), (왼쪽,아래) 방향일때, 해당 방향으로 len길이만큼 숫자를 채워나갑니다. 방향이 두번 변화할 때마다 len을 늘려주면 됩니다.
    • 처음에는 10000^2 공간배열을 만들어 숫자를 채우려고 하였으나, 메모리 제한이 걸려서 원하는 숫자범위만 저장하도록 하였습니다.
    • 두번째로 출력을 할 때, 출력범위에서 가장 큰 숫자를 찾아야 합니다. 그리기를 할 때, 만약 숫자범위에 들어가면 최대 숫자 길이를 갱신 하도록 하였습니다.
    • 각 숫자에 대해서 (최대 숫자 길이-숫자 길이)만큼 공간을 더 주고 출력하면 됩니다.

2.구현(40)

  • 코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define OFFSET 5000

vector<string> map;
int len = 1;
int cnt = 0;
int r1, c1, r2, c2;
int dx[] = { 0,-1,0,1 };
int dy[] = { 1,0,-1,0 };
int max_num = 0;
bool is_range1(int x, int y) {
	if (x < r1 || y < c1 || x > r2 || y > c2) return false;
	return true;
}
void make(vector<vector<string> > & map) {

	int x = OFFSET;
	int y = OFFSET;
	int nx = x;
	int ny = y;
	int dir = 0;
	int dir_cnt = 0;
	int num = 2;
	int total_cnt = (r2 - r1 + 1) * (c2 - c1 + 1);
	while (cnt < total_cnt) {
		
		for (int i = 0; i < len; i++) {
			nx += dx[dir];
			ny += dy[dir];
			if (is_range1(nx, ny)) {
				map[nx - r1][ny - c1] = to_string(num);
				cnt++;
				int tmp_len = map[nx-r1][ny - c1].length();
				if (max_num < tmp_len) max_num = tmp_len;
			}
			num++;
		}
		dir = (dir + 1) % 4;
		dir_cnt++;
		if (dir_cnt == 2) {
			dir_cnt = 0;
			len++;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> r1 >> c1 >> r2 >> c2;
	r1 += OFFSET;
	c1 += OFFSET;
	r2 += OFFSET;
	c2 += OFFSET;
	vector<vector<string> > map(r2 - r1 + 1, vector<string>(c2 - c1 + 1));
	if (is_range1(OFFSET, OFFSET)) {
		map[OFFSET - r1][OFFSET - c1] = to_string(1);
		cnt++;
		int tmp_len = map[OFFSET - r1][OFFSET - c1].length();
		if (max_num < tmp_len) max_num = tmp_len;
	}
	make(map);
	
	for (int i = 0; i < r2 - r1 + 1; i++) {
		for (int j = 0; j < c2 - c1 + 1; j++) {
			int num = max_num - map[i][j].length();
			while (num > 0) {
				cout << " ";
				num--;
			}
			cout << map[i][j] <<" ";
			
		}
		cout << "\n";
	}
	return 0;
}

  • 디버깅

    • 숫자 길이를 찾기 쉽도록 string형 vector를 이용하였습니다.

  • 제출결과

136ms

3.마무리

  • 제가 구현한 방법은 최악의 경우에 시간복잡도가 O(1억)이므로 실행시간이 그리 빠르지 않았습니다.
    다른 분들의 코드를 참조해보니 해당 숫자를 바로 찾을 수 있는 수식으로 계산하여 순차적으로 그리지 않아도 되었습니다.
    그러나, 이 방법을 이용하면 문제의 목적인 구현을 연습할 수 없습니다.
    최적화도 좋지만 주먹구구식이긴 하여도 구현을 해보는 것도 나쁘지 않다고 생각합니다.
 BOJ

Related Posts