뚝딱뚝딱

깃허브에서 커밋 후, 오랜만에 잔디 현황 확인할 겸 프로필을 눌렀는데..

내 초록초록 잔디는 어디가고??? 노랑노랑.. 심지어는 까맣기까지하다

뭐지?? 색깔을 바꿀 수 있는 건 알고 있었는데, 난 아무 설정도 안했는데 색이 변해있었다.

한참을 생각하다가 구글에 검색해보니.. 

할로윈 이벤트 였던 것!! 

지금보니 아래에 조그맣게 Happy Halloween! 이라고 적혀있네..

무료했던 하루에 조금의 재미를 느낀 것 같다!

여행 경로

💡문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.


주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

딱 보자마자 모든 경로를 탐색해야 하기 때문에, dfs를 사용해야 한다는 점은 알아야 한다.

그런데, 문제를 보면, 여러개의 경로가 나올 시 사전 순으로 앞서는 경로를 return해야 한다.

여러개의 경로를 구해두고 그 중에서 알파벳 순으로 먼저인 경로가 앞으로 오도록 정렬한 후 맨 앞에 있는 것을 선택해야한다.

따라서 이 문제는 BFS도 적용해야 한다.(위에서 말한 바와 같이 정렬만 하면 되긴 한다)

다음과 같은 단계로 진행할 수 있다.

1. 여러가지 경로 자체를 리스트 형태로 여러개 저장할 수 있는 이중 리스트를 생성하자.

static List<List<String>> answerList;

솔루션 함수 밖에서 생성해주었다.

2. 방문 여부를 위한 boolean타입 배열을 선언하자.

static boolean[] visited;

이 역시 솔루션 함수 밖에서 생성해주었다.

3. 이제 이중리스트에 ArrayList로 동적 할당해주고, 방문 배열 역시 tickets배열 크기만큼 동적 할당하자.

answerList = new ArrayList<>();
visited = new boolean[tickets.length];

솔루션 함수 내로 들어왔다.

4. 이제 tickets 배열을 순회하면서 출발지가 "ICN"인지 확인하자.

for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {

5. 조건에 만족한다면, 경로를 저장하기 위한 list를 생성하고 동적할당한다. 그리고 출발지인 "ICN"을 담는다.

현재 노드를 방문한 것이므로 visited[i]를 true로 하고, 리스트에는 해당 노드의 도착지를 저장한다.

List<String> list = new ArrayList<>();
list.add("ICN");
visited[i] = true;
list.add(tickets[i][1]);

6. 도착지인 tickets[i][1]이 다시 출발지가 되어 다음 노드를 방문해야 한다. 따라서 아직 방문하지 않은 노드들 중 출발지가 tickets[i][1]인 노드를 찾아 위의 과정을 반복하자. 이를 dfs함수에 구현하자.

public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }

   - dfs함수는 tickets와 출발지 인덱스, 진행중이던 경로 list에 대한 정보를 받는다.

   - 만약 현재 list의 크기가 tickets의 길이보다 1 큰 것과 같다면, 모든 tickets를 고려한 것이기 때문에, 이중 리스트인 answerList에 list를 넣는다. = 경로 모음집에 경로를 하나 추가한 것이다.

   - 아직 tickets를 다 방문하지 않았다면, 모든 노드에 대해서, 아직 방문하지 않았고, 인자로 받은 출발지를 갖는 노드를 방문한다.

   - 역시 list에 방문한 노드의 도착지를 넣어준다 (출발지는 이전 단계에서의 도착지로, 이미 넣어졌기 때문이다)

   - 그리고 그 도착지를 기점으로 다시 dfs를 호출해서 반복되도록 해준다.

   - 다 돌고 나서 다시 다른 경로를 순회하기 위해 다시 visited[i]를 false로 바꾸어주는 단계를 잊어선 안된다.

   - 동일한 원리로 list에서도 제거해준다.

7. 다시 solution함수로 돌아오자. 방금 전까지 dfs가 어떻게 돌아가는지를 확인하였다. 이 dfs를 최초로 불러주자.

dfs(tickets, i, list);
visited[i] = false;

   - 여기에서도 dfs를 돌고난 후 혹시 다른 경로를 먼저 방문했을 시를 고려해서 visited[i]를 false로 바꿔주는 것을 잊지 말자.

