Meng's Algorithm

코딩테스트 지뢰찾기 문제

내 코드

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

class Main {
public static void main(String[] args) throws Exception {
    
	Scanner scanner = new Scanner(System.in);
	int count=0;
        
	while(true){
        
		int m = scanner.nextInt();
		int n = scanner.nextInt();
            
		if(m==0 && n==0) break;
            
		char mines[][]= new char[m][n];
            
		for(int i=0 ;i<m;i++){
			String st= scanner.next();
			for(int j=0; j<n;j++){
				mines[i][j]=st.charAt(j);
			}
		}
           
            
		count++;
		System.out.println("Field #"+count+ ":");
            
            
		for(int i=0; i<m;i++){
			for ( int j=0; j<n; j++){
                
				if(mines[i][j]=='*')
					System.out.print('*');
				else{
					int mine_num=0;
                        
					for(int ii=( (i>0) ? i-1:0 ) ; ii<i+2 && ii<m ;ii++)
						for(int jj= ( (j>0)? j-1:0) ; jj< j+2 && jj<n ; jj++ )
							if(mines[ii][jj]=='*') mine_num+=1;
                       
					System.out.print(mine_num);  
				}
			}
			System.out.println("");
		}
		System.out.println("");
	}
}

Code Number 9-18번째 줄.

이부분은 어렵지 않다. 이차원 동적 배열을 생성한뒤 사용자로부터 문제 포멧에 맞게 입력을 받아 minesweeper(지뢰)판을 형성한다. 

🔑 Key Point 🔑

for(int i=0; i<m;i++){
	for ( int j=0; j<n; j++){
		if(mines[i][j]=='*'){
			System.out.print('*');
		}
		else{
			int mine_num=0;
			for(int ii=( (i>0) ? i-1:0 ) ; ii<i+2 && ii<m ;ii++)
				for(int jj= ( (j>0)? j-1:0) ; jj< j+2 && jj<n ; jj++ )
					if(mines[ii][jj]=='*') mine_num+=1;
			System.out.print(mine_num);
		}
	}
	System.out.println("");
}

주목할 부분은 이 부분이다. 

생각의 발상은 지뢰가 아닌곳을 조회하게 될때 그 곳은 중심으로 동서남북 8개 칸에 지뢰가 몇개 있는지 세어 그것을 출력하는 것이다.  즉 3x3 작은 행렬을 중심만 빼고 조회하는 것과 같다. (중심을 조회해도 상관 x)

그래서 조회하는 도중에 3x3을 조회하는 2중 for문을 다시 넣어준다. 

3x3의 인덱스는 i-1 또는 j-1로 시작하면 될 것 같지만 0보다 작은 경우도 생각해야한다.

난해한것은 8개 칸을 조회하는 경우 인덱스가 0보다 작거나 m이나 n(지뢰판의 마지막수)을 넘어 서면 안된다는 것이다. 

따라서 삼항연산자를 이용하여 0보다 작으면 그냥 0부터 시작하게 해준다. 

그리고 중간 조건문에서 m이나 n보다 커지면 종료되게 설정해준다. 

이렇게 이 작은 행렬을 조회하다 지뢰가 있으면 mine_num (지뢰 개수 저장변수) 값을 올려준다.

📌 기억해야 할 부분

3x3 작은 행렬 만들기 

시작점을 3항연산자를 이용하기

[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문 한번만 써도 됨 🔑