da9dac

문제

접근 방식

바킹독님 시뮬레이션 강의를 들으면서 처음 풀어보는 빡구현 문제로

지문 길이 보고 풀기 싫어지지만 귀찮음을 이겨내고 풀어냈다...

무식하게 풀다 보니 코드가 엄청 길어지긴 했지만 백트래킹을 사용해서

쉽게 풀 수 있는 문제다. (지문의 길이게 겁먹지 말자...)

백트래킹 연습 문제로 풀었던 N과 M 시리즈를 CCTV에 적용하면 되는 문제로

1번 : 위, 오른쪽, 아래, 왼쪽 중 한 방향이벽을 만나기 전까지 감시 가능
2번 : 위/아래, 왼쪽/오른쪽 중 양쪽이 벽을 만나기 전까지 감시 가능
3번 : 위/오른쪽, 오른쪽/아래, 아래/왼쪽, 왼쪽/위처럼 직각인 두 방향이 벽을 만나기 전까지 감시 가능
4번 : 위/오른쪽/아래, 오른쪽/아래/왼쪽, 아래/왼쪽/위, 왼쪽/위/오른쪽처럼 세 방향이 벽을 만나기 전까지 감시 가능
5번 : 위/오른쪽/아래/왼쪽이 모두 벽을 만나기 전까지 감시 가능

위와 같이 CCTV 종류 별로 감시 가능한 경우의 수들을 모두 시도해 주면 된다.

사각지대는 경우의 수들을 모두 시도해 보며 마지막 CCTV를 방문했을 때

현재까지 방문하지 않은 곳 + 벽의 수를 구하면 알 수 있기 때문에

테스트 케이스를 입력을 받으면서 CCTV의 좌표를 리스트에 저장해 둔 후에

리스트를 이용해 백트래킹을 해주면서 방문 여부를 체크해 준다.

이때 조심해야 할 부분은 백트래킹에서 다른 cctv가 감시한 부분의 방문 여부를

다른 cctv가 바꿀 수 없게 해야 한다.

// 초기 상태
4 0 0 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 0 0 4

// 방문 후
4 x x x x x x
x 0 0 2 0 0 x
x x x x x x 4

// 잘못된 케이스
4 x x x x x 0
x 0 0 2 0 0 0
x 0 0 0 0 0 4

// 다른 CCTV에 관여하지 말아야 함
4 x x x x x x
x 0 0 2 0 0 0
x 0 0 x 0 0 4

즉, 위와 같이 다른 CCTV가 먼저 감시 중인 곳을 건드리면 안된다.

이 부분을 해결하기 위해 방문여부를 boolean 배열이 아닌

몇 번째 CCTV인지 리스트의 인덱스를 사용해서 기록했다.

풀이

public class Main {

	private static int n;
	private static int m;
	private static int size;
	private static int min = Integer.MAX_VALUE;

	private static int[][] office;
	private static int[][] isWatched;
	private static List<CCTV> cctvs;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		office = new int[n][m];
		isWatched = new int[n][m];

		cctvs = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				int num = Integer.parseInt(st.nextToken());
				office[i][j] = num;

