[프로그래머스 Level 1] 직사각형 별찍기 (C++ - 2가지)

programmers.co.kr/learn/courses/30/lessons/12969

코딩테스트 연습 - 직사각형 별찍기

직사각형 별찍기 문제

구현 방법 1

이 문제를 보면 대부분의 사람들은 2중 for문을 생각할 것입니다.

 

보통의 경우 다음과 같이 풀 것입니다.

 

높이만큼 반복하며, 내부에서 너비만큼 반복하여 별을 찍어줍니다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a;
    int b;
    cin >> a >> b;

    for(int i=0;i<b;i++) {
        for(int j=0;j<a;j++) {
            cout << "*";
        }
        cout << endl;
    }
    return 0;
}

이런 풀이는 2중 for문을 사용하기 때문에 O(N^2)의 시간 복잡도를 가지게 됩니다.

 

구현 방법 2

2중 for문 없이 구현하는 방법에 대해 소개하겠습니다.

• String의 append() 함수를 사용해 입력받은 너비만큼 *으로 구성된 문자열을 만들어 줍니다.
• for문을 통해 입력받은 높이만큼 해당 문자열을 출력해줍니다.

위 내용은 아래 소스코드처럼 구현해 주었습니다.

 

소스코드 2

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a;
    int b;
    cin >> a >> b;
	
    string s="";
    //a 갯수만큼 * 더해주기
    s.append(a,'*');
    
    for(int i =0;i<b;i++) {
        cout << s << endl;
    }
    return 0;
}

이는 시간 복잡도가 O(N)인 풀이입니다.