[알고리즘 문제] 백준9933 - 민균이의 비밀번호

문제 자체는 생각보다 그렇게 어렵지 않다. 

텍스트 파일에는 여러 단어가 들어가 있는데, 이 들중에 좌우반전이 되는 한쌍의 단어가 있으면 그 값이 비밀번호가 되고 단어의 길이와 단어의 가운데 값을 출력하면 되는 문제이다.

 

이 문제를 듣고 map을 쓰면 되겠다는 생각이 들었다.

 

문제 해결 방법은,

1. 먼저 단어를 좌우반전("asdfg" -> "gfdsa"가 map에 존재하는지 검사한다)

2. 있으면 답을 출력하고, 없으면 좌우 반전한 값을 map에 넣는다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Map<String, Integer> map = new HashMap<String, Integer>();
        String str;

        for (int i = 0; i < N; i++) {

            str = sc.next();

            if (str.equals(generateReverseString(str)) || map.get(str) != null) { // str이 팰린드롭이거나, 반전되는 값이 이미 map에 있으면
                System.out.print(str.length() + " ");
                System.out.println(str.charAt(str.length() / 2));
                break;
            }

            map.put(generateReverseString(str), 1);
        }
    }

    static String generateReverseString(String str) { // 입력받은 단어를 좌우반전하여 return

        char[] arr = str.toCharArray();
        int start = 0;
        int end = arr.length - 1;
        char c;

        while (start < end) {
            c = arr[start];
            arr[start] = arr[end];
            arr[end] = c;
            start++;
            end--;
        }
        return new String(arr);
    }
}

if문의 조건을 살펴볼 필요가 있는데, 아래의 두가지 조건이 true면 결과를 출력한다.

1. 팰린드롬 : 애초에 입력받은 문자가 좌우반전을 해도 같은 단어인 경우, ex) asdsa, qqwewqq

2. map에 str에 해당하는 value가 널이 아닌 경우 : for문이 끝날 때 마다 해당 단어의 좌우반전 단어가 저장되므로, null이 아니란 말은 현재 단어의 좌우반전인 단어가 존재한다는 의미,