				if (num == 6) isWatched[i][j] = 1;
				else if (num != 0) {
					cctvs.add(new CCTV(i, j));
				}
			}
		}

		size = cctvs.size();

		watch(0);

		System.out.println(min);
	}

	private static void watch(int idx) {
		if (idx == size) {
			int count = 0;
			for (int[] w : isWatched) {
				for (int b : w) {
					if (b == 0) count++;
				}
			}
			min = Math.min(min, count);
			return;
		}

		CCTV cur = cctvs.get(idx);
		int x = cur.x;
		int y = cur.y;
		int cctv = office[x][y];

		switch (cctv) {
			case 1: {
				up(idx, x, y);
				down(idx, x, y);
				left(idx, y, x);
				right(idx, y, x);
				break;
			}
			case 2: {
				height(idx, x, y);
				width(idx, y, x);
				break;
			}
			case 3: {
				upRight(idx, x, y);
				rightDown(idx, x, y);
				downLeft(idx, x, y);
				leftUp(idx, x, y);
				break;
			}
			case 4: {
				leftUpRight(idx, x, y);
				upRightDown(idx, x, y);
				rightDownLeft(idx, x, y);
				downLeftUp(idx, x, y);
				break;
			}
			case 5: {
				all(idx, x, y);
				break;
			}
		}
	}

	private static void right(int idx, int y, int x) {
		visitRigth(idx, y, x);

		watch(idx + 1);

		rollbackRight(idx, y, x);
	}

	private static void rollbackRight(int idx, int y, int x) {
		for (int j = y; j < m; j++) {
			if (office[x][j] == 6) break;
			if (isWatched[x][j] != idx + 1) continue;
			isWatched[x][j] = 0;
		}
	}

	private static void visitRigth(int idx, int y, int x) {
		for (int j = y; j < m; j++) {
			if (office[x][j] == 6) break;
			if (isWatched[x][j] != 0) continue;
			isWatched[x][j] = idx + 1;
		}
	}

	private static void left(int idx, int y, int x) {
		visitLeft(idx, y, x);

		watch(idx + 1);

		rollbackLeft(idx, y, x);
	}

	private static void rollbackLeft(int idx, int y, int x) {
		for (int j = y; j >= 0; j--) {
			if (office[x][j] == 6) break;
			if (isWatched[x][j] != idx + 1) continue;
			isWatched[x][j] = 0;
		}
	}

	private static void visitLeft(int idx, int y, int x) {
		for (int j = y; j >= 0; j--) {
			if (office[x][j] == 6) break;
			if (isWatched[x][j] != 0) continue;
			isWatched[x][j] = idx + 1;
		}
	}

	private static void down(int idx, int x, int y) {
		visitDown(idx, x, y);

		watch(idx + 1);

		rollbackDown(idx, x, y);
	}

	private static void rollbackDown(int idx, int x, int y) {
		for (int j = x; j < n; j++) {
			if (office[j][y] == 6) break;
			if (isWatched[j][y] != idx + 1) continue;
			isWatched[j][y] = 0;
		}
	}

	private static void visitDown(int idx, int x, int y) {
		for (int j = x; j < n; j++) {
			if (office[j][y] == 6) break;
			if (isWatched[j][y] != 0) continue;
			isWatched[j][y] = idx + 1;
		}
	}

	private static void up(int idx, int x, int y) {
		visitUp(idx, x, y);

		watch(idx + 1);

		rollbackUp(idx, x, y);
	}

	private static void rollbackUp(int idx, int x, int y) {
		for (int j = x; j >= 0; j--) {
			if (office[j][y] == 6) break;
			if (isWatched[j][y] != idx + 1) continue;
			isWatched[j][y] = 0;
		}
	}

	private static void visitUp(int idx, int x, int y) {
		for (int j = x; j >= 0; j--) {
			if (office[j][y] == 6) break;
			if (isWatched[j][y] != 0) continue;
			isWatched[j][y] = idx + 1;
		}
	}

	private static void all(int idx, int x, int y) {
		visitLeft(idx, y, x);
		visitUp(idx, x, y);
		visitRigth(idx, y, x);
		visitDown(idx, x, y);

		watch(idx + 1);

		rollbackLeft(idx, y, x);
		rollbackUp(idx, x, y);
		rollbackRight(idx, y, x);
		rollbackDown(idx, x, y);
	}
	private static void leftUpRight(int idx, int x, int y) {
		visitLeft(idx, y, x);
		visitUp(idx, x, y);
		visitRigth(idx, y, x);

		watch(idx + 1);

		rollbackLeft(idx, y, x);
		rollbackUp(idx, x, y);
		rollbackRight(idx, y, x);
	}

	private static void upRightDown(int idx, int x, int y) {
		visitUp(idx, x, y);
		visitRigth(idx, y, x);
		visitDown(idx, x, y);

		watch(idx + 1);

		rollbackUp(idx, x, y);
		rollbackRight(idx, y, x);
		rollbackDown(idx, x, y);
	}

	private static void rightDownLeft(int idx, int x, int y) {
		visitRigth(idx, y, x);
		visitDown(idx, x, y);
		visitLeft(idx, y, x);

		watch(idx + 1);

		rollbackRight(idx, y, x);
		rollbackDown(idx, x, y);
		rollbackLeft(idx, y, x);
	}

	private static void downLeftUp(int idx, int x, int y) {
		visitDown(idx, x, y);
		visitLeft(idx, y, x);
		visitUp(idx, x, y);

		watch(idx + 1);

		rollbackDown(idx, x, y);
		rollbackLeft(idx, y, x);
		rollbackUp(idx, x, y);
	}

	private static void width(int idx, int y, int x) {
		visitRigth(idx, y, x);
		visitLeft(idx, y, x);

		watch(idx + 1);

		rollbackRight(idx, y, x);
		rollbackLeft(idx, y, x);
	}

	private static void height(int idx, int x, int y) {
		visitUp(idx, x, y);
		visitDown(idx, x, y);

		watch(idx + 1);

		rollbackUp(idx, x, y);
		rollbackDown(idx, x, y);
	}

	private static void upRight(int idx, int x, int y) {
		visitUp(idx, x, y);
		visitRigth(idx, y, x);

		watch(idx + 1);

		rollbackUp(idx, x, y);
		rollbackRight(idx, y, x);
	}

	private static void rightDown(int idx, int x, int y) {
		visitRigth(idx, y, x);
		visitDown(idx, x, y);

		watch(idx + 1);

		rollbackRight(idx, y, x);
		rollbackDown(idx, x, y);
	}
	private static void downLeft(int idx, int x, int y) {
		visitDown(idx, x, y);
		visitLeft(idx, y, x);

		watch(idx + 1);

		rollbackDown(idx, x, y);
		rollbackLeft(idx, y, x);
	}

	private static void leftUp(int idx, int x, int y) {
		visitLeft(idx, y, x);
		visitUp(idx, x, y);

		watch(idx + 1);

		rollbackLeft(idx, y, x);
		rollbackUp(idx, x, y);
	}

	private static class CCTV {
		int x;
		int y;

		public CCTV(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

세그먼트 트리를 사용해서 풀 수 있는 문제라는데 아직 배우지 않아서

세그먼트 트리에 대해서 간단하게 검색해 보니 재귀를 사용한 방식이라

스택으로도 풀 수 있는 문제라서 스택을 사용해서 풀어봤다.

눈으로는 이해가 쉽고 넓이가 바뀌는 구간을 찾아서 계산을 해주면

해결된다는 사실도 머리로는 쉽게 이해가 가능하지만

구현하려니 막상 머리가 안 돌아갔다...

우선, 간단하게만 생각해 보면

직사각형의 넓이는 다음 막대그래프의 높이가 낮아질수록

최대로 가능한 넓이가 작아질 것이고

다음 막대그래프의 높이가 같거나 높아야

최대로 가능한 넓이가 유지되거나 커진다.

정리하면 각각의 높이가 4 5 5인 막대그래프가 연속해서 존재하면

가능한 최대 높이는 가장 낮은 높이인 4와 연속된 그래프의 개수 3을 곱한

12가 나온다는 것을 알 수 있고

각각의 높이가 4 3 2인 그래프가 연속해서 존재하면

가능한 최대 높이는 가장 낮은 높이인 2와 연속된 그래프의 개수 3을 곱한

6이 나온다는 말이다.

즉, 스택에 구간이 바뀔 때까지 계속해서 쌓아주다가

구간이 바뀔 때 쌓아둔 그래프들은 비슷한 높이가 연속적으로 존재하기 때문에

모두 계산해 주면 그 구간의 최댓값을 구할 수 있다.

조심해야 할 부분은 위와 같이 이전까지의 모든 값들을 다 계산해줘야 한다는 것인데

지금의 경우에는 아래 표시한 영역의 넓이는 7이라 정답이 아니지만

만약 아래 표시한 영역의 넓이가 가장 큰 경우에 이 부분을 체크하지 않으면

잘못된 정답을 얻게 된다.

그래서 스택에서 값을 하나씩 꺼낼 때마다 각각 계산을 하여

현재까지 기록된 최댓값이랑 비교해서 저장해줘야 한다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int[] arr = new int[n + 2];
		for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(br.readLine());

		Stack<Integer> histograms = new Stack<>();
		histograms.push(0);

		int max = 0;

		for (int i = 1; i <= n + 1; i++) {
			while (!histograms.isEmpty()) {
				int prev = arr[histograms.peek()];
				if (prev <= arr[i]) break;
				histograms.pop();
				max = Math.max(max, prev * (i - histograms.peek() - 1));
			}
			histograms.push(i);
		}

		System.out.println(max);
	}
}

