[백준 / C++] 11365번 - !밀비 급일

문제 링크

11365번: !밀비 급일

문제

문제 해석

입력받는 문장을 뒤집어 출력하는 문제이다.

---

코드

#include <cstdio>
#include <cstring>

int main(void) {
    
    char password[502]; //암호 500자 + 개행문자 \n + 널문자 \0 = 502칸
    
    while (1) {
        fgets(password, sizeof password, stdin);
        if (password[0] == 'E' && password[1] == 'N' && password[2] == 'D') break;

        password[strlen(password) - 1] = '\0';

        for (int i = strlen(password) - 1; i >= 0; i--) {
            printf("%c", password[i]);
        }

        printf("\n");
    }

    return 0;
}

---

문제 풀이

입력받을 char형 변수를 만든다.

이 변수는 입력받는 문장의 최대 길이 500자 + fgets로 입력받을 때 들어오는 개행문자 1자 + 널 문자 1자로

총 502의 크기를 갖는다.

입력받은 문장을 뒤집어 출력하고자 strlen() 함수를 사용해 변수의 마지막 인덱스에 접근한다.

그래서 마지막 인덱스부터 0번째 인덱스까지 반복문을 통해 출력해준다.

---

알고 있으면 좋은 것

위 코드에서는 반복문의 초기화식을 strlen() 함수로 저장해주었다. 하지만 이렇게 하면

strlen() 함수가 값을 구하는 데에 시간을 n만큼, 또 반복문을 도는 데에 n만큼 써서 n * n

즉, 반복문 내에서 n^2 만큼 시간이 쓰인다. (시간 복잡도 O(n^2))

이를 방지하고자 strlen()의 값을 반복문 바깥에서 미리 저장해준 뒤, 그 값을 반복문으로 가져오는 게

더 빠르다. (시간 복잡도 O(n))

char password[502];
fgets(password, sizeof password, stdin);

int len = strlen(password);

/* 시간 복잡도를 n^2에서 n으로 줄일 수 있다 */
for (int i = len - 1; i >= 0; i--) {
    printf("%c", password[i]);
}