[BOJ / C++] 비밀 이메일 (문자열)

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

 

1. 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    string s;
    cin >> s;

    int n = s.size();

    int r = 1, c = s.size();
    
    for (int i = 1; i*i <= s.size(); i++) {
        if (n % i == 0 && i <= n/i) {
            r = i;
            c = n/i;
        }
    }

    vector<vector<char>> board(r, vector<char>(c));
    int idx = 0;
    for (int j = 0; j < c; j++) {
        for (int i = 0; i < r; i++) {
            board[i][j] = s[idx];
            idx++; 
        }
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << board[i][j];
        }
    }
}

 

 

2. 시간복잡도

보드에 문자열을 넣는 것이 가장 오래걸리는데 O(rc)이다. n = 100이므로 O(rc) = 50 * 50 = 2,500 <= 10^8 이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

r, c를 찾아내는 것이 가장 핵심이다. (r<=c && r*c ==n)을 만족시켜야한다.

 

i * i <= n까지 돌면서 n%i == 0 && i <= n/i 인 것을 찾으면 된다. n%i==0이어야 r이 될 수 있고, n/i가 c가 될 값이기 때문이다.