백준 1195 자바 - 킥다운 (BOJ 1195 JAVA)

문제 : https://www.acmicpc.net/problem/1195

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1195.java

 

  순전히 구현력에 따라 풀 수 있고 없고가 갈리는 문제이다.

길이가 최대 100이므로 그냥 brute force로 모든 경우를 시뮬레이션 돌려도 전혀 문제가 없다.

 

1. 일단 최대로 나올 수 있는 경우는 예를들어 모든 부분이 '이'로 되어 있다면 서로 겹칠 수 없으니 두 문자열의 합이 일단 최대치이다. 그 후에, 이런 모양부터 시작해서 하나하나 직접 비교해보는 것이다. 이 때 '이'와 '이'가 만나는 경우는 맞물릴 수 없는 경우이므로 무시한다.

...

--(A)--

 

...

이런식으로 모든 경우를 다 비교해보면 된다!

구현 아이디어 자체는 쉬우니, 이제 맞고 틀리고는 개인의 구현력에 달렸다.

 

참고로 코드에서는 find 함수를 2번 호출하면서 문자열을 변경하는데, 위 이미지 중 (A) 부분까지만 진행하고 그 이하 부분은 서로 문자열 순서를 바꿔서 (A) 이전의 과정을 반복하는 것과 동일하기 때문이다. 코드가 더 복잡해질 수 있으니 반으로 쪼갠것이다.

즉, (A) 부분 위까지 진행 후에

...

이렇게 아래위를 바꿔서 진행한것이다.

 

 

그리고 어차피 길이가 최대 100개라 수식으로 짜기보다는 그냥 LinkedList에 빈 공간을 0으로 채우는 방식으로 짰다.

즉,  아래와 같이 비교중이라면..

둘이 길이를 '0'을 앞뒤로 추가해서 아래와 같이 변경한 후 비교하는 식으로 진행했다.