본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[백준 Baekjoon 알고리즘]2741번, 2742번 N찍기 문제(반복문 문제)

백준(BAEKJOON) 알고리즘 문제 풀기- 난이도: 하

오늘은 반복문을 이용한 알고리즘이라고 부르기 조차 민망한.. 문제를 풀게요

둘 다 똑같은 문제인데 위에서 아래로 출력하냐 아래에서 위로 출력하나 차이뿐이예요.

다만 여기서 우리가 주의해야할 입출력 상태에 대해서 중요한 개념이 나옵니다~! 아직 입출력 성능에 대해 잘 모르시는 분은 꼭 풀어보세요 

 

[2741] N찍기

----------------------------------------------------------------------------------------

문제: 자연수 N이 주어졌을 때, 1부터 N까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오

시간제한: 1초,  메모리 제한 128MB

입력: 첫째 줄에 100,000보다 작거나 같은 자연수 N이 주어진다.

출력: 첫째 줄부터 N번째 줄까지 차례대로 출력한다.

 

예시1

입력: 5

출력: 

1

2

3

4

5

 

[2742] 기찍N

 

----------------------------------------------------------------------------------------

문제: 자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오

시간제한: 1초,  메모리 제한 128MB

입력: 첫째 줄에 100,000보다 작거나 같은 자연수 N이 주어진다.

출력: 첫째 줄부터 N번째 줄까지 차례대로 출력한다.

 

예시1

입력: 5

출력: 

5

4

3

2

1

 

 

 

ANSWER

문제를 다 풀어보셨나요? 어려운 문제는 아니라서 쉽게 풀었는데 C++로 푸신 분들은 시간초과! 떠서 당황하신 분들이 있을거예요. for나 while등을 사용해 많은 양의 처리를 반복적으로 수행해야 할 경우에는 수행속도를 신경써주셔야 합니다. 

특히 입출력방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있습니다.

 

[C++언어]

문제: 2741번, 2742번 공통

#include <iostream>
int main()
{
    int n;
    std::cin>>n;
    //2741번일 때
    for(int i=1; i<=n; i++){
        std::cout<<i<<std::endl;
    }
    //2742번일 때
    for(int i=n; i>0; i--){
        std::cout<<i<<std::endl;
    }
    return 0;
}

시간초과!!!

어디가 문제였을까요? 

 

[C++ 통과]

#include <iostream>
int main()
{
    int n;
    std::cin>>n;
    for(int i=1; i<=n; i++){
        std::cout<<i<<'\n';
    }
    return 0;
}

메모리: 1984KB

시간: 12ms

코드 길이: 148B

 

웃긴게.. 이렇게 짜면 통과입니다 endl하나만 '\n'함수로 바꿨을 뿐인데..!! 심지어 시간 제한이 1초인데 개행 표현 바꾼 것만으로 12ms로 확 줄었어요. 즉 여기서 메인 문제는 cout을 썼기 때문이 아니라 개행 문자였던 것입니다.

 

 

사람들이 C가 먼저고 C++ cout은 추후에 나온 것이라고 생각해 cout이 더 느릴 것이라고 추측하는데 printf, scanf는 cout, cin보다 느립니다. (차이는 크지 않아요) 밑에 C 부문 코드를 보면 걸린 시간이 12m로 똑같은 것을 볼 수 있어요.

endl이 더 느린 이유는 단순 개행이 아니라 개행 후 출력 버퍼를 비워주는 역할을 추가로 하기 때문입니다. 이 작업은 매우 느려요.

☆☆☆ 즉 알고리즘에서 성능을 올리고자 한다면 endl대신 개행문자(\n)를 써주는 것이 훨씬 효율적입니다. ☆☆☆

 

도움이 됐다면!! 선물선물 ↓

 

 

 

 

 

[C++ 통과]

#include <iostream>
using namespace std;
int main()
{
    ios_base :: sync_with_stdio(false); cout.tie(NULL);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        cout<<i<<'\n';
    }
    return 0;
}

메모리: 1984KB

시간: 8ms

코드 길이: 217B

 

또 이런 반복적인 많은 입출력을 다뤄야 하는 상황에서 cin/cout을 사용하고자 하면 cin.tie(NULL), cout.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해주면 좋아요. 어떤 사람이 이를 측정한 결과를 블로그에 올렸는데 여기서 보면 cout에다가 \n을 사용하고 sync_with_stdio(false)를 해준 것이 가장 속도가 좋은 결과를 확인할 수 있어요.

(링크는 그림에 연동해놓을게요 참고하고 싶으신 분은 한 번 방문에서 읽어보세요. 영어라는게 함정...)

단 이렇게하면 더 이상 scanf / printf / puts /  getchar / putchar 등 C의 입출력 방식을 사용하면 안됩니다.

 

[C 통과!]

문제: 2741번

#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        printf("%d\n", i);
    }
    return 0;
}

메모리: 1116KB

시간: 12ms

코드 길이: 150B

 

[Java 통과!]

문제: 2741번, 2742번

import java.util.Scanner;
class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //2741번의 경우
        for(int i=1; i<=n; i++){
            System.out.println(i);
        }
        //2742번의 경우
        for(int i=n; i>0; i--){
            System.out.println(i);
        }
    }
}

메모리: 34012KB

시간: 680ms

코드 길이: 251B

 

통과는 아슬아슬하게 됐지만 시간이 너무 많이 걸리죠?

이 BufferedReader/BfferedWriter 포스팅에서 전에 배웠다싶이 출력이 반복적으로 많이 일어날 경우에는 Scanner보다 BufferedReader/BufferedWriter를 사용해주는 것이 훨씬 효율적입니다.

 

[Java 통과!]

문제: 2741번

import java.util.Scanner;
import java.io.*;
class Main{
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=1; i<=n; i++){
            bw.write(i+"\n");
        }
        bw.flush();
        bw.close();
    }
}

메모리: 28580KB

시간: 224ms

코드 길이: 411B

 

한 번 비교 정리해보기 좋은 문제였어요 

오늘은 여기까지입니다. 도움이 되셨다면 좋아요, 또는 광고보답은 어떠신가요?! 더 좋은 정보를 공유하는데 소소한 활력이 됩니다 :)