[Algorithm] 백준 1107(BOJ 1107) 리모컨 문제풀이!! (Java)

---

안녕하세요 coding-knowjam입니다.

오늘은 백준 온라인 저지에 있는 1107번 리모컨 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

해당 문제는 모든 경우의 수를 확인해서 풀어야 하는 완전 탐색, 브루트 포스 유형의 문제입니다.

실제로 문제를 풀다 보면 경우의 수를 하나씩 놓치게 되는데 생각보다 고려해야 할 사항이 많습니다.

특별한 알고리즘보다는 경우의 수만 잘 확인하면 풀리는 문제이므로 막상 풀면 어렵지 않았다고 생각하실 겁니다.

먼저 문제에서 요구하는 사항은 현재 채널은 100번이며 이동해야 할 채널까지 리모컨 버튼을 얼마나 최소로 클릭할 수 있느냐입니다.

문제를 풀기 위해 고려해야 할 경우의 수는 다음과 같습니다.

1. 현재 채널(100)과 타깃 채널(이동해야 할 채널)이 같은 경우
2. 타깃 채널로 리모컨 숫자 버튼만 눌러서 이동한 경우
3. 현재 채널에서 타깃 채널까지 +,- 버튼만 눌러서 이동한 경우
4. 리모컨 숫자 버튼을 눌러서 타깃 채널에 가장 근접한 작은 채널로 이동한 후 + 버튼을 눌러서 이동한 경우
5. 리모컨 숫자 버튼을 눌러서 타깃 채널에 가장 근접한 큰 채널로 이동한 후 - 버튼을 눌러서 이동한 경우

위의 5가지 경우를 고려하면 되는데 각각의 경우에서 구해지는 버튼 누름 횟수 중 가장 최솟값을 출력하면 됩니다.

추가로 4번의 경우 채널이 무한대만큼 존재하므로 적절한 기준으로 탐색을 중지할 수 있도록 신경 써야 합니다.

그럼 코드를 살펴보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingknowjam.algorithm.boj;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.IntStream;

public class BOJ_1107 {
	private static final Scanner scanner = new Scanner(System.in);
	// 리모컨 숫자버튼 누른 횟수
	private static int numberPadClickCount = 0;
	private static int currentMinValue = Integer.MIN_VALUE;

	//백준온라인저지 1107번 리모컨 문제풀이
	public static void main(String[] args) {
		// 리모컨
		RemoteController remoteController = RemoteController.create();
		// 현재 채널
		Channel currentChannel = Channel.of(100);
		// 이동해야 할 채널
		Channel targetChannel = Channel.of(scanner.nextInt());
		// 리모컨 버튼 망가짐
		breakButton(remoteController, scanner);

		// 현재 채널과 타켓 채널이 동일한 경우 -> 버튼 안눌러도 되므로 0이 최소값
		if (targetChannel.equals(currentChannel)) {
			System.out.println(numberPadClickCount);
			return;
		}

		// 리모컨 숫자버튼 눌러서 타켓 채널로 이동 가능한 경우 -> 숫자버튼 누른 횟수가 최소값
		int count1 = Integer.MAX_VALUE;
		if (remoteController.isPress(targetChannel.value())) {
			count1 = numberPadClickCount;
		}

		// 리모컨 +, - 버튼만 눌러서 채널 이동한 경우 -> +, - 버튼 누른 횟수가 최소값
		int count2 = currentChannel.getDifferenceValue(targetChannel);

		// 현재 리모컨으로 이동할 수 있는 채널 중 타켓채널에 가장 근접한 작은 채널로 이동한 경우
		// -> 숫자버튼 누른 횟수 + "+, -" 버튼 누른 횟수가 최소 값
		int count3 = currentChannel.moveLessTargetChannel(targetChannel, remoteController);

		// 현재까지 중 최소값 구하기
		currentMinValue = getMinValue(count1, count2, count3);

		// 현재 리모컨으로 이동할 수 있는 채널 중 타켓채널에 가장 근접한 큰 채널로 이동한 경우
		// -> -> 숫자버튼 누른 횟수 + "+, -" 버튼 누른 횟수가 최소 값
		// ## 채널이 무한대이므로 currentMinValue 값보다 버튼 누른 횟수 많으면 종료
		int count4 = currentChannel.moveGreaterTargetChannel(targetChannel, remoteController);

		// 최종 최소값 비교해서 결과 출력
		System.out.println(Math.min(currentMinValue, count4));
	}

	private static int getMinValue(int value1, int value2, int value3){
		return Math.min(value1, Math.min(value2, value3));
	}

	private static void breakButton(RemoteController remoteController, Scanner scanner) {
		IntStream.range(0, scanner.nextInt())
			.forEach(ignore -> remoteController.breakButton(scanner.nextInt()));
	}

	static class RemoteController {
		private final HashMap<Integer, Integer> numberPad = new HashMap<>();

		private RemoteController() {
			IntStream.range(0, 10)
				.forEach(number -> numberPad.put(number, 1));
		}

		public static RemoteController create() {
			return new RemoteController();
		}

		public void breakButton(int buttonNumber) {
			numberPad.put(buttonNumber, 0);
		}

		public boolean isPress(int channel) {
			String[] digitsArray = String.valueOf(channel).split("");
			numberPadClickCount = digitsArray.length;
			long matchCount = Arrays.stream(digitsArray)
				.map(Integer::parseInt)
				.filter(integer -> numberPad.get(integer) == 1)
				.count();
			return matchCount == digitsArray.length;
		}
	}

	static class Channel {
		private int channel;

		private Channel(final int channel) {
			this.channel = channel;
		}

		public static Channel of(final int channel) {
			return new Channel(channel);
		}

		private int moveLessTargetChannel(Channel targetChannel, RemoteController remoteController) {
			boolean end = false;
			channel = targetChannel.value();
			while (!end) {
				if (channel <= 0) {
					numberPadClickCount = 99999999;
					break;
				}
				channel--;
				end = remoteController.isPress(channel);
			}
			return targetChannel.value() - channel + numberPadClickCount;
		}

		private int moveGreaterTargetChannel(Channel targetChannel, RemoteController remoteController) {
			boolean end = false;
			channel = targetChannel.value();
			while (!end) {
				if (channel >= targetChannel.value() + currentMinValue) {
					numberPadClickCount = 99999999;
					break;
				}
				channel++;
				end = remoteController.isPress(channel);
			}

			return channel - targetChannel.value() + numberPadClickCount;
		}

		public int getDifferenceValue(Channel closeChannel) {
			return Math.abs(this.channel - closeChannel.channel);
		}

		public int value() {
			return this.channel;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;
			if (o == null || getClass() != o.getClass())
				return false;
			Channel channel1 = (Channel)o;
			return channel == channel1.channel;
		}

		@Override
		public int hashCode() {
			return Objects.hash(channel);
		}
	}
}

 

알고리즘 문제를 풀면서 너무 절차 지향적으로 작성하는 것 같아 최대한 객체지향스럽게 작성해보았습니다.

모든 코드에 주석을 달지는 않았지만 특별한 알고리즘이 존재하지 않으므로 이해하는데 크게 어렵지 않으실 겁니다.

감사합니다.

---