[백준] 10871번 : X보다 작은 수 - [C++]

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

10871번: X보다 작은 수

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

그리 어렵지 않은 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

반복문 카테고리의 마지막 문제다. 이쯤오면 아마 대부분 반복문 사용 방법은 익히셨을 것이다.

그래서 이 문제는 크게 설명할 것이 없다.

 

N개의 수를 입력을 받은 뒤, 해당 수들 중에서 X보다 작은 수들을 출력해주면 되는 문제다.

 

크게 풀이방법은 2 가지가 있는데, 먼저 배열을 사용하여 풀이하는 방법과 입력과 동시에 if 조건절을 통해 출력해주는 방식이 있다.

 

 

 

간단하게 코드로 보자면 다음과 같다.

 

int main() {

	int N;
	int X;
	cin >> N >> X;	// N과 X 입력

	int arr[10000];	// 최대 가질 수 있는 N은 10000이므로, 10000칸의 배열 생성

	for(int i = 0; i < N; i++) {
		cin >> arr[i];		// 배열에 N개의 수를 저장
	}

	for(int i = 0; i < N; i++) {
		// i번째 원소가 X보다 작다면 출력
		if(arr[i] < X) {
			cout << arr[i] << " ";
		}
	}
}

 

 

 

위와 같이 풀이하는게 가장 직관적일 것이다.

 

만약 배열을 사용하지 않고 입력과 동시에 출력 조건이 맞을 경우 출력하는 방법으로 풀이한다면 다음과 같이 할 수도 있다.

 

int main() {

	int N;
	int X;
	cin >> N >> X;	// N과 X 입력

	int val;
	for(int i = 0; i < N; i++) {
		// 입력을 받은 값이 X보다 작을 경우 출력
		cin >> val;
		if(val < X) {
			cout << val;
		}
	}

}

 

위와 같이 풀이할 수도 있다.

 

위 첫 번째 방식은 2N 번 순회해야하는 방면, 두 번째 방식은 N번 순회를 하기 때문에 좀 더 효율적인 측면이 있다.

 

 

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

 

위에서 설명한 두 가지 방식과 더불어 좀더 향상된 입출력 방식을 같이 다루고자 한다.

 

 

1. 배열 + 기본 입출력

2. 비 배열 + 기본 입출력

3. 비 배열 + 향상 된 입출력

 

 

 

 

---

• 풀이

- 방법 1 : [배열 + 기본 입출력]

 

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	int N, X;
	cin >> N >> X;

	int arr[10000];	// 최대 가질 수 있는 N은 10000이므로, 10000칸의 배열 생성

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	// i번째 원소가 X보다 작으면 출력
	for (int i = 0; i < N; i++) {
		if (arr[i] < X) {
			cout << arr[i] << " ";	// 출력 형식 주의 (원소간 공백이 있음)
		}
	}
	return 0;
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

크게 어려운 것도 없고...  다만 출력 형식만 주의해서 출력 할 원소 사이에 공백을 반드시 출력해주도록 하자.

 

 

 

---

- 방법 2 : [비 배열 + 기본 입출력]

 

 

 

 

앞서 설명했던 두 번째 방법이다. 

 

 

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	int N, X;
	cin >> N >> X;

	int val;
	for (int i = 0; i < N; i++) {
		cin >> val;
		// 입력을 받은 값이 X보다 작을 경우 출력
		if (val < X) {
			cout << val << " ";
		}
	}

	return 0;
}

 

 

 

 

 

 

 

---

- 방법 3 : [비 배열 + 향상 된 입출력]

 

 

 

 

앞서 말했듯, C와 C++의 표준 입출력 동기화를 끊어주는 방법이다.

 

이 번 풀이 방법은 입력과 출력이 번갈아가며 사용되므로 입출력 묶음을 풀어주도록 하자.

 

이 부분에 대해 잘 모른다면 다음 글을 참고하시길 바란다.

st-lab.tistory.com/232

[백준] 15552번 : 빠른 A+B - [C++]

 

 

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {

	ios_base::sync_with_stdio(false);	// 동기화 해제
	cin.tie(NULL);	// 묶음 해제

	int N, X;
	cin >> N >> X;

	int val;
	for (int i = 0; i < N; i++) {
		cin >> val;
		if (val < X) {
			cout << val << " ";
		}
	}

	return 0;
}

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 29768735  -  방법 3 : 비 배열 + 향상 된 입출력

채점 번호 : 29768730  -  방법 2 : 비 배열 + 기본 입출력

채점 번호 : 29768725  -  방법 1 : 배열 + 기본 입출력

 

 

 

 

위 결과를 보면 두 번째 방식의 결우 시간이 갑자기 뻥튀기되는 것을 확인할 수 있다. (솔직히 이정도까지 차이날 거라고는 생각 못했다..) 아무래도 두 번째, 세 번째 코드의 경우 입출력이 번갈아가면서 진행되기 때문에 tie 되어있는 코드의 경우 스트림에서 입출력이 발생하기 전에 계속 스트림을 flush 하기 때문에 결과적으로 매 번 flush 되면서 416ms 라는 결과가 나온 것으로 보인다. (스트림을 비우는 작업은 생각보다 큰 비용을 치룬다.) 

반면에 세 번째 코드는 untie 시켰기 때문에 마지막에만 스트림을 flush 시킴으로 인해 결과적으로 한 번에 모든 출력이 이루어짐으로 시간이 단축되는 것을 볼 수 있는 것이다.

 

 

 

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다.

 

알고리즘의 기초적인 부분인 만큼 반복문의 형식에 익숙해져야 할 필요가 있다. 그만큼 많이 풀어보고 다른 비슷한 문제들도 같이 풀어보시는 것을 권장드린다.

혹여 어렵거나 모르는 부분이 있다면 언제든 댓글 남겨주시길 바란다.