처음 문제를 봤을 때는 2중 for문을 사용해야 한다고 생각했었다. 그런데 역시 코딩을 배운 입장에서 역시 최적화가 필요하며, 어떻게든 시간 복잡도를 줄여야하지 않을까 고민을 하게되었다. 아무래도 for문을 2중으로 쓰면 O(n^2)이 되버릴테니 당연히 시간적인 측면에서 문제가 발생할 것이라 판단하고 for문을 한번만 쓰고도 해결할 방법을 짜내려 노력했다.
나의풀이
int n = int.Parse(Console.ReadLine());
for(int i = 1; i <= n ; i++){
Console.Write(new string(' ', n - i));
Console.Write(new string('*', i));
Console.Write("\n");
}
for문을 한번쓰기 위해서 생각한 방법은 console.Write를 중복사용하는 것 이었다. 아무래도 익숙한 Console.WriteLine()에 생각이 고정되어 있어 이전에 있었던 별찍기 - 1의 다른사람 풀이에서 영감을 받았다.
new string을 이용해 원하는 만큼의 ' '공백과 *을 찍는다면 한번의 반복문 만으로도 풀이가 가능했다.
하지만 이상하게 생각되는건 거의 모든 문제가 O(n)의 시간복잡도를 가지고 있었다면 대부분 소요시간이 50~58ms 구간에 있었는데 반해, 이번 풀이의 시간은 72ms 로 20센트 이상 더 소요시간의 증가가 있었다. 왜? 같은 시간복잡도를 가지고 있으며, 예제의 입력값의 최대값으 100밖에 안되는데 이렇게 오래걸일 수 있나? 싶어 2중 for문을 이용해서 다시풀어보았다.
int n = int.Parse(Console.ReadLine());
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j <= (n - i)) Console.Write(" ");
else Console.Write("*");
}
Console.WriteLine();
}
결과는 첫번째 문제와 어마어마한 시간차이를 보여주었다. 거의 0.5초에 달하는 시간적 소모가 발생했다. 역시 2중for문은 되도록 사용해서는 안될 것 같다는 것을 새삼 느꼈다.
다른사람 풀이
int T=int.Parse(Console.ReadLine());
for(int i=1;i<=T;i++)
Console.WriteLine(new String(' ',T-i)+new string('*',i));
8ms의 속도차이가 나는 풀이를 보았지만, 매커니즘은 크게 다르지 않았다. 의문점은 앞의 String은 왜 대문자 S를 사용했는가? 어떻게 정상동작했는가가 의문이었을 뿐, 한줄의 WriteLine()안에 직접 연산식을 작성하여 결과를 쓰면 좀 더 깔끔하게 코드를 작성할 수 있는 것 같아 좋았다.