8. 이렇게 가능한 경로를 다 구했으면, List에 들어있는 경로들을 알파벳 순으로 정렬해주자.

Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
});

   - Collections의 sort함수를 사용할건데, 람다식을 이용해서 모든 경로에 대해 각각의 첫번째부터 끝번째 노드까지 알파벳 순을 비교해서 빠른것이 앞으로 오도록 설계한다.

9. 이제 answerList의 맨 첫번째 경로가 asnwer가 될 것이다. 이 경로 하나를 가져오기 위해 answer를 list로 선언하고 answerList의 0번째 리스트를 가져와 할당한다. 그리고 list의 toArray함수를 통해 answer를 배열 형태로 반환하도록 한다.

List<String> answer = answerList.get(0);

return answer.toArray(new String[answer.size()]);

이렇게 해서 모든 경로를 탐색하고, 정렬을 통해 알파벳 순으로 가장 빠른 경로를 찾아낼 수 있었다.

전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    static List<List<String>> answerList;
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        answerList = new ArrayList<>();
        visited = new boolean[tickets.length];
        
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {
                List<String> list = new ArrayList<>();
                list.add("ICN");
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
            }
        }
        
        // 결과로 반환할 경로 선택 (알파벳 순서가 앞서는 경로)
        Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
        });

        List<String> answer = answerList.get(0);

        return answer.toArray(new String[answer.size()]);
    }
    
    public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }
}

이제 DFS문제를 3-4번 풀어보니, 어느정도 감이오고, 문제를 읽어보면 DFS로 풀어야하는지 알 수 있게 되었다.

확실히 BFS보다 DFS의 비중이 더 많은 것 같기도 하다.

그리고 자바 문법은 더 꼼꼼히 살펴보아야겠다!!

📌 날짜 : 2023/10/21 2PM~5PM

코딩테스트를 준비하면서 알고리즘 문제를 해결하는 것에 막 재미를 붙일 시기였다.

올해 ICPC 프로그래밍 대회가 가을에 있다고 하였고, 재미있게 참여할 수 있을 것 같아서 한 번 도전해 보았다.

ICPC대회는 본선이 있기 전에, 예선을 치루고, 예선을 통과한 팀만 본선에 진출할 수 있다.

대학 동기들과 셋이서 as_PA라는 팀으로 출전했다.

예선 때 참고할 수 있는 팀노트를 25장까지 허용한다. 우리는 헷갈리거나, 자주 나올 것 같은 참고할 만한 알고리즘들을 정리해서 갔다. (사실 대회때는 오히려 문제에 집중하느라 팀노트를 거의 안보게 된다.) 

셋 다 평소에 백준이나 프로그래머스 등의 프로그래밍 문제 플랫폼으로 열심히 준비해왔었기 때문에, 대회 또한 부담없이 즐기고 오기로 했다.

총 3시간 동안 9문제?10문제?를 해결하는데, 문제는 A부터 알파벳 순이다.

언어는 C, C++, JAVA 중에서 하나를 선택해 해결해야 하고, 우리는 C++을 선택했다.

참고로 시험 문제는 거의 영어로 출제된다.

문제를 풀 때 쓸 수 있는 여백의 종이를 하나씩 나눠 주신다.(우리는 팀 노트 뒷부분이 여백이라, 이것도 사용하긴 했다)

시험이 시작되고, 문제를 하나씩 살펴보았고, 간단히 해결할 수 있는 문제부터 접근했다.

D번 문제

D번을 먼저 풀어보았는데, 주어진 범위내의 펠린드롬 수의 개수를 구하는 문제였다.

1.무식하게 접근

일단은 무식하게 접근했다.

[무식하게 접근한 방법]
주어진 범위내의 모든 숫자를 for문으로 돌아가면서 모두 탐색하도록 하였고, 문자열의 맨 앞과 맨 뒤가 동일한지를 비교해가도록, string을 이용해 숫자를 문자열로 바꿔서 문자열 비교 방법으로 사용했다.
while문을 이용해서 문자열이 1보다 크면, 앞 뒤 쌍이 있는 것이기 때문에 비교하고, 동일하면 그 쌍을 문자열에서 자른다. 이를 while문 안에서 반복하고, 문자열이 다르면 bool 타입 변수를 false로 변경하고(=현재 수는 펠린드롬 수가 아니다) while문을 빠져나오도록 break처리하였다.
만약 while문을 끝까지 잘 돌았다면 bool 타입 변수가 true일 것이기 때문에 펠린드롬 수로 카운트한다.

