[백준OJ] 20114번 미아 노트

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

20114번: 미아 노트

---

 

풀이

예제입력 1번을 예시로 들어보겠다.

3 2 2
a?????
???bcc

여기서 총 3글자가 옆으로 2글자씩, 아래로 2글자씩 번졌다는 의미가 된다.

 

따라서 아래 그림과 같은 의미가 된다.

처음만나는 2*2 배열(빨간색) 은 첫번째 글자가 번진 구역이다. 따라서 처음만나는 2*2배열에서 ?가 아닌 글자를 만난다면, 그것이 첫번째 글자이다. 여기선 'a'가 된다.

 

다음으로 만나는 2*2배열(파란색)은 두번째 글자가 번진 구역이다. 따라서 파란구역에서 ?가 아닌 글자를 만난다면, 그것이 두번째 글자이다. 여기선 'b'가 된다.

 

마지막으로 검은색구역은 세번째 글자가 번진 구역이다. 따라서 검은 구역에서 ?가 아닌 글자를 만난다면, 그것이 세번째 글자이다. 여기선 'c'가 된다.

 

그럼 일반화를 해보자. 입력을 받을때, 높이는 h로 모두가 한글자가 번진것이므로, 구역을 나눌때 가로 인덱스를 슬라이싱하면된다.

 

현재 가로 인덱스가 i라고 하고, 가로로 번진 글자의 개수를 w라고 한다면, 현재 인덱스는 몇번째 글자가 번진것인지 확인하기 위해서 i/w를 해주면 된다. 이때 처음 문자열을 모두 ?로 초기화 해준뒤, 그 구역에서 만나는 문자로 해당 문자를 바꾸어주면된다.

 

시간복잡도

입력을 받으며 모든 문제를 해결할 수 있으므로, O(NHW)가 된다.

 

코드

#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n, h, w;
char maze[1000][1000];
char result[100];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> h >> w;
	memset(result, '?', sizeof(result));
	for (int i = 0; i <h; i++) {
		for (int j = 0; j < n*w; j++) {
			cin >> maze[i][j];

			int rindex = j / w;
			if (maze[i][j] != '?') {
				result[rindex] = maze[i][j];
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << result[i];
	}


	return 0;
}