★ solved.ac 난이도 : G3
(2021년 12월 29일 기준)
[문제 링크]
15551번: if 3
다음 프로그램을 실행시켰을 때, "true"를 출력하는 길이가 N인 문자열 a, b 를 찾는 프로그램을 작성하시오. import java.util.*; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System
www.acmicpc.net
[문제 분석]
Java에서 hashcode()가 같고, 길이도 같으면서 서로 다른 두 문자열을 찾는 문제
(hashcode의 원리도 알아야겠죠?)
[풀이]
이번에는 Java의 hashcode() 함수의 원리를 알아야 합니다.
hashcode() 함수의 정의는,
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] (s : 문자열, n : 문자열의 길이)
입니다. 여기에서 잘 살펴보시면, hashcode()의 반환 값에서 s[n-1]의 아스키코드 값을 뺀 수가 31로 나누어 떨어진다는 것을 알 수 있습니다.
(실제로 Java에서는 수가 너무 크면 int 형으로 돌려줍니다.)
이를 적절히 활용해서, 두 개의 서로 다른 문자열의 hashcode() 반환 값을 같게 만들어보겠습니다.
(여기에서 문자열 2개를 각각 s1, s2라고 하겠습니다. 또, 문자열의 길이를 n이라고 하겠습니다.)
여기에서 제일 마지막 두 개의 문자에 주목하면,
s2[n-2] = s1[n-2]-1이 되도록 설정하고, s1의 마지막 두 문자는 같은 문자로 가정하겠습니다. (나머지 앞 문자들은 무시하셔도 되지만, 두 개가 같아야 합니다.)
(s1[n-1] = s1[n-2])
또, s2[n-1] = s1[n-1]+31로 두겠습니다. 이렇게 되면, s1[n-2]*31+s1[n-1]과 s2[n-2]*31+s2[n-1]을 비교하게 됩니다.
(여기에서 S = s1[n-2]로 두겠습니다.)
그러면, s1.hashcode() = s2.hashcode()가 31S+S = 31(S-1)+S+31 = 31S-31+S+31 = 31S+S가 됩니다.
결과적으로, 두 문자열의 hashcode() 반환 값이 같아지게 됩니다.
이를 활용한 예시 정답을 알려드리자면,
s1의 마지막 두 문자는 '>>', s2의 마지막 2문자는 '=]'로 설정하였습니다. (단, 나머지 문자들과 길이가 모두 같아야 합니다.)
마지막 부분에 예시 소스(Java)를 첨부하겠습니다.
저도 처음에는 너무 어려워 보였지만, 원리를 알고 보니 풀 만 했습니다.
어려운 글 읽어주셔서 감사합니다~! (꾸벅...)
[참고 자료 (Oracle Java Docs 발췌)]
[소스 코드]
공유 소스 보기
www.acmicpc.net
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)