Meng's Algorithm

[Java] 암호 깨기 II (Crypt kicker II) - UVa 850문제

onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=791

문제 설명

내 코드

import java.io.*;
import java.util.*;

class Main {

	
	public static void main(String[] args) throws Exception {
		Scanner scanner = new Scanner(System.in);
		
		String standard = "the quick brown fox jumps over the lazy dog";

		
		
		int n = scanner.nextInt();
		scanner.nextLine();
		scanner.nextLine();	
		
		
		for(int i=0; i<n ; i++){
			TreeMap<Character,Character> rule = new TreeMap<Character,Character>();
			ArrayList<String> cryptlist = new ArrayList<String>();
			
			//입력하기
			while(scanner.hasNextLine()) {
				String input = scanner.nextLine();
				if(input.equals("")){
					break;
				}	
				cryptlist.add(input);	
			}
			
			
			//해당 암호 해쉬에 저장
			for(String str: cryptlist){
				if(str.length()==standard.length()){
					TreeMap<Character,Character> rule_copy = new TreeMap<Character,Character>();
					for(int j=0 ; j<str.length();j++){
						rule_copy.put(str.charAt(j), standard.charAt(j));
					}
					String result="";
					for(int j=0; j<str.length(); j++)
						result+=rule_copy.get(str.charAt(j));
						
						
					if(!result.equals(standard)) continue;
					else {
						
						rule.putAll(rule_copy); 
						break;
					}		 
					
				}
			}
		
			
			//출력하기
			String no_solution="";
			for(String str: cryptlist){
				String result="";
				for(int j=0; j<str.length(); j++){
					if(rule.get(str.charAt(j))==null){
						no_solution = "No solution.";
						break;
					}
					result+=rule.get(str.charAt(j));
				}
				if(no_solution.equals("No solution.")){
						break;
				}
				System.out.println(result);
			}
			if(no_solution.equals("No solution.")){
				System.out.println(no_solution);
			}
			System.out.println("");
			
		}
		
	}
}

🔑 Key Point 🔑

//해당 암호 해쉬에 저장
for(String str: cryptlist){
	if(str.length()==standard.length()){
		TreeMap<Character,Character> rule_copy = new TreeMap<Character,Character>();
		for(int j=0 ; j<str.length();j++){
			rule_copy.put(str.charAt(j), standard.charAt(j));
		}
		String result="";
		for(int j=0; j<str.length(); j++)
			result+=rule_copy.get(str.charAt(j));
						
		if(result.equals(standard)) {
			rule.putAll(rule_copy); 
			break;
		}			
	}
}

검사 str이 plain text랑 길이가 같으면 임시 TreeMap에 암호 대응을하여 다시 그 암호를 넣었을때 평서문이 나오면 기준 Map 완성 . 암호 Key value를 대응한 Map을 통하여 모든 input string 번역하여 출력!

굳이 좀더 빠르게 하려고 자꾸 if문을 남발할 필요가 없다 그러다가 알고리즘 짜는데 시간이 너무 오래걸림...

프로그래머스 42578번 위장 HashMap - Level2

https://programmers.co.kr/learn/courses/30/lessons/42578

내 코드(틀린코드)

#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

int solution(vector<vector<string>> clothes) {

    int answer = 1;
   
    map<string, int> m1;
    
    for(int i=0; i<clothes.size();i++){
        m1[clothes[i][1]]+=1;
    }
    
    int mapsize=m1.size();
    
    for(int i=0;i<m1.size();i++){
        answer *= (m1[clothes[i][1]]+1);
    }
    
    return answer-1;
}

이 문제의 핵심은 각각 옷의 종류의 가짓수에 대하여 포함하냐 포함하지 않는냐의 경우를 곱하는 것의 시그마이다.

• 예제 1번

[[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]

이경우 headgear의 가짓수는 2가지 eyewear의 가짓수는 1가지 이다. 

headgear를 포함하거나 안포함 되는 경우 : 총 3가지

eyewear를 포함하거나 안포함 되는 경우 : 총 2가지

총 경우의수 : 5가지

이 핵심을 파악해야되는데 고딩때 경우의수를 헷갈려 삽질을 했다..

그리고 고민끝에 핵심은 파악하여 답을 제출하였으나 결과는 오답이였다.

틀린이유는 우선,

맨밑 for문에서 i를 이용하여 clothes[i][1]이부분을 돌리는것은 잘못됐다. 

해쉬맵 m1의 인자 하나하나를 조회해야하는데 vector clothes를 조회하게 해두었기 때문에 틀린답이 나온다.

맞는 풀이

#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    map<string, int> m1;
    
    for(int i=0; i<clothes.size();i++){
        m1[clothes[i][1]]+=1;
    }
    
    map<string, int>::iterator it;
    for(it =m1.begin(); it!=m1.end();it++)
        answer*=it->second+1;
    
    
    return answer-1;
}

따라서 해쉬맵의 요소들을 접근하기 위해서는 iterator를 이용하는 것!

해쉬맵은 for문에서 i로 접근하기가 까다롭다. 

the shortest code

#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> m1;
    
    for(auto ele: clothes){
        m1[ele[1]]+=1;
    }    
  
    for(auto it =m1.begin(); it!=m1.end();it++)
        answer*=it->second+1;
        
    return answer-1;
}

iterator를 선언해주지않고 auto를 이용하면 더 간단한 문이 나올 수 있다.

🔑 Key Point 🔑

Haspmap을 조회하기 위해서는 Iterator를 사용해야된다 !!

각각 옷의 종류의 가짓수마다 포함하냐 포함하지 않는냐의 경우의 수를 곱하는 것들을 다 더한다

프로그래머스 42577번 전화번호목록

https://programmers.co.kr/learn/courses/30/lessons/42577

Hash Map - LEVEL 2

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를
그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

내코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {

    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    
    for(int i=0; i<phone_book.size(); i++){
        for(int j=i+1; j<phone_book.size();j++){
        
            if ( phone_book[i].compare(phone_book[j].substr(0 , phone_book[i].size())) == 0)
               return false;
               
        }
    }
    
    return answer;
    
}

Better way

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool solution(vector<string> phoneBook) {

    bool answer = true;
    sort(phoneBook.begin(), phoneBook.end());
    
    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
    
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
        
    }
    
    return answer;
    
}

리뷰

<Algorithm> sort.
<String> substr. 이용

🔑이미 지나온 길을 확인하지 않기 때문에 For문 한번만 써도 됨 🔑