글 읽기 - logn으로 구현한거 같은데 왜 시간초과가 나오는지 모르겠습니다.

kysu5095 3년 전 0

set자료구조를 사용하여 해당열에 벽이나 돌들의 위치(행)을 저장해 주었습니다.

함수로 열(x)의 정보가 들어오면 해당 열의 set을 확인하여 돌을 떨구던가 좌우로 옮겨주었습니다.

이때 upper_bound를 사용하여 현재 행보다 아래있으면서(값이 크면서) 가장 가까운 값을 찾아주었는데

이 작업이 logn이 걸려서 저는 제 알고리즘이 logn이라고 생각했습니다.

해당열에 돌이나 벽이 30만개를 거의 다 채워도 금방 돌의 위치를 알 수 있다고 생각하는데

시간초과가 나버리네요ㅠ 어떤 문제점이 있는건가요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>

using namespace std;

int r, c;
char arr[30001][31];
set<int> s[31];


void print() {
	for (int i = 0; i < r; i++)
		cout << arr[i] << '\n';
}

void throw_stone(int x) {
	int cur_y = 0, y = 0;
	set<int>::iterator iter;
	while (true) {
		// 해당 열이 비어있다면 가장 아래에 돌 추가
		if (s[x].empty()) {
			arr[r - 1][x] = 'O';
			s[x].insert(r - 1);
			break;
		}
		// 현재 행에서부터 아래로 가장 가까이 있는 돌이나 벽 찾기
		iter = s[x].upper_bound(y);
		// 만약 아래로 돌이나 벽이 없다면 가장 아래에 돌 추가
		if (iter == s[x].end()) {
			arr[r - 1][x] = 'O';
			s[x].insert(r - 1);
			break;
		}
		y = *iter;
		// 해당 행이 벽이라면 그 위에 돌 고정
		if (arr[y][x] == 'X') {
			arr[y - 1][x] = 'O';
			s[x].insert(y - 1);
			break;
		}
		// 왼쪽칸과 왼쪽아래칸이 비어있다면 왼쪽열로 이동
		if (x > 0 && arr[y - 1][x - 1] == '.' && arr[y][x - 1] == '.') {
			x--;
			continue;
		}
		// 오른쪽칸과 오른쪽아래칸이 비어있다면 오른쪽열로 이동
		if (x < c - 1 && arr[y - 1][x + 1] == '.' && arr[y][x + 1] == '.') {
			x++;
			continue;
		}
		// 위 두 경우가 아니라면 돌 고정
		arr[y - 1][x] = 'O';
		s[x].insert(y - 1);
		break;
	}
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	freopen("kamen.in.8", "r", stdin);
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> arr[i];
		for (int j = 0; j < c; j++)
			if (arr[i][j] == 'X')
				s[j].insert(i);
	}
	int t, col;
	cin >> t;
	while (t--) {
		cin >> col;
		throw_stone(col - 1);
	}
	print();
	return 0;
}

sait2000 3년 전 0

while 문의 도는 횟수를 보장할 수가 없습니다. 아래처럼 계단(?)이 좌우로 왔다갔다 하는 모양이면 while문이 총 R^2번 쯤 도는 데이터가 생길 겁니다

in:
15 4
....
....
X...
.X..
..X.
....
....
...X
..X.
.X..
....
....
X...
.X..
..X.
10
1
1
1
1
1
1
1
1
1
1

out:
....
O...
XO..
.XO.
..X.
....
...O
..OX
.OX.
.X..
....
O...
XO..
.XO.
..XO

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

logn으로 구현한거 같은데 왜 시간초과가 나오는지 모르겠습니다.

kysu5095 3년 전 0

sait2000 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말