[결과]
테스트 케이스는 모두 통과한다. 다른 값을 집어 넣어 봤을때에도 문제가 없다.
그런데, 자꾸 결과가 wrong이라고 떴다.
큰 수를 집어 넣어보니 실행 시간이 1초가 넘는다.
결국 제한시간 1초를 고려하지 못해 효율성 면에서 떨어지는 것을 확인하였다.

시간을 줄이기 위해서..

쓸데 없는 계산을 줄여야 했다.

현재 코드는 for과 while문의 2중 루프이기 때문에 n*(문자열 길이)의 복잡도를 가진다. n은 최대 10^10이었기 때문에 엄청난 시간복잡도를 가질 수 밖에 없다.

2. 규칙에 따른 접근

따라서 우리는 n의 범위에 따른 펠린드롬 수의 개수에 대한 규칙을 찾아냈다.

바로 n이 몇자리 수인지에 따른 규칙이다.

len=n의 자리수
1~n자리수의 제일 큰수 중 펠린드롬 수의 개수 = 9*10^(len/2)

이렇게 되면, 굳이 1부터 다 순회하면서 비교할 필요없이, n의 자리수보다 1작은 자리수까지의 펠린드롬 수는 위의 규칙을 통해 미리 카운트 함으로써 계산 횟수를 확실히 줄이고자 하였다.

그리고 나머지 n자리수의 시작~n까지의 수는 앞에서 했던 방식으로 문자열을 비교하도록 하였다.

테스트 케이스를 모두 만족하였으나, 이상하게 예선 때 컴퓨터에서는 다른 결과를 보였다.

아무리 생각해도 맞는 것 같아서 집에와서 돌려보니 내 노트북에서는 정확히 돌아간다.. 무슨 오류가 있는지 모르겠다.

그러나 시간 초과는 여전할 것 같다. 생각해보니 위의 알고리즘 역시 O(n)일 텐데, n이 9999999999라면, 1억이 넘는 것이기 때문에 1초가 초과될 것 같긴 하다.(컴퓨터 성능에 따라 다르겠지만..)

3. (번외) 만약 자바로 풀었다면?

이 문제를 만약 java로 풀었다면?

굳이 문자열을 하나하나 비교할 것없이, String의 reverse 메서드를 이용해서 true이면 count하도록 했어도 훨씬 빠를 것 같긴하다.

[소감]

아무튼 이 문제를 풀면서 여러가지 생각이 들었는데, 역시 간단한 문제일수록 최적화에서 빛을 발해야 한다는 점이다.

그리고 거듭제곱 메서드를 쓰는데 우리 모두 sqrt를 pow로 착각해서 pow를 써야 할 것을 sqrt로 적고는 이상하다~?하고 있던게 너무 어이없었다..ㅋㅋ 기본기를 잘 하자!!

여러가지 접근법을 고민해보고 하는 과정에서, 서로의 코드를 리뷰하고 최적화를 위해 여러 지식도 공유할 수 있어서 많이 배우고 왔다.

D의 최적화를 해결 할 동안 간단하게 C를 풀었다.

C번 문제

주어진 문자열에서 HAPPY, SAD에 포함되어 있는 문자가 등장하면 카운트하고, 그 합산에 따라 이 문자열을 보낸 사람의 행복지수를 측정하는 문제이다.

P_h = H,A,P,Y의 등장 횟수 합산

P_g = S,A,D의 등장 횟수 합산

행복지수 = P_h/(P_h+P_g)

행복지수를 퍼센티지로 나타내야하기 때문에 식에 100을 곱하고, 소수점 둘째자리까지라서, 출력할 때 .2f로 출력하였다.

이 문제는 그냥 문자열을 for문으로 순회하면서 한 글자씩 H,A,P,Y에 해당하면 P_h를 카운트, S,A,D에 해당하면 P_g를 카운트하도록 하였다. (즉 A이면 둘다 카운트한다)

그렇게 해서 행복 지수 식에 대입해 행복지수를 출력하였다.

예외로, P_h와 P_g가 같으면 행복지수가 0임이 조건으로 있어서 이에 대한 처리도 해주었다.

이 문제의 난이도는 비교적 매우 쉬운 편이었다.

그리고 풀다가 시간이 끝나 구현해 보지 못한 문제..

G번? F번?

