[Java] SWEA 4371번 항구에 들어오는 배

SW Expert Academy

---

풀이

우선, 입력받은 즐거운 날은 정렬이 되어있으므로 1일 부터 시작해서 각 즐거운 날마다의 주기를 구하였습니다.

 

그리고, 다음 인덱스 부터 전부 살펴보면서 해당 주기에 포함되는일이 있다면 입력받은 즐거운 날과 인덱스 크기가 동일한 boolean 타입의 check 배열을 사용해서 들어온 배가 주기에 해당한 배인지를 표시하였습니다.

이때, check가 true이면 이미 주기에 포함된 배가 들어온 것 이므로 다음 즐거운 날을 검사하도록 하였습니다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
	public static int N;
	public static boolean[] check;
	public static int[] harbor;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			N = Integer.parseInt(br.readLine());
			check = new boolean[N];
			harbor = new int[N];
			
			for (int i = 0; i < N; ++i) {
				harbor[i] = Integer.parseInt(br.readLine());
			}
			
			int boatCnt = 0;
			for (int i = 1; i < N; ++i) {
				if (check[i]) {
					continue;
				}
				
				boatCnt++;
				
				int cycle = harbor[i] - 1;
				int happyDay = harbor[i];
				for (int j = i; j < N; ++j) {
					if (happyDay == harbor[j]) {
						check[j] = true;
						happyDay += cycle;
					}
				}
			}
			
			sb.append("#").append(tc).append(" ").append(boatCnt);
			System.out.println(sb);
			sb.setLength(0);
		}
	}
}

---

pyo7410/Algorithm