[TIL] (230617) 중복값이 존재할 수 있는 두 배열을 비교하여 포함되지 않은 요소를 찾아내자.-> 소거법 or HashMap 이용하기.

 

 

 

오늘도 조건문과 반복문을 활용한 프로그래머스 문제를 풀어보았다.
이제는 단순히 조건문, 반복문의 사용법뿐만 아니라 늘 사용하던 형태들( int [], String [], ArrayList <> )이 아닌 다양한 변수들의 형태와 특징을 알아보고 적재적소에 활용하는 문제풀이가 필요했다.

 

---

🔸문제 발생 

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576

- 조건
String[] participant: 마라톤 경기에 참여한 모든 선수들의 이름이 담긴 배열
String [] completion: 완주한 모든 선수들의 이름이 담긴 배열
완주하지 못한 선수의 이름을 return 하는 함수를 작성해라

*  1≤ 참여한 선수의 수 ≤ 100,000명
* completion의 길이는 participant의 길이보다 1 작다.
* 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자이다.
* 참가자 중에는 동명이인이 있을 수 있습니다.

 

 

 

✅ 처음 기재한 코드 👇

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

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        List<String> doneList = Arrays.asList(completion);
        
        for (String s: participant) {
            if (!doneList.contains(s)) {
                answer = s;
            }
        }
        // 여기에 중복값을 체크하는 코드가 필요함
        
        return answer;
    }
}

 

 

✅ 실행 결과 ( 중복체크를 구현 못해서 부분실패 예상했음)

 

completion에 contains()을 사용하고 싶어서 Arrays.asList()로 변환했다.

for문을 돌리면서 포함되지 않은값을 저장하는 코드를 만들었고 실제로 중복값이 없는 경우는 원하는 값이 나왔다.

다만 테스트 3번처럼 완주하지 못한 사람과 완주한 사람이 동명이인일 때는 원하는 대로 체크되지 않아서 방법을 찾아봤다.

---

 

🔸시도해 본 것

 

1. 각 배열에서 값의 포함여부를 반복문으로 확인 후 없는 값만 저장한다.
2. 동명이인(중복값)인데 한명은 완주를 해서 1과 같이 체크할 때 오류가 발생하는 부분을 별도로 구현한다.

내가 생각한 방향은 크게 두가지였다.

여기서 2번이 문제였는데 "어떤 식으로 중복요소라는 걸 알아보고 처리할 건가?" 이 부분을 boolean형태의 변수로 선언해 봤다.

 

 

1. boolean Key 선언

👇 코드 👇

  boolean key = false;
        if(answer.length() == 0) {
            for(String s: participant) {
                if(doneList.contains(s)) {
                    key = !key;
                }
            }
        }

의도: key의 기본값을 false로 선언 후  participant와 completion값이 일치하는 인덱스만 true로 바꾼다.

이미 if문으로 문자열의 길이가 0인 경우만 진행하기 때문에 무조건 중복이 있다고 보며, 이 중 중복값이 있을 경우 다시 false로 바꾼 후 그 값만 추출하고 싶었다.

 

코드를 짜면서도 느낀 문제점

1.  boolean값을 기억하려면 각 인덱스마다 boolean값을 따로 저장해야 되는데 그럼 기존의 participant배열을 이차원 배열로 복사하고 복사할 때 false로 설정해야 한다.

사실 이 부분을 진행하기 전에도 if-for-if를 사용하면서 이미 코드의 비효율성이 보이고 또 지금 내가 시도하려는 배열의 복사 역시 비용이 증가한다는 것을 알지만 이 방법이 실제로 구현되는 건 맞는지 궁금해져서 다른 건 신경 쓰지 않고 구현여부만 확인해 봤다.

 

 

 

✅ 이차원 배열로 설정했을 때 코드👇

 String[][] arr2 = new String[participant][2];
        List<String> doneList = Arrays.asList(completion);
        
        for(int i = 0; i < participant.length; i++) {
            arr2[i][0] = participant[i];
            arr2[i][1] = "0";
        }

        System.out.println(Arrays.deepToString(arr2));
        
        // 출력값 [[leo, 0], [kiki, 0], [eden, 0]]

생각한 대로 이차원 배열 설정은 했으나 문제가 있다.

participant []가 String 배열이라 이차원 배열도 String으로 설정했는데 그럼 논리값을 넣을 수가 없다.

내가 원한 건 논리의 반전인! 연산자를 이용해서 중복으로 체크된 경우 다른 요소들과 값이 다르게 나오도록 하는 건데 판단에 사용되는 값이 문자열로 들어간다면 이 방식은 진행할 수 없게 된다.

중복체크에 해당되는 값이 나오면 arr [i][1]을 true처럼 문자열로 바꾸고 해당되는 모든 문자를 reverse()할까?

근데 이렇게 진행하면 코드가 너무 길어지고 복잡도가 상당해서 다른 방식의 접근을 생각해 봤다.

 

---

2. 같은 값을 찾으면 소거하기!