몇번이었는지 기억은 안나는데, n개의 별의 좌표를 x,y 평면에 주어졌을 때 어떤 한 점에 대칭인 별의 최대 개수를 구하는 문제였다. 이때 어떤 한 점은 주어지지 않기 때문에, 더 어려웠던 것 같다.

수학적으로 창의성을 요구하는 문제이기도 했고, 끝까지 팀원들과 여러 방법을 갈구해보았으나, 정답으로 가는 식을 찾지는 못한 것 같다.

<총평>

생각보다 시간이 널널한 것 같아도, 9-10문제이기도 하고, 수학적 창의성을 요하는 문제가 너무 많아서, 다 풀기에는 무리였지만, 쉬운 문제는 또 풀기 쉬웠던 것 같다.

문제가 영어로 되어 있어서 해석하는데에도 오래걸린 것도 있다..

실시간으로 문제를 여러 사람과 풀어보는 게 처음이기도 했지만, 확실히 내가 주춤거렸던 부분에 대해서 옆에 팀원이 척척 해결해주니 그 시너지가 정말 크게 느껴졌다. 

서로의 부족한 점을 채우면서 하나의 문제를 해결해 갔을 때 그 희열은 아직 잊을 수가 없다.

결과가 어떻든, 함께 해결해 나가는 것의 즐거움을 느꼈고, 비슷한 기회가 있다면 다음에는 더 성장해서 한 번 더 시도해보고 싶다!!

코테를 보고나서 DFS의 중요성을 뼈저리게 느끼고, 한 번 더 개념을 잡고, 흐름을 잡고자 풀어본 문제이다.

✅ 코테에서 머뭇거렸던 부분

• DFS함수를 어느 시점에서 불러야 할지
• DFS함수를 어떻게 구성해야 할지
  (함수 내에서 재귀적으로 호출하는 부분은 어떻게?)
  (해당 노드를 방문할지 말지를 어떻게?)
• 방문하고 나서 다시 이전 단계로 돌아와 다른 경로를 찾게 하려면 코드를 어떻게?⭐⭐⭐(이게 관건임)

위와 같은 이유들은 내가 dfs를 스택으로 해결한 문제만 풀어봤기 때문이고, dfs함수를 써서 재귀적으로 함수를 호출하며 방문 여부를 체크하는 배열을 사용한 문제를 접해보지 못했기 때문에, 그 로직을 정확히 이해하지 못한 것 같다.

이 문제를 계기로 dfs의 전체적인 흐름을 바로잡고자 한다.

💡 문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.


변환할 수 없는 경우에는 0를 return 합니다.

다음과 같은 것을 고려해 볼 수 있다.

1. 현재 begin과 비교했을 때 words 중에 딱 한 문자만 다른 단어가 있는지?
   => 이를 위한 함수가 필요하다.
2. 만약 한문자만 다른 단어가 있으면 그 단어에서 다음 변경될 단어를 찾을 때 역시 한 문자만 다른지를 확인해야하고, 그 문자를 방문한 이력이 있는지를 확인해야한다.
   =>해당 단어를 방문한 이력이 있는지를 기록하는 boolean타입의 배열이 필요하다.
3. 조건에 맞는 단어를 방문하고 나서 다음 방문 여부를 확인하고 이어서 또 방문하기 위해선 dfs함수안에 dfs함수를 재귀적으로 호출하여 해당 루트에 대해 끝까지 방문하도록 해야한다.
4. 재귀함수이더라도 끝은 있어야 한다. dfs함수 내에 if문으로, 현재 방문한 단어가 target과 같을 시에는 answer를 갱신하고 dfs를 빠져나오도록 한다.
5. 항상 dfs를 재귀로 호출한 다음에는, 이전 단계로 돌아왔을 때 다른 루트를 고려하기 위해서 해당 노드의 방문여부를 다시 false로 바꾸어주는 단계가 필요하다.(=이것은 즉, 이 노드를 방문하지 않았다면?과 같은 의미이다=>이어지는 다음 루프에서는 해당 노드를 방문하지 않은채로 고려할 수 있기 때문이다⭐⭐⭐)

✏ [5에 대한 부가 설명]

