[TIL-32/230924] 알고리즘, 숫자야구
날이 많이 풀려 시원한 주말, 나는 개발과 함께 보냈다.
어제 하루를 휴식해서 컨디션이 좋았기에 우선 알고리즘부터 시작했다.
저번에 풀지 못하고 stranger's lab 블로그를 보며 공부했던 체스판 다시 칠하기를 스스로 다시 풀어보았다.
https://www.acmicpc.net/problem/1018
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
| 시간 | 제한메모리 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
| 2 초 | 128 MB | 104671 | 51838 | 41470 | 49.663% |
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
문제 분석
처음에 감이 잡히지 않는 문제였다.
어떻게 접근해야 하나 고민을 했고, 8x8의 체스판 범위를 만들어, 입력값 내에서 조건의 최솟값을 만족시키는 8x8을 찾아서 그 최솟값을 반환하는 방식의 풀이방법을 구현해야 한다고 이해하였다.
하지만 구현하지 못하였고, 그래서 stranger's lab님의 블로그를 참고하여 공부 후, 며칠이 지난 오늘 다시 풀어보았다.
문제 풀이
- find 메서드 구현
- 입력받은 (x,y) 좌표를 기점으로 8x8 체스판을 만듦
- (x,y) 좌표의 값을 TF에 저장하고, 체스판을 순회
- TF의 값을 매번 반전시키며, TF의 값과 chess[i][j]의 값이 같지 않다면 count의 개수를 늘린다.
- count와 64-count 중 최솟값을 count에 저장
- min과 count 중 최솟값을 min에 저장
- main 메서드 구현
- 행과 열을 입력받고, 체스판 배열을 입력받는다.
- 2차원 boolean 배열을 선언
- 2중 for문을 통해 체스판을 순회하며 W인 곳을 true, B인 곳을 false로 배열에 저장
- find 메서드를 실행할 행의 범위, 열의 범위를 지정(입력받은 행의 값, 열의 값에서 각각 -7)
- 2중 for문을 돌면서 find 메서드 실행
- min 값 출력
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static boolean[][] chess; // 체스판 상태를 저장하는 배열
public static int min = 64; // 최소 칠해야 하는 칸 수를 저장할 변수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int row = Integer.parseInt(st.nextToken()); // 행 수
int col = Integer.parseInt(st.nextToken()); // 열 수
chess = new boolean[row][col]; // 체스판 배열 초기화
// 입력 받은 체스판 정보를 배열에 저장
for (int i = 0; i < row; i++) {
String chessRow = br.readLine();
for (int j = 0; j < col; j++) {
if (chessRow.charAt(j) == 'W') {
chess[i][j] = true; // 'W'인 경우 true로 표시
}
if (chessRow.charAt(j) == 'B') {
chess[i][j] = false; // 'B'인 경우 false로 표시
}
}
}
int rangeOfRow = row - 7; // 행 범위
int rangeOfCol = col - 7; // 열 범위
for (int i = 0; i < rangeOfRow; i++) {
for (int j = 0; j < rangeOfCol; j++) {
find(i, j); // 모든 가능한 8x8 체스판을 탐색하며 최소값 찾기
}
}
System.out.println(min); // 최소 칠해야 하는 칸 수 출력
}
// 주어진 시작 위치에서 8x8 체스판을 검사하여 최소 칠해야 하는 칸 수 계산
public static void find(int x, int y) {
int endX = x + 8; // 행 끝 위치
int endY = y + 8; // 열 끝 위치
int count = 0; // 칠해야 하는 칸 수 카운트
boolean TF = chess[x][y]; // 첫 번째 칸의 색상
for (int i = x; i < endX; i++) {
for (int j = y; j < endY; j++) {
if (chess[i][j] != TF) { // 현재 칸의 색상과 기대값이 다르면
count++; // 칠해야 하는 칸 수 증가
}
TF = !TF; // 색상을 반전시킴
}
TF = !TF; // 행이 바뀔 때 색상을 반전시킴
}
count = Math.min(count, 64 - count); // 현재 칠해야 하는 칸 수와 반대로 칠할 때의 칸 수 중 작은 값 선택
min = Math.min(min, count); // 현재까지의 최소값과 비교하여 갱신
}
}공부는 stranger's lab님의 블로그를 보고 하여 코드 진행 방식은 거의 유사하나, 복사-붙여넣기가 아닌 공부한 내용을 바탕으로 보지 않고 직접 코드를 작성하였다. 보다 질 좋은 풀이를 보기 원한다면 아래 참고자료에 추가한 stranger's lab님의 블로그를 들어가보길 추천한다.
숫자야구
https://github.com/woowacourse/java-baseball-precourse
GitHub - woowacourse/java-baseball-precourse: 숫자 야구게임 미션을 진행하는 저장소
숫자 야구게임 미션을 진행하는 저장소. Contribute to woowacourse/java-baseball-precourse development by creating an account on GitHub.
github.com
오늘부터 우아한 테크코스의 프리코스를 준비하려 한다.
우선 첫 번째 과제인 숫자 야구 게임을 만들어봤다.
기능 요구사항
기본적으로 1부터 9까지 서로 다른 수로 이루어진 3자리의 수를 맞추는 게임이다.
- 같은 수가 같은 자리에 있으면 스트라이크, 다른 자리에 있으면 볼, 같은 수가 전혀 없으면 포볼 또는 낫싱이란 힌트를 얻고, 그 힌트를 이용해서 먼저 상대방(컴퓨터)의 수를 맞추면 승리한다.
- 예) 상대방(컴퓨터)의 수가 425일 때
- 123을 제시한 경우 : 1스트라이크
- 456을 제시한 경우 : 1볼 1스트라이크
- 789를 제시한 경우 : 낫싱
- 예) 상대방(컴퓨터)의 수가 425일 때
- 위 숫자 야구 게임에서 상대방의 역할을 컴퓨터가 한다. 컴퓨터는 1에서 9까지 서로 다른 임의의 수 3개를 선택한다. 게임 플레이어는 컴퓨터가 생각하고 있는 3개의 숫자를 입력하고, 컴퓨터는 입력한 숫자에 대한 결과를 출력한다.
- 이 같은 과정을 반복해 컴퓨터가 선택한 3개의 숫자를 모두 맞히면 게임이 종료된다.
- 게임을 종료한 후 게임을 다시 시작하거나 완전히 종료할 수 있다.
- 사용자가 잘못된 값을 입력할 경우 IllegalArgumentException을 발생시킨 후 애플리케이션은 종료되어야 한다.
- 아래의 프로그래밍 실행 결과 예시와 동일하게 입력과 출력이 이루어져야 한다.
입출력 요구사항
입력
- 3자리의 수
- 게임이 끝난 경우 재시작/종료를 구분하는 1과 2 중 하나의 수
출력
- 입력한 수에 대한 결과를 볼, 스트라이크 개수로 표시
1볼 1스트라이크- 하나도 없는 경우
낫싱- 3개의 숫자를 모두 맞힐 경우
3스트라이크
3개의 숫자를 모두 맞히셨습니다! 게임 종료💻 프로그래밍 실행 결과 예시
숫자를 입력해주세요 : 123
1볼 1스트라이크
숫자를 입력해주세요 : 145
1볼
숫자를 입력해주세요 : 671
2볼
숫자를 입력해주세요 : 216
1스트라이크
숫자를 입력해주세요 : 713
3스트라이크
3개의 숫자를 모두 맞히셨습니다! 게임 종료
게임을 새로 시작하려면 1, 종료하려면 2를 입력하세요.
1
숫자를 입력해주세요 : 123
1볼
…기재된 조건은 위와 같다.
특히 프로그래밍 요구사항을 지키면서 개발을 해야하는데, 우선 나는 숫자 야구가 어떤 방식으로 작동하는지 이해하기 위해 오늘은 한 클래스 내에 구현을 해보는 것을 목표로 개발읕 진행했다.
차후 추가 공부를 하면서 리팩토링해볼 생각이다.
코드는 아래와 같다.
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class baseball {
public static void main(String[] args) {
while (true) {
game();
}
}
public static void wrongNumber() throws IllegalArgumentException {
System.exit(0);
}
// 게임 진행
public static void game() {
Scanner sc = new Scanner(System.in);
System.out.print("숫자를 입력해주세요 : ");
String userNumber = sc.next();
if (userNumber.length() != 3 || userNumber.charAt(0) == userNumber.charAt(1) || userNumber.charAt(0) == userNumber.charAt(2)
|| userNumber.charAt(1) == userNumber.charAt(2)) {
wrongNumber();
}
// System.out.println("사용자 : " + userNumber);
String computerNumber = computer();
String judgement = judge(userNumber, computerNumber);
System.out.println(judgement);
if (judgement.equals("3스트라이크")) {
strikeOut();
}
}
//3개의 숫자를 모두 맞힌 경우 게임 종료
public static void strikeOut() {
Scanner sc = new Scanner(System.in);
System.out.println("3개의 숫자를 모두 맞히셨습니다! 게임 종료");
System.out.println("게임을 새로 시작하려면 1, 종료하려면 2를 입력하세요.");
int input = sc.nextInt();
if (input == 1) {
game();
}
if (input == 2) {
System.exit(0);
}
}
//볼,스트라이크,낫싱 판정
public static String judge(String userNumber, String computerNumber) {
int strike = 0;
int ball = 0;
String judgement = "";
if (userNumber.charAt(0) == computerNumber.charAt(1) || userNumber.charAt(0) == computerNumber.charAt(2)) {
ball++;
}
if (userNumber.charAt(1) == computerNumber.charAt(0) || userNumber.charAt(1) == computerNumber.charAt(2)) {
ball++;
}
if (userNumber.charAt(2) == computerNumber.charAt(0) || userNumber.charAt(2) == computerNumber.charAt(1)) {
ball++;
}
if (ball != 0) {
judgement += ball + "볼 ";
}
if (userNumber.charAt(0) == computerNumber.charAt(0)) {
strike++;
}
if (userNumber.charAt(1) == computerNumber.charAt(1)) {
strike++;
}
if (userNumber.charAt(2) == computerNumber.charAt(2)) {
strike++;
}
if (strike != 0) {
judgement += strike + "스트라이크";
}
if (strike == 3) {
}
if (ball == 0 && strike == 0) {
judgement = "낫싱";
}
return judgement;
}
//상대방(컴퓨터)의 수를 생성하는 메서드
public static String computer() {
String computerNumber = "";
List<Integer> numberList = new LinkedList<>();
for (int i = 1; i <= 9; i++) {
numberList.add(i);
}
while (true) {
int randomValue = (int)(Math.random() * 9 + 1);
if (numberList.contains(randomValue)) {
computerNumber += String.valueOf(randomValue);
numberList.remove(Integer.valueOf(randomValue));
}
if (computerNumber.length() == 3) {
// System.out.println("상대방 : " + computerNumber);
break;
}
}
return computerNumber;
}
}코드 분석
우선 위의 코드는 프로그래밍 요구사항을 만족시키지 못한 코드다.
MVC 방식이나 TDD와 같은 개념에 아직 친숙하지 않고, indent depth 3의 조건을 만족하기 위해서는 객체 단위로 더 분리해야 한다.
어떤 방식으로 야구를 구현할 지 기초적인 코드로 구조를 파악해보기 위해 작성했다.
아주 기초적인 코드였지만, 한 클래스 내에서 기능 단위 메서드 분리, 자료구조 등을 신경쓰려 노력했다.
내일은 객체지향의 사실과 오해라는 책을 읽고 MVC 개념에 대해서도 공부를 하여 어떻게 해야 해당 프로그래밍 요구사항을 만족시키며 개발을 할 수 있을지 공부할 계획이다.
참고자료
https://st-lab.tistory.com/101
[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]
www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어
st-lab.tistory.com