[알고리즘] 백준 알고리즘 2743 단어 길이 재기

안녕하세요 감자 코딩& 감자 개발자 입니다. 이번에 살펴볼 문제는 2743번의 알고리즘 문제인 단어길이 문제 입니다.

상당히 쉬운문제라서 포스팅을 하지 않으려고 했으나, 시간복잡도면에서 한번더 생각해볼 수 있었던 문제여서 포스팅 하겠습니다.

---

문제 링크

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

문제

알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 영어 소문자와 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 최대 100이다.

출력

첫째 줄에 입력으로 주어진 단어의 길이를 출력한다.

예제 입력 1 

pulljima

예제 출력 1 

8

---

어떠신가요? 문제는 너무 쉽지요? 그래서 포스팅을 하지않으려고 했습니다. 하지만! 쉬울수록 한번더 생각해보아야 할것같았습니다.

---

문제 해결 방법

1) C언어에 대해서 많이 해보신분들은 쉽게 해결하실문제인데요 보통은 strlen()함수를 사용하시거나 string을 사용하실경우 size(), length()로 충분하게 푸실 수 있는 문제입니다

하지만 ! 코딩테스트에서 string을 사용하되, size() ,length()함수를 사용하지 마세요. 라는 조건이 달려있다면 어떻게 처리 하실껀가요. 그래서 사이즈 함수를 쓸수없을때 사용할 수 있는 코드를 알려드리려고 합니다.

    // type 2 - string,size,length를 사용못하고 고전적인 방법으로 구하는방법 (코딩테스트의 경우 제한이 걸려있을 수 있음)

    int len = 0;

    for (int i=0; str[i]; i++) {

        len += 1;

    }

    

이런식으로 코드를 작성하게되면, size함수를 굳이 구현하지않아도 길이를 구할 수 있게됩니다

2) 또, strlen()함수를 사용하여 길이를 구할 경우에 여러분들은 시간복잡도에 대해서 알아보셨나요? 저는 시간복잡도를 생각조차 하지않고, 그대로 사용하였는데 잘못된 생각이였습니다. strlen() 함수 자체가 O(N)이라는 복잡도를 갖고 있기때문에 대부분의 경우에서는 for문에 조건을 strlen(str)까지로 잡고 사용하시는분들이 있을겁니다.

  상관은 없겠지만, 절대적으로 알고리즘을 풀때 이런것도 생각하는 연습을 계속해야된다고 생각합니다. 이렇게 사용하였을 경우에는 시간복잡도가 어떻게 될까요?

네, 맞습니다. O(N^2)이 되겠지요?

왜 그렇게 된다고 생각하셨나요? for문에서 현재 N까지의 복잡도를 잡고있고, strlen()의 함수를 사용하면서 O(N^2)의 복잡도를 갖게됩니다. 따라서, strlen()함수를 for문 내부에서 사용하는것이 아니라, 그밖에서 미리 변수에 넣어놓고 사용을 해야겠지요?

시간복잡도라고 하는것은 한 코드에서의 1억번 수행되는데에 있어서 1초가 수행되는 시간으로 생각하시면 됩니다. 전체코드상의 시간복잡도로 잡고 생각을 해야합니다.

다른 말들은 생략하고 전체적인 코드로 보여드리겠습니다.

---

코드리뷰 

//

//  2743(단어길이재기).cpp

//  beakjoon_algorithm

//

//  Created by kgh on 21/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

#include <stdio.h>

#include <string>

#include <iostream>

using namespace std;

int main(void){

    

    // type 1 - 기본적인 문자열 길이 구하는 방법

    string str;

    cin >> str;

    cout << str.size();

    

    // type 2 - string,size,length를 사용못하고 고전적인 방법으로 구하는방법 (코딩테스트의 경우 제한이 걸려있을 수 있음)

    int len = 0;

    for (int i=0; str[i]; i++) {

        len += 1;

    }

    

    // type 3 - strlen의 시간복잡도는 O(N)이기 때문에, for문과 함께 쓰이면 O(N^2)의 복잡도가 나오게 됩니다.

    for (int i=0; i<strlen(str); i++) {

    }

    // type 3 의 해결방법 -  len의 변수에 strlen을 사용해서 미리 담아 놓으면 전체적인 시간복잡도는 O(N)을 유지 할 수 있습니다.

    int len = strlen(str);

    for (int i=0; i<len; i++) {

    }

    

    return 0;

    

}

---

자세한 사항은 코드 리뷰에 자세하게 적어놓았으니 참고하시면 될것같습니다. 쉬운것 같으면서도 복잡도에 대해 한번더 생각해볼 수 있었던 2743번 문제였습니다.

이상, 감자 코딩 & 감자개발자 문제 풀이 및 코드 리뷰를 마치겠습니다. 감사합니다 : )