문제
N개의 단어 중 어떤 단어와 그 뒤집은 단어가 모두 포함되어 있을 때, 해당 비밀번호의 길이와 가운데 글자를 출력하라. 단어 자체가 팰린드롬인 경우도 포함한다.
입력
첫째 줄에 N, 이후 N개의 단어가 주어진다.
출력
비밀번호의 길이와 가운데 글자를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 abc def ghi cba jkl | 3 b |
풀이
각 단어를 읽으며 뒤집은 문자열이 이전에 등장했는지 확인하고, 팰린드롬 여부도 검사한다.
- 각 단어를 읽을 때
StringBuffer.reverse()로 뒤집은 문자열을 만든다 - 뒤집은 문자열이 자기 자신(팰린드롬)이거나 이전에 읽은 단어와 같으면 비밀번호이다
- 비밀번호를 찾으면 길이와 가운데 글자(
length / 2위치)를 출력한다
핵심 아이디어: 단어를 뒤집어 이전 단어 목록과 비교하여 쌍을 찾는다.
코드
package day699;
import java.io.*;
public class Day695BOJ9933민균비밀 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
int N = Integer.parseInt(br.readLine());
String[] arr = new String[N];
String password = "";
boolean isFind = false;
String tmp;
for (int i = 0; i < N && !isFind; i++) {
arr[i] = br.readLine();
sb.append(arr[i]);
tmp = sb.reverse().toString();
for (int j = 0; j <= i; j++) {
if (arr[i].equals(tmp) || (j != i && arr[i].equals(arr[j]))) {
password = arr[i];
isFind = true;
break;
}
}
arr[i] = tmp;
sb.setLength(0);
}
System.out.println(password.length() + " " + password.charAt(password.length() / 2));
}
}복잡도
- 시간: O(N^2) — 각 단어마다 이전 단어들과 비교
- 공간: O(N) — 단어 배열 저장