[BOJ] 백준 1022. 소용돌이 예쁘게 출력하기

▶문제설명

[BOJ] 1022. 소용돌이 예쁘게 출력하기

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

▶Hint

---

시뮬레이션 & 구현 문제이다.

소용돌이 전체를 배열에 저장하지 않고 필요한 부분만 저장해야 한다는 점과 

숫자의 길이가 맞지 않으면 공백을 추가해서 예쁘게 출력해야 한다는 점이 핵심이다.

소용돌이 전체를 배열에 저장하려면 10001x10001 크기의 int형 2차원 배열이 필요한데, 문제의 메모리 제한이 128mb이므로MLE(Memory Limit Exceeded)가 발생한다.

출력해야 할 소용돌이의 숫자 중에서 가장 큰 숫자를 찾고 그 숫자의 길이에 맞춰서 

길이가 짧은 숫자의 경우 공백을 추가하여 가장 큰 숫자의 길이와 맞게 '예쁘게' 출력해주면 된다.

▶시간 복잡도

---

소용돌이 전체를 만드는 데 10001*10001 = 100,020,001 번의 연산이 필요하다.

소용돌이를 만들면서 필요한 부분을 저장한다.

가장 큰 수를 구하기 위해 O(50*5 = 250)의 시간이 걸리고 가장 큰 수의 길이를 L이라고 했을 때,

(1 <= r1-r+1 <= 50)

(1 <= c1-c+1 <= 5)

예쁘게 출력하기 위해 모든 수의 길이를 확인해야 하므로 O((r1-1+1) * (c1-c+1) * L) 의 시간이 걸린다.

▶Solution