TopCoder 문제로 연습해보는 알고리즘: 초급 (2) 전체 탐색 (1/2)

TopCoder 알고리즘 트레이닝
https://book.naver.com/bookdb/book_detail.nhn?bid=7333164

TopCoder 알고리즘 트레이닝

5장 전체 탐색의 1~5챕터까지 문제를 정리해 본 내용입니다

 

---

 

Exhaustive Search

어떻게 찾을 지는 알려주지 않고 답을 찾으라고 하면 일단 전체 탐색!

1. InterestingParty

가장 많은 것을 답하라는 문제를 보면 직감적으로 전체 탐색을 사용해야 한다

Problem

i번째 친구가 흥미있어하는 화제는 first[i]와 second[i]
String[] first
String[] second

return int of maximum friend

Example Data

0)
first = {"fishing", "gardening", "swimming", "fishing"}
second = {"hunting", "fishing", "fishing", "biting"}
returns: 4

1)
first = {"variety", "diversity", "loquacity", "courtesy"}
second = {"talking", "speaking", "discussion", "meeting"}
returns: 1

2)
first = {"snakes", "programming", "cobra", "monty"}
second = {"python", "python", "anaconda", "python"}
returns: 3

Solve

1. for 반복문으로 전체 탐색

1. 관심사별로 중복되는 관심사가 있는지 fisrt, second 배열을 전체 탐색한다
    - 사람마다 first, second 관심사는 중복되는 것이 아니다

public class InterestingParty{
    public static int interestingPartyFor(String[] first, String[] second){

        int ret = 0;

        for(int i=0; i<first.length; i++){
            String fsubj = first[i];
            String ssubj = second[i];
            int fsame = 0;
            int ssame = 0;
            for (int j=0; j<first.length; j++){
                if (first[j].equals(fsubj)) fsame ++;
                if (second[j].equals(fsubj)) fsame ++;
                if (first[j].equals(ssubj)) ssame ++;
                if (second[j].equals(ssubj)) ssame ++;
            }
            ret = Math.max(ret, fsame);
            ret = Math.max(ret, ssame);
        }
        return ret;
    }
}

2. 연관 배열 HashMap으로 전체 탐색

2. 모든 관심사를 Map의 Key로 등록해놓고 등장 횟수를 센다
    - HashMap은 중복 키를 허용하지 않는다
    - 등장 수를 Value로 사용한다

import java.util.*;
public class InterestingParty{

    private static int interestingPartyHm(String[] first, String[] second) {

        int ret=0;
        HashMap<String, Integer> hm = new HashMap<String, Integer>();

                //각 키에 대한 카운트를 초기화
        for (int i=0; i<first.length; i++){
            hm.put(first[i],0);
            hm.put(second[i],0);
        }        

        for (int i=0; i<first.length; i++){
            hm.put(first[i], hm.get(first[i])+1);
            hm.put(second[i], hm.get(second[i])+1);
        }

        for (String key: hm.keySet()){
            ret = Math.max(hm.get(key), ret);
        }

        return ret;
    }

2. Cryptography

Problem

입력 리스트에서 1개의 값을 +1 증가시킬 때, 모든 숫자 곱이 가장 커지도록 함

int[] numbers
returns: the maximum product

Example Data

0)
numbers = {1, 2, 3}
returns: 12

1)
numbers = {1, 3, 2, 1, 1, 3}
returns: 36

2)
numbers = {1000, 999, 998, 997, 996, 995}
returns: 986074810223904000

3)
numbers = {1, 1, 1, 1}
returns: 2

Solve

1. 전체 탐색

모든 숫자에 +1한 뒤 곱을 계산해 본 후, 곱의 최댓값을 리턴

import java.util.*;

public class Cryptography{

    public static long cryptographyFor(int[] numbers) {
        long ret=0;
        for(int i=0; i<numbers.length; i++){
            long tmp=1;
            for(int j=0; j<numbers.length;j++){
                if(i==j) {
                    tmp *= (numbers[j]+1);
                } else {
                    tmp *= numbers[j];
                }
            }
            ret = Math.max(ret, tmp);
        }

        return ret;
    }
}

