99클럽 코테 스터디 9일차 TIL + 민균이의비밀번호

- 오늘의 학습 키워드 : HashSet, StringBuilder().reverse(),

 

문제

## [BOJ 9933] 민균이의 비밀번호 ### 문제 창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다. 파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다. 예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다. 알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다. 민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오.

 

### 입력 첫째 줄에 단어의 수 N (2 ≤ N ≤ 100)이 주어진다. 다음 N개 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 홀수이다.

 

### 출력 첫째 줄에 비밀번호의 길이와 가운데 글자를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

 

### 예제 입력 1

4
las
god
psala
sal

 

출력 1

3 a

 

### 예제 입력 2

4
kisik
ptq
tttrp
tulipan

 

출력 2

5 s

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

StringBuilder를 사용해서 역으로 만든 배열을 만들어서 비교하였다

풀이 방식

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

public class BOJ9933_민균이의비밀번호 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        String[] password = new String[N];

        for(int i =0 ; i < N; i++){
            st = new StringTokenizer(br.readLine());
            password[i] = st.nextToken();
        }

        for(int i =0 ; i < N; i++){
            String reversePassword = new StringBuilder(password[i]).reverse().toString();
            for(int j = 0; j < N; j++){
                if(password[j].equals(reversePassword)){
                    System.out.println(password[i].length() + " " + password[i].charAt((password[i].length() - 1 )/2));
                    return;
                }
            }
        }
    }
}

 

  - 어떻게 해결했는지

 

그런데 이렇게 하면 O(N^2)으로 for문을 두번 사용하게 된다.

이보다 좋은 방식은 HashSet을 이용한 방식으로 O(N)으로 해결이 가능하다

풀이

public class BOJ9933_민균이의비밀번호 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        String[] passwords = new String[N];
        Set<String> set = new HashSet<>();

        for(int i =0 ; i < N; i++){
            st = new StringTokenizer(br.readLine());
            passwords[i] = st.nextToken();
            set.add(passwords[i]);
        }

        for(String password : passwords){
            String reversePassword = new StringBuilder(password).reverse().toString();
            if(set.contains(reversePassword)){
                System.out.println(password.length() + " " + password.charAt((password.length() - 1 )/2));
                return;
            }
        }
    }
}

 

메모리와 시간은 거의 비슷하게 나오지만
이후에 큰 값이 들어올 경우 밑의 방식이 더 유용해 보임
또한, 여기서는 set으로 풀었지만

map을 사용해서 containsKey를 활용해서 풀어도 마찬가지의 답을 얻을 수 있을 것 같다