백준 1195 킥다운 python, java

기어의 길이가 100정도로 짧아서 기어를 한칸씩 움직여가며 확인해 보는 방법으로 풀었다.

📜 문제 바로 가기 : 킥다운

제출코드

파이썬

import sys
input = sys.stdin.readline

gearA = input().rstrip()
gearB = input().rstrip()

sumlen = len(gearA) + len(gearB)
ans = sumlen

ai, aj = len(gearA) -1, len(gearA) -1
bi, bj = 0, 0
while 1:

    for i in range(aj-ai + 1):
        if gearA[ai + i] == gearB[bi + i] and gearB[bi + i] == "2":
            break
    else:
        ans = min(ans, sumlen - (aj - ai + 1))
    
    ai -= 1
    if ai == -1:
        ai = 0
        bi += 1
    
    bj += 1
    if bj == len(gearB):
        bj = len(gearB) -1
        aj -= 1

    if ai > aj or bi > bj:
        break

print(ans)

자바

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

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

        String gearA = br.readLine();
        String gearB = br.readLine();

        int sumlen = gearA.length() + gearB.length();
        int ans = gearA.length() + gearB.length();

        int ai = gearA.length() -1;
        int aj = gearA.length() -1;
        int bi = 0;
        int bj = 0;

        while (true) {

            boolean for_else = true;
            for (int i = 0; i < aj-ai + 1; i++) {
                char a = gearA.charAt(ai + i);
                char b = gearB.charAt(bi + i);
                if (a == b && b == '2') {
                    for_else = false;
                    break;
                }
            }

            if (for_else == true) {
                ans = Math.min(ans, sumlen - (aj-ai + 1));
            }

            ai -= 1;
            if (ai == -1) {
                ai = 0;
                bi += 1;
            }

            bj += 1;
            if (bj == gearB.length()) {
                bj = gearB.length() -1;
                aj -= 1;
            }

            if (ai > aj || bi > bj) {
                break;
            }
        }

        System.out.println(ans);

    }

}

---

접근방법

gearB를 아래에 고정해두고 gearA를 맨 왼쪽부터 한칸씩 오른쪽으로 옮겨가며 비교한다.
ai, aj, bi, bj는 겹치는 부분의 인덱스값인데 gearA가 오른쪽으로 움직이는 방향이므로 A입장에서 B는 한칸씩 왼쪽으로 움직이게 된다. 따라서 각 차례마다 ai-=1, bj+=1 처리를 해주고 서로의 길이가 맞지 않아 넘어 갈 수 있는 부분 역시 처리해줬다.

참고로 기어가 맞물리지 않는 경우는 맞닿아 있는 부분이 "2"로 같은 경우이다.
"1"로 같은 경우는 체크하지 않는다.