2. 정렬을 이용하여 최솟값을 찾기

가장 작은 수를 찾아서 +1한 뒤 모든 수의 곱을 리턴  → n이 작으면 작을수록 전체 수의 곱한 값은 커짐

import java.util.*;

public class Cryptography{

    private static long cryptographyMin(int[] numbers) {
        long ret=1;
        Arrays.sort(numbers);
        numbers[0]++;
        for (int n: numbers){
            ret *= n;
        }

        return ret;
    }

3. InterestingDigits

Problem

base 진법이 주어졌을 때, 0, 1을 제외한 n에 대해
- n의 배수의 각 자릿수의 총합은 또다른 n의 배수인 수의 배열을 리턴
- 확인해 볼 n의 배수는 4자리 미만으로 제한

base: int n (n진법)
returns: int[]

Example Data

0)
base: 10
retruns: {3, 9}

1)
base: 3
retruns: {2}

2)
base: 9
retruns: {2, 4, 8}

3)
base: 26
retruns: {5, 25}

Solve

n진법을 10진수로 생각하는 방법 ⇒ ... + i_n_n + j\*n + k  
최대 3자리의 수까지만 제한되어 있으므로 0~NNN의 수를 전체 탐색하면 된다

import java.util.*;

public class InterestingDigits{

    public static int[] interestingDigits (int base){
        //요소를 하나씩 추가해야 하므로 List 사용(add 사용가능) <-> 배열은 정해진 크기여야 함
        ArrayList<Integer> ls = new ArrayList<>();

        for(int i = 2; i<= base; i++){
        	//일단 i에는 반례가 없다고 생각하고 시작함
            boolean chk = true; 
            for(int k1=0; k1<=base ; k1++){
                for(int k2=0; k2<=base ; k2++){
                    for(int k3=0; k3<=base ; k3++){
                        if((k1*base*base + k2*base + k3)%i == 0 
                            && (k1 + k2 + k3)%i !=0){
                            //수 자체는 i의 배수라 해도
                            //각 자릿수의 합이 i의 배수가 아니라면(반례발생)
                            //i는 조건에 완전히 부합하는 수가 아님
                            
                            //반례가 하나라도 발견되면 i의 배수에 대해 더이상 탐색할 필요가 없음
                            chk = false; 
                            break;
                        }                         
                    }
                    if(!chk) break; //chk가 false라면 탐색 중지를 위해 break 
                }
                if(!chk) break; //chk가 false라면 탐색 중지를 위해 break 
            }
            if(chk) ls.add(i); 
            // 반례가 없는(조건에 부합하는) i라면 해당 라인이 실행되어 i가 리스트에 추가됨
        }

        //답을 리턴하기 위해 배열로 옮긴다
        int[] ret = new int[ls.size()];
        for(int i=0; i<ls.size(); i++){
            ret[i] = ls.get(i);
        }
        return ret;
    }
}

4. 회문 ThePalindrome

Problem

회문은 앞으로 읽으나 뒤에서 읽으나 같은 대칭형 단어
임의의 문자열 s뒤에 0+개의 문자를 추가해 회문을 생성하기

String s
return: int length of Palindrome string

Example Data

0)
s = "abab"
returns: 5

1)
s = "abacaba"
returns: 7

2)
s = "qwerty"
returns: 11

3)
s = "abdfhdyrbdbsdfghjkllkjhgfds"
returns: 38

Solve

길이가 n인 문자열에 길이 a의 문자열을 더해서 회문을 만든다고 할 때

0번지 문자와 끝번지 문자를 비교하는데

1) 같으면 → 다음 문자들을 비교한다: i번지 문자와 (끝번지-i)번지 문자를 비교하는 것임  
2) 다르면 → 회문에 필요한 문자 하나를 끝에 추가하고(lastIdx++, a++) 처음부터 다시 비교한다