문제

접근 방식

문제를 본 순간 떠올릴 수 있는 가장 쉬운 풀이는

배열을 하나하나 다 비교해 보는 것인데

두 배열의 최대 크기가 20000이기 때문에

최악의 시간 복잡도가 20000^2라 해당 문제를 풀 수가 없다.

투 포인터를 사용하여 효율적으로 풀 수 있지만

아직 배우지 않았기 때문에 정렬만 사용해서 풀어보기로 했다.

우선 두 배열을 모두 오름차순으로 기본 정렬한 후에

먹히는 배열을 순회하면서 먹는 배열을 매번 순회해 준다.

이때 먹히는 배열의 값이 먹는 배열의 값보다 작아지는 시점부터는

뒤에 오는 배열의 값들은 확인할 필요가 없기 때문에

남은 배열의 크기만큼 카운트를 추가해 주면 된다.

이렇게 풀면 시간은 오래 걸려도 통과는 되긴 하지만

나중에 이분탐색을 배운 후에 다시 풀이를 추가하도록 하겠다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			Integer[] a = new Integer[n];
			Integer[] b = new Integer[m];

			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				a[j] = Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				b[j] = Integer.parseInt(st.nextToken());
			}

			Arrays.sort(a);
			Arrays.sort(b);

			int count = 0;
			int max = a[n - 1];

			for (int j = 0; j < m; j++) {
				int num = b[j];
				if (num >= max) break;
				for (int k = 0; k < n; k++) {
					if (num >= a[k]) continue;
					count += n - k;
					break;
				}
			}

			sb.append(count).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