여러 방법을 생각해 보다가 배열을 오름차순으로 정렬 후 contains() 즉, 포함여부가 아닌 equals()를 사용하면 되지 않을까?라는 생각이 들었는데 마찬가지로 주어진 배열 말고 추가적으로 확인할 수 있는 키가 필요하다고 생각했다.

그럼 1번의 상황과 다를 게 없어서 직접 손으로 그림을 그려보다가 일치하는 값을 아예 지워버리는 소거법이 생각났다.

 

굳이 키 값을 설정할게 아니라 완주자 목록에서 참가자를 이용하여 일치하는 경우 목록에서 지워버리면 어떨까?? 그럼 동명이인이라도 값이 남게 된다는 생각을 했다.

매개변수로 받아오는 배열 participant의 데이터의 보존이 필요할 수 있기 때문에 새로운 배열 participantCopy를 생성하여 진행해 봤다.

 

 

✅ 중복값을 제거했을 때 코드👇

 

값은 정상, 런타임은 초과

 

 

 

---

 

🔸해결

 

원하는 대로 실행은 되었으나 런타임 에러가 떴다는 건 내가 선택한 코드가 아닌 다른 효율적인 방법이 있다는 거라고 생각한다. for문에서 걸린 것 같은데 이 코드를 더 간단하게 줄이는 방법을 찾아봤고 2가지 경우로 접근할 수 있었다.

 

 

3. sort 정렬 후 처음으로 일치하지 않는 값 찾기

주어진 문자열을 먼저 오름차순으로 정렬한 후 값을 순서대로 비교하면서 일치하지 않는 값을 찾는다.

사실 이 방법도 생각했었으나 일치하지 않는 값이 나오면 뒷부분부터 순서가 다 밀리지 않나?라는 생각으로 배제시켰던 방법이었다. 이 방법으로 진행할 수 있다고 나와서 직접 그려봤다.

 

 

✅ 오름차순 정렬 후 값을 비교했을 때 코드 👇

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        Arrays.sort(participant);
        Arrays.sort(completion);

        for(int i=0;i<completion.length; i++) {
             if(!completion[i].equals(participant[i])){
                answer = participant[i];
                 break;
             }
        }
        if("".equals(answer)) {
            answer = participant[participant.length -1];
        }

        return answer;
    }
}

역시 애매할 땐 직접 그려보는 게 확실하다.

 

조건문의 불일치가 발생하는 시점이 바로 cpmpletion에 없는 값이 되고, 원본의 훼손도 없을뿐더러 런타임 에러도 발생하지 않는다.

단, 불일치 값이 가장 마지막 인덱스라면 처음 설정한 ""으로 나오기 때문에 if조건에 원래 배열인 participant []의 마지막 인덱스를 반환한다.

이렇게 진행하면 런타임도 통과가 된다!

 

 

4. HashMap 이용하기

 

✅ HashMap 코드 👇

 

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

내가 애먹었던 매개변수에 키, 값을 설정하는 부분이 HashMap으로 간단하게 해결할 수 있었다.

participant 배열을 순회하면서 이름을 key로 사용하는데 value디폴트를 0으로 설정하여 초기에 대응되는 key-value를 (player, 1)로 설정하고 다음 for문에서  key-value를 -1씩 진행하여 아래와 같이 판별하게 된다.

 

1) 동명이인이 없을 때

value : 1 (다음 for문에서 매칭되는 key값이 없기 때문에 -1을 못했음)

2) 동명이인이 있을 때

value: 1(처음 for문에서 getOrDefault(player, 0) + 1로 인해 총 2라는 값을 가짐, 이후 -1이 진행됨)

 

이렇게 key-value를 통해 간단하게 구현이 가능하다

 

 

 

 

---

 

🔸알게 된 점 

 

처음 이차원 배열을 선언 후 원하는 대로 값이 들어갔는지 확인차 toString()을 했는데 오류가 발생했다.

일차원 이상의 다차원 배열에서는 toString()이 아니라 deepToString()를 진행한다는 것을 배웠다.

두 배열이 있고 딱 한 가지 값만 다르고 나머지는 모두 동일하다면 정렬을 통해 없는 값을 찾을 수도 있다. 

포함여부를 확인하는 contains()는 중복여부를 체크하지 않고 확인할 값이 확인해야 되는 데이터의 모음에 존재하는지 여부만 판단하기 때문에 지금 문제에서는 적합하지 않았다.

단순한 반복문이 아닌 지금처럼 주어진 값의 체크여부가 필요할 경우 key-value를 사용하면 조금 더 효율적이다.

나는 HashMap의 key값이 중복되지 않고 같은 값일 경우 덮어쓰기가 된다는 것만 알고 있어서 중복값의 경우 단순히 덮어쓰기가 되기 때문에 여전히 중복값 체크는 못하지 않을까 싶었는데 

hm.put(player, hm.getOrDefault(player, 0) + 1);
hm.put(player, hm.get(player) - 1);

value값에 get으로 설정되어 있던, 혹은 디폴트값을 가져와서 진행하면 key값은 그대로이고 기존값에 ±가 가능하게 구현할 수 있다는 것을 알게 되었다.