1,2,3 노드가 있다고 하자.
현재 1번 노드를 방문한 상태이고, 앞으로 방문기록이 없는 2와 3에 대해 방문을 할것이다.
for문을 통해 번호순으로 방문할 것이기 때문에, 2를 먼저 방문한다.
2를 방문했으므로 visited배열에 2를 방문했다는 표시(true)를 한다.
그리고 다시 2를 시작으로 남은 노드를 순차적으로 방문한다. 
현재 예시에서는 방문기록이 없는것 중 남은게 3뿐이므로 3을 방문한다.
더이상 방문할 곳이 없기 때문에 다시 이전 단계로 돌아가 본다.
2를 다시 방문하지 않은 상태로 둔다.
하지만 이전 for루프에서는 순차적으로 2를 방문한 것이었고, 이번 for루프에서는 3을 방문할 차례이다.
따라서 3을 방문하고, visited배열에 3을 방문했다는 표시를 한다.
그리고 다시 3을 시작으로 남은 노드를 순차적으로 방문한다.
현재 방문기록이 없는게 2뿐이므로 2를 방문한다.

이렇게 되면 1->2->3으로 한번 방문했고, 1->3->2로도 한번 방문했다.
이런식으로 첫 시작이 잡히면 그 뒤로 방문처리, 재귀적으로 호출, 다시 미방문처리, 다음루프 로 이어지면서 모든 경로를 탐색해 볼 수 있게 되는 것이다.

위와 같은 사항들을 고려하면서 코드를 작성하면 다음과 같은 단계로 작성할 수 있다.

✅ 코드 작성 단계

1. 간단한 예외 처리해주기.
   - 문제에서 주어진 예시를 보면 words배열에 target이 없는 경우 변환될 수 없는 것이기 때문에, 0을 answer로 리턴하도록 되어 있다.

   - 배열에 해당 요소가 있는지를 비교하면되는데, 이는 ArrayList의 contains() 메서드를 활용하면 매우 쉽다.

list = new ArrayList<>(Arrays.asList(words));//리스트에 Arrays.asList메서드를 통해
//words배열을 리스트로 변경하고 있다
        
if(!list.contains(target)) return 0;//만약 list에서 target이 없으면 0을 리턴

   -list의 경우 List<String> list 로 static 전역으로 선언하여 사용하였다.

2. solution함수 내에서 첫 시작 방문을 for문으로 돌기

   - 어떤 노드가 시작이 될지 모르기 때문에, 시작을 정해주기 위한 모든 경우의 수를 고려해야한다.

   - 따라서 for문을 words의 크기만큼 돌면서 현재 단어가 begin과 한글자만 차이나는지 확인해야 한다.

   - 위를 확인하기 위한 boolean타입의 함수를 생성해주어야 한다.