숫자의 등장 횟수가 가장 많은 순서대로 정렬해야 하고

같은 경우에는 처음 입력된 순서대로 유지해야 한다.

입력 순서를 유지하기 위해 LinkedHashMap을 사용해서 풀었는데

생각해보니 입력의 범위가 모두 int형이라 배열을 사용해도 되는 문제다.

순서와 숫자의 카운트만 신경 써서 정렬해주면 되는 문제라

구현 자체는 어렵지 않았다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		Map<Integer, Integer> sequence = new LinkedHashMap<>();

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			int key = Integer.parseInt(st.nextToken());
			sequence.put(key, sequence.getOrDefault(key, 0) + 1);
		}

		List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(sequence.entrySet()).stream()
			.sorted((o1, o2) -> {
				int ov = o1.getValue();
				int tv = o2.getValue();

				if (ov == tv) {
					return 0;
				} else if (ov > tv) {
					return -1;
				} else {
					return 1;
				}
			}).collect(Collectors.toList());

		for (Map.Entry<Integer, Integer> entry : entries) {
			int target = entry.getKey();
			int end = entry.getValue();

			for (int i = 0; i < end; i++) {
				sb.append(target).append(" ");
			}
		}

		System.out.println(sb);
	}
}

문제

접근 방식

입력받은 문자열들 중에서 중복을 제외하고

문자열의 길이가 같지 않다면 짧은 것을 우선 정렬하고

같다면 사전순으로 정렬해줘야 한다.

입력받은 배열을 위의 정렬 기준으로 정렬한 후에

중복이 아닌 경우만 출력해 주거나

Set을 이용해 애초에 중복을 허용하지 않고 저장하여

정렬한 후에 출력해 주는 방법이 있는데 Set을 사용해서 풀었다.

HashSet을 이용해서 중복 없이 입력받은 후에 정렬을 해주거나

TreeSet을 이용해서 순서를 유지해 가며 입력을 받을 수 있다.

첫 번째 코드가 HashSet을 이용한 방법이고

두 번째 코드가 TreeSet을 이용한 방법이다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());

		Set<String> set = new HashSet<>();

		for (int i = 0; i < n; i++) set.add(br.readLine());

		List<String> result = set.stream().sorted(Comparator.comparingInt(String::length).thenComparing(o -> o)).collect(Collectors.toList());

		for (String s : result) sb.append(s).append("\n");

		System.out.println(sb);
	}
}

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());

		Set<String> set = new TreeSet<>(Comparator.comparingInt(String::length).thenComparing(o -> o));

		for (int i = 0; i < n; i++) set.add(br.readLine());

		for (String s : set) sb.append(s).append("\n");

		System.out.println(sb);
	}
}

문제

접근 방식

이 문제는 입력을 왜 이렇게 불편하게 주는지는 모르겠다...

입력 받은 수들을 모두 뒤집은 후에 오름차순으로 정렬해야 하는데

