[백준/Java] 10709번 : 기상캐스터
[문제]
JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.
각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.
지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.
각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.
[조건]
- 시간 제한 : 1초
- 메모리 제한 : 256MB
[입력]
입력은 1 + H 행으로 주어진다.
첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.
이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.
[출력]
출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.
[문제 풀이]
- 입력 받을 때 c면 0
- 그렇지 않다면, 왼쪽으로 한 칸씩 이동해 c(==0)을 찾고 이동한 칸 수 만큼 집어넣음
- 만약 왼쪽에 c(==0)이 없다면 -1 집어넣음
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
static StringTokenizer st;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
int[][] region = new int[H][W];
for(int h=0; h<H; h++) {
String text = br.readLine();
next : for(int w=0; w<W; w++) {
char c = text.charAt(w);
if(c=='c') region[h][w] = 0;
else {
int idx = 1;
int nw = w-idx;
while(nw>=0) {
if(region[h][nw]==0) {
region[h][w] = idx;
continue next;
}
idx++;
nw = w-idx;
}
region[h][w] = -1;
}
}
}
for(int h=0; h<H; h++) {
for(int w=0; w<W; w++) {
System.out.print(region[h][w]+" ");
}
System.out.println();
}
}
}
[소감]
- 시간복잡도 측면에서 줄일 수 있는 방법이 없을지 더 고민해보면 좋을듯
- 위의 코드 소요 시간은 324ms임.