for(int i=0; i<words.length; i++){//모든 워드에 대해 시작을 탐색
//???

2-1. canChange함수 정의하기

   - 현재 begin 단어가 words의 해당 단어와 한글자만 차이나면 true를, 아니면 false를 반환하도록 하는 함수이다.

   - boolean을 반환한다.

   - for문을 돌면서 begin과 target의 한글자 한글자가 같은지 비교하고, 다르면 count한다.

   - count가 1이면 true를 아니면 false를 반환한다.

public boolean canChange(String target, String begin){//begin과 target을 인자로 받는다
        int count=0;//count는 0으로 초기화한다
        for(int i=0; i<begin.length(); i++){//begin글자수만큼 비교
            if(begin.charAt(i)!=target.charAt(i)) count++;//다르면 카운트
        }
        
        return count==1;//카운트가 1이면 한글자만 차이나는 것이므로 후보가 된다
    }

2-2. 한글자만 차이나는 모든 단어에 대해 해당 단어를 시작으로 하는 루트를 모두 탐색하기

   - 이제 2에서 설명한 for문에서 words 중에 현재 단어가 canChange를 만족하면, visited[] 배열을 새로 할당한다.

   - 해당 단어의 인덱스를 통해 visited에 방문했음을 표시한다.

   - DFS함수를 호출해서 현재 단어를 시작으로 아직 방문하지 않은 나머지 단어에 대해 위 과정을 거치도록 한다.

   - DFS함수를 구현해야 한다.

for(int i=0; i<words.length; i++){
            if(canChange(words[i], begin)){
                visited = new boolean[words.length];
                visited[i]=true;
                dfs(????);
            }
}

3. DFS함수 구현하기

   - dfs함수에서는 사실상 solution함수에 있는 것을 반복하는 것이라고 보면 되는데, 재귀적으로 호출할 것이기 때문에, 마지막에는 멈출 수 있는 조건이 항상 있어야 한다.

   - dfs함수에 현재 루트에서 몇번 노드를 탐색했는지(=answer와 직결됨), 현재 방문한 단어는 무엇인지, 최종 찾고자 하는 (=도달하고자 하는)단어는 무엇인지에 대해 인자로써 알려주어야 한다.

   - 따라서 몇번 노드를 탐색했는지는 int타입의 index, 현재 방문한 단어는 String의 begin, 찾고자 하는 단어는 String의 target이다. 

   - dfs에서는 일단 현재 방문한 노드 begin이 target과 동일한지 비교하고, 동일하면 answer를 갱신한다.

   - 이때 answer는 몇번 노드를 탐색했는지를 나타내는 index와 현재 answer중에 더 작은 것으로 선택하여 갱신하도록 한다. 그리고 return을 하여 dfs가 끝나도록 한다

   - 만약 같지 않다면, for문을 통해 다음 방문할 노드를 찾기 위해 words를 또한번 탐색하는데, visited와 canChange를 통해, 방문한 기록이 없고, 한글자 차이인 경우에는 그 단어를 방문한 상태로 바꿔준다.

   - 그리고 dfs를 호출해서 현재 막 방문한 상태로 바꿔준 단어를 기점으로 위 단계를 반복하도록 한다.

   - 만약 다 돌아서 이전 단계로 돌아왔을 때에는 다시 방문하지 않은 상태로 바꾸어주고, 다음 루프에서 다른 단어를 먼저 방문하더라도 이 노드가 방문될 수 있도록 (즉 여러 루트를 고려하도록 하기 위해, 위에 5번 설명 참고)한다.

   - 위 단계가 매우 중요하다. 이것이 없으면 다시 돌아가서 다른 루트를 찾는 과정을 거칠 수가 없기 때문이다.

public void dfs(int index, String[] words, String begin, String target){
        if(begin.equals(target)){
            answer=Math.min(index, answer);
            return;//이에 해당하면 아래를 실행하지 않기 위해
        }
        
        for(int i=0; i<words.length; i++){
            if(!visited[i]&&canChange(words[i],begin)){
                visited[i]=true;
                dfs(index+1, words, words[i], target);//재귀호출하여 현재 루트를 이어가도록한다
                visited[i]=false;//다른 루트를 탐색하도록 하기 위함이다.매우 중요!!!
            }
        }
    }

4. DFS함수 호출하고, 최종 answer 리턴하기.

   - 앞에서 정의한 dfs에 따라서 인자를 다음과 같이 설정해준다.

   - 첫 방문 노드의 경우 한번 방문했으므로 index는 1이된다. 그리고 방문했을 경우 begin은 words[i]가 되는 것이고, target은 최종 target이다.

for(int i=0; i<words.length; i++){
            if(canChange(words[i], begin)){
                visited = new boolean[words.length];
                visited[i]=true;
                dfs(1,words,words[i],target);
            }
        }
        
        return answer;

   - 이렇게 다 하고 나면 answer에는 최종 답이 들어간다.

5. 세부사항

   - min 연산을 위해 answer는 integer의 max_value로 초기화 하였다.

   - answer, visited배열, list는 static 전역으로 선언하였다.

   - answer는 그래서 모든 연산에서 실시간으로 제일 작은 값을 얻도록 하였다.

최종코드이다.

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    static List<String> list;
    static int answer;
    static boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        answer = Integer.MAX_VALUE;
        list = new ArrayList<>(Arrays.asList(words));
        
        if(!list.contains(target)) return 0;
        
        for(int i=0; i<words.length; i++){
            if(canChange(words[i], begin)){
                visited = new boolean[words.length];
                visited[i]=true;
                dfs(1,words,words[i],target);
            }
        }
        
        return answer;
    }
    public void dfs(int index, String[] words, String begin, String target){
        if(begin.equals(target)){
            answer=Math.min(index, answer);
            return;
        }
        
        for(int i=0; i<words.length; i++){
            if(!visited[i]&&canChange(words[i],begin)){
                visited[i]=true;
                dfs(index+1, words, words[i], target);
                visited[i]=false;
            }
        }
    }
    
    public boolean canChange(String target, String begin){
        int count=0;
        for(int i=0; i<begin.length(); i++){
            if(begin.charAt(i)!=target.charAt(i)) count++;
        }
        
        return count==1;
    }
}