주의할 점은 처음부터 다시 비교할 때 임의로 붙인 글자와 대칭여부를 검사하지 않는다는 점  
→ (비교 과정을 이미 처리한) 추가한 글자수(a)만큼은 건너뛰고 비교를 시작한다

public class ThePalindrome{
    public static int find(String s){
        int lastidx = s.length()-1; //마지막 인덱스
        int add = 0; //추가한 문자의 개수를 count
        for (int i=0; i<s.length(); i++){
            if( i>=add //이미 비교 처리한 문자를 다시 비교하지 않는다
                && s.charAt(i) != s.charAt(lastidx-i)){
                   //끝에서 동일한 거리에 있는 문자(대칭 위치)가 다르다면 
                    lastidx++; //끝에 필요한 문자를 추가하고
                    add++; //추가한 문자 수를 기억시킨다
            }
        }
        int ret = lastidx+1; //문자열의 총 길이는 1-base
        return ret;
    }
}

Tips

문제 이해를 정확하게 하기 위해서는 그림으로 나타내보는 것이 좋다  
관계에 대한 이해가 어려우면 원과 선으로 연결하여 표현해보며 정확하게 이해를 해야 함

5. FriendScore

Problem

친구의 수 = 서로 친구인 사람 수 + 공통 친구가 한명이라도 있는 사람 수

String[] friends
friends[i]의 j번째 글자가 'Y'라면 서로 친구, 'N'라면 친구가 아님
return 가장 인기 있는 사람의 친구 수

Example Data

0)
friends = { "NNN",
            "NNN",
            "NNN" }
returns: 0

1)
friends = { "NYY",
            "YNY",
            "YYN" }
returns: 2

2)
friends = { "NYNNN",
            "YNYNN",
            "NYNYN",
            "NNYNY",
            "NNNYN" }
returns: 4

3)
friends = { "NNNNYNNNNN",
            "NNNNYNYYNN",
            "NNNYYYNNNN",
            "NNYNNNNNNN",
            "YYYNNNNNNY",
            "NNYNNNNNYN",
            "NYNNNNNYNN",
            "NYNNNNYNNN",
            "NNNNNYNNNN",
            "NNNNYNNNNN" }
returns: 8

Solve

i==j 일 때는 서로 친구인 사람을 중복 카운트하게 되므로 건너뛰어야 함

friends[i]의 i번째가 'N'일 때 → friends[i]의 k번째가 'Y'인 사람 → friends[k]의 i번째가 'Y'  
		    friends[i]의 k번째가 'Y'인 사람 → friends[k]의 i번째가 'Y'
                	//이 부분은 'Y'일 때 이미 카운트가 된 상태

예를 들어 friends[2] "NYNYN"를 탐색할 때:  
N ---> i= 2, j= 0, k= 1  
Y ---> i= 2, j= 1  
N ---------------> i= 2, j= 2, k= 1 //(i=j=2) cnt++가 중복 호출됨 
N ---------------> i= 2, j= 2, k= 3 //(i=j=2) cnt++가 중복 호출됨 
Y ---> i= 2, j= 3  
N ---> i= 2, j= 4, k= 3

public class FriendScore{  
    private static int highestScore(String\[\] friends) {

        int ans=0;
        for(int i=0; i<friends.length; i++){
            int cnt = 0;
            for(int j=0; j<friends[i].length(); j++){
                if(i==j) continue;
                if(friends[i].charAt(j)=='Y')  cnt++;
                else{
                    for(int k=0; k<friends[j].length(); k++){
                        if(friends[j].charAt(k) == 'Y' 
                           && friends[k].charAt(i)=='Y') {//cnt++;
                            cnt++;
                            break; 
                            //공통인 친구가 단 한명이라도 있으면 간접 친구임!
                            //더이상 탐색할 필요 없으므로 break
                        }
                    }
                }
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}