입력 자체를 스트링으로 받기 때문에 스트링 빌더의 리버스 메서드를 사용하여

돌려준 후에 long 타입으로 변환해줬다.

그 후에 정렬은 직접 구현해서 하거나 sort 메서드를 사용하면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());

		long[] arr = new long[n];
		int idx = 0;

		while (true) {
			if (st.hasMoreTokens()) {
				StringBuilder input = new StringBuilder(st.nextToken());
				arr[idx++] = Long.parseLong(input.reverse().toString());
				if (idx == n) break;
			} else {
				st = new StringTokenizer(br.readLine());
			}
		}

		Arrays.sort(arr);

		for (long a : arr) {
			sb.append(a).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

정렬한 후에 반복문으로 카드 수를 일일이 체크하는 것이 더 빠르지만

Comparator 사용에 익숙해질 겸 한 번의 정렬만으로 해결해 봤다.

맵을 사용 해서 카드의 수를 키로 하고

값을 해당 카드가 등장할 때마다 1씩 증가시켜 줬다.

맵은 배열처럼 하나의 객체와 타입으로만 이루어진 것이 아니기 때문에

맵을 정렬하기 위해선 entrySet 메서드를 사용하여 셋이나 리스트로 바꿔줘야 한다.

List<Map.Entry<Long, Integer>> entries = new ArrayList<>(cards.entrySet());
entries.sort(
    (o1, o2) -> {
        int ov = o1.getValue();
        int tv = o2.getValue();

        long ok = o1.getKey();
        long tk = o2.getKey();

        if (ov < tv) {
            return 1;
        } else if (ov > tv) {
            return -1;
        } else {
            if (ok < tk) {
                return -1;
            } else if (ok > tk) {
                return 1;
            } else {
                return 0;
            }
        }
    }
);

이번 풀이에서는 리스트를 사용하여 정렬을 하였고

이전 문제에서 풀었던 것처럼 Comparator를 구현하여

sort 메서드의 정렬 기준으로 전달해 주었다.

우선 가장 많이 등장한 횟수 기준으로 정렬하기 위해

값을 최우선 순위로 비교한 후에 키를 기준으로 비교해 주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		
	}
}

문제

접근 방식

세 가지의 정렬 기준대로 시리얼 번호를 정렬해야 하는데

자바에서는 Comparator를 사용하여 정렬 메서드의 정렬 기준을 커스텀할 수 있다.

(블로그에 Comparator와 Comparable에 대해 정리해 둔 글이 있으니 참고하길 바란다.)

우선 첫 번째 정렬 기준은 문자열의 길이라 짧은 것이 가장 최우선이고

길이가 같다면 시리얼 번호의 각 자릿수의 합이 낮은 것

합도 같은 경우에는 사전순으로 정렬해준다.

public int compare(String o1, String o2) {
    if (o1.length() != o2.length()) {
        return o1.length() - o2.length();
    } else {
        int sum = sum(o1, o2);
        if (sum != 0) {
            return sum;
        }
        else {
            return o1.compareTo(o2);
        }
    }
}

이를 코드로 구현하면 위와 같은데

문자열의 길이가 서로 다른 경우 더 짧은 길이를 우선 정렬하고

길이가 같다면 두 문자열의 자릿수를 모두 합한 값으로 비교한 후에

이 값들이 같다면 사전순으로 비교해 준다.

문자열의 사전순 비교는 따로 구현할 필요 없이

String 클래스에 있는 compareTo 메서드를 사용해 주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());

		String[] serials = new String[n];

		for (int i = 0; i < n; i++) {
			serials[i] = br.readLine();
		}

		Arrays.sort(serials, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				if (o1.length() != o2.length()) {
					return o1.length() - o2.length();
				} else {
					int sum = sum(o1, o2);
					if (sum != 0) {
						return sum;
					}
					else {
						return o1.compareTo(o2);
					}
				}
			}

			int sum(String o1, String o2) {
				int x = 0;
				int y = 0;

				for (int i = 0; i < o1.length(); i++) {
					char cx = o1.charAt(i);
					char cy = o2.charAt(i);

					if (Character.isDigit(cx)) x += (cx - '0');
					if (Character.isDigit(cy)) y += (cy - '0');
				}

				return x - y;
			}
		});

		for (String s : serials) {
			sb.append(s).append("\n");
		}

		System.out.println(sb);
	}
}