문제 자체가 힙을 구현하는 카테고리에 있는 걸 보고 접근한 거라, priorityqueue로 풀 수 있다는 걸 알고 풀어서 쉽게 풀어버린 케이스이다. 그래도 오랜만에 heap을 다루는 것이기도 하고, java에 있는 pq를 쓰는 건 처음이라 메소드도 익힐 수 있었다.

💡 Min Heap (PriorityQueue)

Heap?
- 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조.
- 힙에서는 중복된 값을 허용.
- max heap은 가장 큰 값이 부모노드에, min heap은 가장 작은 값이 부모노드에 있다.
- 부모노드는 자식노드보다 크거나 같고(max heap), 작거나 같아야(min heap) 한다.

- 힙은 배열을 통해 구현할 수 있다.
- 구현을 쉽게 하기 위해 0번 인덱스는 사용하지 않는다.
- 루트 노드가 1번 인덱스이다.
- 왼쪽 자식 노드 인덱스 : (부모노드 인덱스)*2
- 오른쪽 자식 노드 인덱스 : (부모노드 인덱스)*2+1
- 부모 노드 인덱스 : (자식노드 인덱스)/2

자바에서 힙은 java.util에 있는 PriorityQueue를 사용할 수 있고, 기본적으로 min heap을 구현한다.

💡 java.util.PriorityQueue

- 기본적으로 mean heap을 구현한다.
- 요소 삽입 : offer()
- 가장 작은 요소 반환 및 삭제 : poll()
- 가장 작은 요소 반환 : peek()
- 힙의 크기 반환 : size()

이 정도로 정리해 두면 문제는 충분히 풀 수 있다.

문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.


Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.


모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식의 스코빌 지수가 K이상이 된다는 것은, min heap에서 가장 우선 순위에 있는 노드의 값이 K이상인 것과 같고, 그렇게 되면 그 아래 모든 노드는 K이상이 되기 때문에, min heap을 이용해서 아주 쉽게 이 문제를 해결할 수 있다.

알고리즘은 다음과 같다.

1. PriorityQueue 객체를 Integer 타입으로 생성한다.
2. 스코빌 배열에 있는 모든 값을 우선순위 큐에 삽입한다.
3. while문을 통해 다음의 조건을 만족하는 경우에만 반복실행한다
   "우선순위 큐의 가장 작은 값=가장 먼저 나오는 값이 K보다 작고, 우선순위 큐에 있는 요소가 2개이상인 경우"
   다음을 실행한다
   우선순위 큐에서 가장 작은 값 두개 꺼내고 위의 식을 통해 섞은 음식의 스코빌 지수를 구한 후 이를 다시 큐에 삽입한다. 그리고 answer 값을 1 올린다.
   위 과정을 조건을 만족할 경우에 반복한다
4. 위 과정을 마치고 나면 큐는 스코빌 지수가 모두 K이상이거나, 큐에 있는 요소가 2개 미만인 상태일 수 있다.
5. 전자의 경우라면 answer를 그대로 반환하면 되고, 후자의 경우라면 모든 음식을 섞어도 K이상이 안된다는 것이므로 문제에서 주어진 조건에 따라 -1을 반환하면 된다.

전체 코드는 아래와 같다.

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int item : scoville){
            pq.offer(item);
        }
        
        while(pq.peek()<K && pq.size()>=2){
            int temp1 = pq.poll();
            int temp2 = pq.poll();
            pq.offer(temp1+(temp2*2));
            answer++;
        }
        
        if(pq.size()==1 && pq.peek()<K) return -1;
        
        return answer;
    }
}

*** while문을 실행하고 나면 어차피 pq.peek()<K라는 것은 pq.size()==1인 것과 동시에 일어나기 때문에, 마지막 if문에서는 pq.peek()K만 만족하면 -1을 반환하도록 코드를 줄여도 된다.

자바 문법 정도만 레퍼런스를 받고, 알고리즘 자체는 직접 구현한 풀이 방법이다.

set을 활용한 부분에 있어서는 다른 사람들의 코드를 살펴보니 대부분 사용하는 편인 것 같았다.

전체적인 진행 방향은 다음과 같다.

1. 문자열에 들어 있는 0~9 숫자들을 INT 타입으로 바꾸어 int배열에 저장한다.
2. 배열에 저장된 수를 가지고, 직접 짠 조합 알고리즘을 통해 가능한 모든 숫자 조합을 찾아 SET 자료구조에 저장한다.
3. SET에 저장된 숫자가 소수인지 판별하여, 소수인 경우에만 카운트를 한다.

