[백준] 1394 암호 - JAVA

https://www.acmicpc.net/problem/1394

1394번: 암호

 

🫠 메모리 초과 늪에 빠진 문제.. 중복순열도 해보고, 규칙을 찾아 재귀로 연산도 해봤는데 암호에 사용할 수 있는 문자는 최대 100개 이고, 암호 길이는 최대 100만. 재귀가 스택에 차곡차곡.. 쌓이면서 메모리 초과가 난 것 같다. 그래서 반복문으로 해결! 

 

알고리즘

• 암호의 순서 규칙을 찾아서 반복문으로 계산하면 되는 문제. (규칙을 찾는게 관건인 것 같다!) 
• 규칙을 위해선 각 문자가 문자 집합의 몇번째에 있는지 정보가 필요한데, for문으로 일일히 위치를 찾으면 시간초과 날 수 있음 (최대 100번째에 있다고 할 때, 100*100만) 
• HashMap을 사용하여 각 문자의 순서를 저장해두고, 문자를 key값으로 하여 몇번째에 있는지 빠르게 조회 

 

 

🔎규칙 찾기

암호로 사용될 수 있는 문자 집합이 'abc' 인 경우 

• 컴퓨터의 암호가 1자리 수, 'b' : 문자 집합에서 b의 순서 =2 
• 컴퓨터의 암호가 2자리 수, 'ba' : (b의 순서 * 문자집합의 길이) + a의 순서 = 2*3 + 1 = 7 
• 컴퓨터의 암호가 3자리 수, 'bac' : (ba의 순서 * 문자집합의 길이) + c의 순서 = 7*3 + 3 = 24 
• 컴퓨터의 암호가 n자리수 : (n-1까지의 순서 * 문자집합의 길이) + n번째 수의 순서 

---

구현 과정

• Map<Character, Integer> : key = 문자, value = 해당 문자가 몇번째에 있는지 (1번째 부터 시작) 

 

1. 암호로 사용할 수 있는 문자를 입력받아 map 에 <문자, 순서> 를 저장한다. 

 

2. 컴퓨터의 암호의 가장 앞 문자부터 탐색하며, ((이전)결과*문자집합의 길이) + 현재 문자의 순서 를 계산하여 결과에 저장한다. 현재 결과는 다음 반복문의 이전결과가 된다. (코드에서 ans 값 갱신)

 

3. 계산할 때마다 900528로 나눈 값을 저장한다. (이 과정이 있기에 long 형이 아닌 int형으로 결과값 변수를 생성하였음) 

 

---

 

소스 코드 

import java.util.*;
/*
 * 재귀로 했더니 메모리초과 
 * 반복문으로 변경 -,-*/
public class Solution_BaekJoon_1394 {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		
		Map<Character, Integer> map = new HashMap<>();
		
		String word = sc.next();
		String key = sc.next(); 
		//<문자, 순서> map에 삽입 
		for(int i=0; i<word.length(); i++) {
			map.put(word.charAt(i), i+1); 
		}
		
		int ans=0; 
		for(int i=0; i<key.length(); i++) {
			char now =key.charAt(i);
			ans=(ans*word.length() + map.get(now))%900528; 
		} 
		
		System.out.println(ans);
	}//end of main
}//end of class