[백준/c++] 11728 - 배열 합치기

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

11728번: 배열 합치기

---

1) 풀이

주어지는 배열 모두 정렬되어 있기 때문에, 각 배열의 맨 앞 원소를 대소 비교해서 최종 배열에 넣으면 된다.

 

문제를 푸는 다양한 방식이 있겠지만 난 이 문제를 보자마자 문제에 쓰이는 모든 배열을

큐(queue)로 만들어야겠다고 생각했다. 

각 배열의 front를 비교하고 더 작은 요소를 정답 배열에 넣고 pop 하면

다음 차례에도 front로 비교하면 돼서 인덱스를 신경쓸 필요가 없기 때문이다!

인덱스가 넘어가는지 안 넘어가는지 신경쓰기란 매우 피곤한 일...😂

 

그 다음으로 주어진 배열 두개의 원소가 모두 정답 배열에 들어갈 때까지

맨 앞 원소를 비교하고 정답 배열에 넣으면 된다. (이후 pop까지)

나는 이 전체과정을 while 문으로 처리했는데.

while (첫번째 배열이 비어있지 않다면 || 두번째 배열이 비어있지 않다면)

이런 식의 코드로 작성해놓으면 어느 배열이 먼저 끝나더라도 반복문을 계속 진행할 수 있다.

 

그리고, 한 배열이 먼저 비는 경우의 처리를 반복문 내부에 적어주면 된다.

비지 않은 배열을 모두 정답배열에 차례로 넣어주는 것이다.

두 배열이 모두 정답 배열에 들어가서 두 배열 모두 비는 경우에는

자동적으로 반복문이 끝나기 때문에 그 부분은 고려해줄 필요없다.

 

이렇게 줄글로 풀어서 적어놓으니까 

코드가 잘 연상되지 않는데,

아래의 코드를 보면서 보면 이해가 쉽지 않을까 싶다.

 

 

애초에 바킹독님의 강의를 들으면서 풀게 된 문제라

바킹독님의 코드와도 비교해보았는데 애초에 사용한 자료구조부터 달라서

꽤 많은 부분이 차이가 났지만 구현에만 차이가 있을 뿐,

결론적으로는 같은 원리로 돌아가는 것 같았다!

 

다만, 짜고나니 뭔가... 더 효율적이고 더더 깔끔한 코드를 작성할 수 있을 것 같은데

이 코드밖에는 생각이 안 나서 좀 아쉬울 뿐... 그래두 처음 푸는 것치고이정도면 꽤 선빵했다고 생각하기로 한다 😂

 

바킹독님의 코드는 제일 하단 참고자료 링크에서 확인할 수 있다.

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int n, m; 
int t;
queue<int>a; //n크기의 첫번째 배열
queue<int>b; //m크기의 두번째 배열
queue<int>ans; //최종 정답 배열
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	while (n--){
		cin >> t;
		a.push(t);
	}
	while(m--) {
		cin >> t;
		b.push(t);
	}
	while (!a.empty()||!b.empty()) { //두개 모두 비어야 반복문 종료
		if (a.empty()) { //반복문이 진행됐다는 것은 a만 빈다는 의미
			while (!b.empty()) {
				ans.push(b.front()); //비지 않은 배열 b를 모두 정답에 넣고 반복문 종료
				b.pop();
			}
			break;
		}
		else if (b.empty()) {//반복문이 진행됐다는 것은 b만 빈다는 의미
			while (!a.empty()) {//비지 않은 배열 a를 모두 정답에 넣고 반복문 종료
				ans.push(a.front());
				a.pop();
			}
			break;
		}
		else {
			if (a.front() <= b.front()) { 
				ans.push(a.front());
				a.pop();
			}
			else { //a>b
				ans.push(b.front());
				b.pop();
			}
			
		}

	}
	while(!ans.empty()) {
		cout << ans.front() << " ";
		ans.pop();
	}
}

3) 참고자료

blog.encrypted.gg/955?category=773649