SET 자료구조

- 중복된 값을 저장하지 않아서 유니크한 값으로만 구성된다.
- Set 자료구조는 인터페이스라서 HashSet로 Integer를 명시해서 생성해야 한다.

• 문자열에 들어있는 숫자를 조합해 나올 수 있는 모든 수를 구해야 한다.
• permutation 함수를 이용할 수 있었는데, 존재를 까먹고 조합 알고리즘을 직접 구현함.
• 문자열의 각 숫자를 INT 형식으로 바꾸어 INT타입의 배열에 저장해줌.
• 그 INT배열을 가지고 숫자를 조합하는데, 중복된 숫자 값이 생성될 수 있으므로 Set 자료구조를 사용해서 중복된 값이 들어가지 않도록 하였음.
• 일단, 자리수 하나의 숫자들을 set에 저장.
• 그리고 각각의 저장된 숫자를 제외한 배열 값을 갖는 새로운 배열을 만들어서 재귀적으로 가능한 조합을 만들 수 있도록 하는 함수의 인자로 넣어줌.
• 그 함수가 makePrime인데, 함수이름만 makePrime이고, 사실상 조합을 만드는 함수임. 나의 실수.
• makePrime함수에서는 주어진 배열과, set, 이전에 이미 방문?했던 앞자리 수를 인자로 받음.
• 그리고 앞자리수가 하나 제외되어있는 주어진 배열에 있는 값을 하나씩 앞자리 수에 더하여 수를 만들고 set에 집어 넣음.
• 이때 앞자리 수에 10을 곱하고 배열에 있는 값 중 현재 가리키는 값을 더함으로써 새로운 수를 만들 수 있음.
• 그리고 makePrime함수를 재귀호출함으로써 위의 과정을 반복하다 보면, set에는 모든 가능한 숫자 조합이 만들어져 있음.
• 이 set을 가지고, 순회하면서, 만약 값이 0,1이라면 소수로 포함하지 않고, 2,3,5,7이라면 소수로 카운팅 함.
• 그리고 2의 배수라면 소수로 포함하지 않고, 2의 배수가 아니라면 해당 값을 3부터 (해당값/3)을 한 값까지로 나누었을 때 나머지가 0이면 => 1과 자기 자신 말고도 나눠지는 값이 있다는 것이므로 소수가 아니고, 카운팅 하지 않는다. 만약 그런 값이 하나도 없었다면(=>불리언 값으로 판단함) 소수로 카운팅한다.
• 위의 과정을 거침으로써 소수의 개수를 찾을 수 있다.
• 다소 복잡하게 보이지만, 스스로 짰다는 것에 의의를 둔다.
• 메소드를 익히는 것도 중요해 보인다.

전체 코드이다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] removeValue(int[] arr, int remove){
        int[] newarr = new int[arr.length-1];
        int first = 0;
        int index = 0;
        for(int i : arr){
            if(i==remove && first==0){
                first = 1;
            }else{
                newarr[index]=i;
                index++;
            }
        }
        
        return newarr;
    }
    
    public void makePrime(int[] arr, Set<Integer> set, int prev){
        for(int i=0; i<arr.length; i++){
            set.add(prev*10+arr[i]);
            int[] newarr = removeValue(arr, arr[i]);
            makePrime(newarr, set, prev*10+arr[i]);
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;//count
        
        int[] nums = new int[numbers.length()];
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<numbers.length(); i++){
            nums[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        for(int i=0; i<nums.length; i++){
            set.add(nums[i]);
            int[] newarr = removeValue(nums, nums[i]);
            makePrime(newarr, set, nums[i]);
        }
        
        //set에는 가능한 모든 값들이 생성된다.
        
        for(int i : set){
            if(i==0 || i==1){//0이거나 1이면 패스
                continue;
            }
            if(i==2 || i==3 || i==5 || i==7){//2,3,5,7이면 count
                answer++;
                continue;
            }
            if(i%2==0){//2의 배수이므로 패스
                continue;
            }else{
                int isPrime = 1;
                for(int j=3; j<=(i/3); j++){
                    if(i%j==0){
                        isPrime=0;
                        break;
                    }
                }
                if(isPrime==1) answer++;
            }
        }
        
        return answer;
    }
}

이 문제를 푸는데만 1시간 반이 걸렸지만, 성공한게 뿌듯했다.