작은 기록공간

https://leetcode.com/problems/neighboring-bitwise-xor/description/

이번 문제는 생각보다 간단해서 힘이 빠졌다.

정말 어렵게 고민했었는데  사실은 아주 쉽게 해결된다는 사실을 깨달았다.

길이 n으로 유도된 0-인덱스 배열은 길이 n의 이진 배열 original에서
인접한 값의 비트 단위 XOR(⊕)을 계산하여 유도됩니다.

구체적으로, [0, n - 1] 범위의 각 인덱스 i에 대해
i = n - 1이면 derived[i] = original[i] ⊕ original[0]입니다.
그렇지 않으면 derived[i] = original[i] ⊕ original[i + 1]입니다.

주어진 배열 derived에서, 여러분의 과제는
derived를 형성할 수 있는 유효한 이진 배열 original이존재하는지 여부를 확인하는 것입니다.

그러한 배열이 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
이진 배열은 0과 1만 포함하는 배열입니다.

예제 1:
입력: derived = [1,1,0]
출력: true
설명: derived를 제공하는 유효한 original 배열은 [0,1,0]입니다.
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

예제 2:
입력: derived = [1,1]
출력: true
설명: derived를 제공하는 유효한 original 배열은 [0,1]입니다.
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

예제 3:
입력: derived = [1,0]
출력: false
설명: derived를 제공하는 유효한 original 배열이 없습니다.

제약 조건:
n == derived.length 1 <= n <= 105 derived의 값은 0 또는 1입니다.

요약하면 derived 배열이 주어지는데 이 배열의 값을 생성할 수 있는XOR 배열의 존재 여부를 묻는 문제다.

난 이 문제를 정말로 어렵게 생각했다

왜냐면 [1,1,0] 이 주어지면 1을  만들기 위해서는 0,1이 필요하고

그럼 [0,1] [1,0],[0,0] 이렇게 3개의 경우의 수가 생기는데 이걸 어떻게 합친단 말인가

이것저것 고민했지만 결국 답은 정말 간단했다.

주어진 배열에서 1의 개수가 짝수인 경우에만 정답이라는 것이다.그  예시를 들어보자면 

입력: derived = [1,1,0]
출력: true
설명: derived를 제공하는 유효한 original 배열은 [0,1,0]입니다.
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0


입력: derived = [1,0,0]
출력: false
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 1 = 0
derived[2] = original[2] ⊕ original[0] = 1 ⊕ 1 = 0

두번째 입력인 [1,0,0] 의 경우에 먼저 첫번째 1을 만족하기 위해서는 [0,1] 또는 [1,0] 이 필요하다. 

다음으로 0을 만족하려면 [0,0] 또는 [1,1] / 마지막 0 또한 [0,0] 또는 [1,1] 이 필요하다

하지만 [0,1]로 시작했다면 [0,1,1]이 되어야 하고 이 경우 마지막 XOR은 [1,0]이 되어 0을 만들수가 없다

고로 배열에서 주어진 수에서 1의 개수가 짝수인 경우만 XOR이 성립된다.

이제 문제 해결 방법을 알았으니 이를 적용하여 코드를 짜면 된다.

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        boolean result = false;
        int count = 0;
        
        for(int d : derived){
            if(d == 1){
                count++;
            }
        }

        if(count%2 == 0){
            result = true;
        }

        return result;
    }
}

위 코드는 요소의 값이 1이면 count의 값을 올리고

마지막에  카운트값을 2로 나눈 나머지가 0이면  true를 반환한다.

쓸데없는 동작도 많고 시간복잡도가 꽤 높아서 더 간단하게 코드를 수정했다

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int count = 0;
        
        for(int d : derived){
            if(d == 1){
                count++;
            }
        }
        return count % 2 == 0;
    }
}

이번엔 if문을 하나로 묶어서 해결했다.

그런데도 별 차이가 안나길래 나보다 더 빠른 사람들의 코드를 한번 읽어보았다.

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xor=0;
        for(int x:derived)
            xor^=x;
        return xor==0;
    }
}

이건 정말 신선한 충격이였다

간단하게 ^ (XOR) 을 이용해서 값이 0이 나오면 true를  반환하게 했다니

손으로 다시 계산해봐도 0이 나오면 true가 나왔다.

이외에도 다른 코드도 봤는데

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int count = 0;
        
        for(int d : derived){
            count += d;
        }
        return count % 2 == 0;
    }
}

쓸데없는 if문을 아예 없애서 더 간단하게 짤 수 있었다.

이렇게 하니 런타임은 2ms 메모리는 63.75mb가 나왔다.

일단 원리만 이해하면 푸는건 시간 문제인것 같다.

https://leetcode.com/problems/minimize-xor/description/

이번 문제는 비트연산을 하는 문제이다.

사실 일상에서나 어떤 문제를 해결할 때도 비트연산을 활용하는 경우는 거의 없기 때문에 존재 조차 까먹고있었다.

문제는 다음과 같다

두 개의 양의 정수 num1과 num2가 주어졌을 때, 다음과 같은 양의 정수 x를 구하세요.

x는 num2와 같은 수의 설정된 비트를 가지고 있고 값 x XOR num1이 최소가 됩니다.
XOR은 비트 단위 XOR 연산입니다. 정수 x를 반환합니다.
테스트 케이스는 x가 고유하게 결정되도록 생성됩니다.
정수의 설정된 비트 수는 이진 표현에서 1의 수입니다.

예제 1:
입력: num1 = 3, num2 = 5
출력: 3
설명: num1과 num2의 이진 표현은 각각 0011과 0101입니다.
        정수 3은 num2와 같은 수의 설정된 비트를 가지고 있고 값 3 XOR 3 = 0이 최소가 됩니다.

예 2:
입력: num1 = 1, num2 = 12
출력: 3
설명: num1과 num2의 이진 표현은 각각 0001과 1100입니다.
        정수 3은 num2와 동일한 수의 세트 비트를 가지고 있으며 값 3 XOR 1 = 2는 최소입니다.

제약 조건: 1 <= num1, num2 <= 10⁹

문제에서 2개의 정수값이 주어지고 여기서 num1,num2의 값을 각각 2진수로 바꿨을때,

1. 동일한 비트값을 가져야 한다 (1의 개수가 같아야한다)

2. 가장 최소값이어야 한다

이 두가지 조건을 만족하는 정수를 반환하면 되는 문제이다.

처음 이 문제를 봤을때 떠오른 생각은

1. 먼저 10진수를 2진수로 변환한다.

2. 두 수의 SetBit가 동일하면 답은 num1이고,

    1의 개수가 두 수 모두 동일하면 num1이 최소값이 된다.

...

이런식으로 생각을 이어나가다가 뭔가 아니라고 생각해서 이번엔 토론창을 한번 봤다.

거기서 아주 중요한 힌트가 있었는데,

Unset rightmost bit
x&(x−1)
Set rightmost unset bit
x∣(x+1)

처음 봤을때 이게 무슨소리인가 했는데 &과 |을 단일로 쓰면 비트연산이 된다는 사실을 완전히 잊고 있었다.

이 문제를 풀때 기본적으로 알고있어야 하는 사실은 다음과 같다

- AND : 비트가 모두 같을때 True

- OR   : 하나라도 같으면 True

- XOR : 비트가 같지 않으면 True

- NOT : 해당 비트의 반대값

다시 원점으로 돌아와서 저 공식을 다시 보면

• x&(x−1) : 가장 오른쪽 비트를 0으로 변경

예제)
원래값         :  5 & ( 5-1)
비트로 치환 :  5(101) & 4(100)

AND 연산
  101
&100
---------
 100

• x∣(x+1): 가장 오른쪽 비트를 1로 변경

예제)
원래값         :  12 & ( 12+1)
비트로 치환 :  12(1100) & 13(1101)

OR 연산
  1100
| 1101
---------
  1101

이렇게 볼수있다.

이 공식을 활용하면 우리가 원하는 만큼 비트값을 조절할 수 있게 된다.

아래는 정답 코드다.

class Solution {
    public int minimizeXor(int num1, int num2) {
        while(Integer.bitCount(num1) != Integer.bitCount(num2)) {
            if(Integer.bitCount(num1) > Integer.bitCount(num2)) {
                num1 = num1&(num1-1);
            } else {
                num1 = num1|(num1+1);
            }
        }
        return num1;
    }
}

Java에서는 Integer.bitCount(n) 메서드를 제공하여 이를 활용해 비트 값을 확인할 수 있다.

이를 활용해서 num1과 num2가 같아질 때 까지 반복하며 비트수를 조절하고 반환하는 코드이다.

런타임은 0 ms, 메모리는 40,33Mb가 나왔다.

이번 문제를 통해서 비트 계산에 대한 기초중에 기초를 배운것 같다.

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/description/

이번 문제는 최적의 방법으로 풀지는 못했지만 일단 정석대로 풀었다.

문제
길이가 n인 두 개의 0-인덱스 정수 순열 A와 B가 주어집니다.

A와 B의 접두사 공통 배열은 C[i]가 A와 B 모두에서 인덱스 i에 있거나
그 앞에 있는 숫자의 개수와 같은 배열 C입니다.

A와 B의 접두사 공통 배열을 반환합니다.

n개의 정수 시퀀스는 1에서 n까지의 모든 정수를 정확히 한 번씩 포함하는 경우 순열이라고 합니다.

예 1:
입력: A = [1,3,2,4], B = [3,1,2,4]
출력: [0,2,3,4]
설명:
i = 0일 때: 공통된 숫자가 없으므로 C[0] = 0입니다.
i = 1일 때: A와 B에서 1과 3이 공통이므로 C[1] = 2입니다.
i = 2일 때: A와 B에서 1, 2, 3이 공통이므로 C[2] = 3입니다.
i = 3일 때: A와 B에서 1, 2, 3, 4가 공통이므로 C[3] = 4입니다.

예 2:
입력: A = [2,3,1], B = [3,1,2]
출력: [0,1,3]
설명:
i = 0일 때: 공통된 숫자가 없으므로 C[0] = 0입니다.
i = 1일 때: A와 B에서 공통적인 것은 3뿐이므로 C[1] = 1입니다.
i = 2에서: A와 B에서 1, 2, 3이 공통적이므로 C[2] = 3입니다.

제약 조건:
1 <= A.length == B.length == n <= 50 1 <= A[i],
B[i] <= n A와 B가 모두 n개의 정수 순열임이 보장됩니다.

요약하자면 두개의 배열이 주어지는데 i번째 배열까지 같은 값이 포함된다면 카운트 해서 순서대로 반환해라 이다.

처음에 이 문제를 잘못 이해해서 이렇게 작성했었다.

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int size = A.length;
        int[] c = new int[size];
        int temp = 0;
        
        for(int i = 0; i < size; i++){
            temp = 0;
            for(int j = 0; j <= i; j++){
                if(A[i] == B[j] && (i-1) > 0){
                    c[i-1] = temp;
                }else{
                    temp++;
                }
            }
        }
        c[size-1] = size;

        return c;
    }
}

일단 모든 배열의 크기는 같기 때문에 size를 먼저 구하고,

2중 for문으로 반복하며 같은 값이 있다면 개수를 세서 넣었다.

마지막에는 제대로 값이 안들어가서 c[size - 1] = size 로 집어넣었다.

아주 엉망진창이고 별로인 코드지만 일단 테스트 케이스는 통과했기에 그대로 제출했다가 바로 틀렸다.

이후에 친구를 만나 이야기를 나눴는데 내가 문제를 제대로 이해하지 못하고 있다고 했다.

그래서 이번에는 차근차근 노트에다 한줄씩 적어서 생각을 정리한 다음 작성했다.

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int size = A.length;
        int[] c = new int[size];

        for(int i = 0 ; i < size; i++){     // 순서
            for(int j = 0; j <= i; j++){    // A의 값
                for(int k = 0; k <= i; k++){// B의 값
                    if(A[j] == B[k]){
                        c[i]++;
                    }
                }
            }
        }
        return c;
    }
}

3중 for문을 써서 i번째 배열에 대한 값을 각각 비교해서 c[i]를 증가시켜 반환하는 코드이다.

가장 기본적이고 이번  문제의 핵심이다.

런타임은 21ms, 메모리 45.4mb로, 아마 제약조건에 A와 B의 값이 50보다 더 높았다면 시간이 초과됐을것이다.

이 다음에는 한번 해시셋을 이용해서 풀어보았는데

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int size = A.length;
        
        int[] result = new int[size];
        HashSet<Integer> n1 = new HashSet();
        HashSet<Integer> n2 = new HashSet();

        for(int i = 0; i < size; i++){
            n1.add(A[i]);
            n2.add(B[i]);
            
            HashSet<Integer> n3 = new HashSet(n1);
            n3.retainAll(n2);

            result[i] = n3.size();
        }
        return result;
    }
}

코드 자체는 더 깔끔해졌고 알아보기 쉬워졌지만 런타임 41ms, 메모리 45.3mb로 더 나빠졌다.

아마 이유는 for문에서 해시셋을  반복적으로 생성하기 때문이라고 생각하는데,

처음에 해시셋을 쓸 때, retainAll이라는 함수가 있다는것을 보고 배열의 공통된 값을 제거하고 나머지만 남긴다고 해서

아 이걸 쓰면 되겠구나 했는데, 그 결과값을 객체에 저장할줄은 몰랐다...

그래서 하는수 없이 n3를 하나 생성해서 남은 값들을 저장하고 그 사이즈를 측정해서 배열에 집어넣어 반환했다.

중간에 해시셋을 빼고 if문으로 바꾸면 최적의 결과가 나오겠지만 일단 여기까지 하기로 했다.

나는 항상 문제를 풀 때 먼저 생각난걸 바로바로 코드로 작성해서 테스트로 돌려본 다음 오류를 하나씩 수정해나갔지만

다음부턴 알고리즘 문제를 풀 땐 한번 내가 손으로 동작을 써본다음에 코드를 작성해서 풀어보는게 좋단걸 배웠다.

이번에도 그런식으로 문제를 풀다가 처음부터 틀린채로 계속 나아가다가 결국 해결하지 못하고 처음부터 다시 시작하는걸 반복했지만 한번 먼저 손으로 써본다음에 작성하면 그렇게 여러번 시도하기 전에 틀린걸 알수있을 것이다.

https://leetcode.com/problems/minimum-length-of-string-after-operations/

3223. 작업 후 문자열의 최소 길이

이번 문제의 경우에 중간 난이도인데  생각하기에 따라 쉬운 문제일 수도, 어려운 문제일 수도 있다.

내 경우에는 처음에 너무 복잡하게 생각해서 시간초과로 몇번 틀렸지만 결국 힌트를 보고 빠르게 풀어냈다.

문자열 s가 주어집니다.
다음 프로세스는 s에서 원하는 만큼 수행할 수 있습니다.

- 인덱스 i의 왼쪽에 s[i]와 동일한 문자가 하나 이상 있고
  오른쪽에도 s[i]와 동일한 문자가 하나 이상 있도록 문자열에서 인덱스 i를 선택합니다.
- s[i]와 동일한 인덱스 i의 왼쪽에서 가장 가까운 문자를 삭제합니다.
- s[i]와 동일하고 인덱스 i 오른쪽에 가장 가까운 문자를 삭제합니다.

달성할 수 있는 최종 문자열 s의 최소 길이를 반환합니다.

예 1:
입력: s = "abaacbcbb"
출력: 5
설명: 다음 연산을 수행합니다.
- 인덱스 2를 선택한 다음 인덱스 0과 3에서 문자를 제거합니다.
- 결과 문자열은 s = "bacbcbb"입니다. 인덱스 3을 선택한 다음 인덱스 0과 5에서 문자를 제거합니다.
- 결과 문자열은 s = "acbcb"입니다.

예 2:
입력: s = "aa"
출력: 2
설명: 아무 연산도 수행할 수 없으므로 원래 문자열의 길이를 반환합니다.

제약 조건: 1 <= s.length <= 2 * 105s는 소문자 영어 문자로만 구성됩니다.

이 문제를 보자마자 나는 나만의 풀이 방식을 먼저 작성하고 코드를 작성했다.

1. s의 첫 문자부터 순서대로 검사한다.
2. 만약 이미 검사한 문자가 나오면 그 위치를 i로 정한다.
3. 앞으로 탐색하여 현재 위치의 문자와 같은 문자를 찾는다.
4. 만약에 앞에 동일한 문자가 있다면 이전 문자와 해당 문잘
5. 삭제된 문자열을 제외하고 다시 정렬한 다음 반복한다.
6. 더 이상 반복할 수 없다면 문자 개수를 반환한다.

주어진 문자열을 배열로 바꿔서 탐색한 다음 만나는 글자들을 비교해서 지우고,

최종적으로 배열의 개수를 반환하도록 설계했었다.

그리고 예전에 코테 공부를 할때 사용했던 재귀함수가 생각나서 그것을 응용해보려고 했다.

class Solution {
    public int minimumLength(String s) {
        int result = 0;

        // 초기 배열 생성
        char[] c = s.toCharArray();
        result = aa(c);

        return result;
    }
    // 재귀함수 생성
    public static int aa(char[] c){
        for(int i = 0; i < c.length; i++){
            if(0 <= i-1){ // 이전값이 있다면
                for(int j = 0; j < i; j++){
                    // 같은 값이 있고 마지막이 아니라면
                    if(c[j] == c[i] && i < c.length-1){
                        // 앞 자리에서 같은 값이 있는지 확인
                        // k에 현재 위치값+1 넣고 반복
                        for(int k = i+1; k < c.length; k++){
                            if(c[k] == c[i] && c[k] == c[j]){
                                char[] re = new char[c.length-2];
                                int count = 0;
                                // 배열에서 값 제거
                                for(int l = 0; l < c.length; l++){
                                    if(j == l || k == l){
                                        continue;
                                    }else if(count == c.length-2){
                                        break;
                                    }
                                    re[count] = c[l];
                                    count++;
                                }
                                return aa(re);
                            }
                        }
                    }
                }
            }
        }
        return c.length;
    }
}

일단 테스트 케이스 1,2,3 까지는 맞았는데 이후에 나오는 테스트 케이스들은 시간 초과로 모두 실패했다.

지금 다시봐도 너무 복잡하고 왜 이렇게까지 했어야 했나 싶은데

그래도 이렇게 코드를 짜면서 재귀함수 작성법을 다시 익힐 수 있었다.

이후에 어떻게 풀어야 할까 고민하다 힌트를 봤는데,

힌트에는 이렇게 써져있었다.

힌트 1
답변을 찾는 데 있어 각 캐릭터의 유일한 중요합니다.

힌트 2
문자가 3 회에 발생하면 프로세스를 수행할 수 없습니다.

힌트 3
문자열에 3번 이상 발생하는 문자가 있다고 가정하면 최대 2개의 문자가 남을 때까지 이 문자 중 2개를 반복해서 표시할 수 있습니다.

이걸 보고 머리를 한 대 맞은 느낌이었다.

정답은 정수를  반환하면 되는 건데... 그리고 모든 문자열에서 같은 문자가 3개 이상 존재할 수 없는데...

그래서 바로 모든 코드를 지우고 다시 처음부터 생각해 보았다.

그 결과 이런 결론이 도출되었다.

문자열의 빈도수를 세시오
   -> 해당 문자가 3개 이상 있는가?
         -> 예
              -> 그렇다면 /3을 하시오
         -> 아니오
              -> 그렇다면 다음 문자에 대한 계산을 하십시오
  -> 최종적으로, 모든 문자의 개수가 3개 미만일 때 총개수를 출력하시오

이렇게 생각을 정리하고 다시 코드를 작성하니 좀 더 깔끔하고 더 빠르게 작성이 가능했다.

그리고 중간중간 디버깅 하면서 내가 틀린 부분을 다시 수정해 나갔다.

class Solution {
    public int minimumLength(String s) {
        int result = 0;
        
        int[] tempIndex = new int[26];

        // 초기 배열 생성 (빈도수 측정)
        for(char ch : s.toCharArray()){
            tempIndex[ch - 'a']++;
        }
        
        // a-z까지 반복
        for(int a : tempIndex){
            int temp = 0;
            // 3보다 크다면
            if(a >= 3){
            	// 나눈 값이 3보다 크다면
                if((a/3) + (a%3) >= 3){
                    temp = (a/3) + (a%3);
                    // 3보다 작아질때 까지 반복
                    while(true){
                        temp = (temp/3+temp%3);
                        if(temp < 3){
                            break;
                        }
                    }
                    result += temp;
                }else{
                    result += (a/3) + (a%3);
                }
            }else{
                result += a;
            }
        }
        return result;
    }
}

이렇게 작성하여 제출하였더니

런타임 10ms, 메모리 46.3MB로 양호한 성적이 나왔다.

이번 문제를 풀어보면서 느낀점은

머릿속이 복잡해질땐 과감하게 모두 지우고 환기시킨 다음

다시 간단하게  생각해 보는 게 참 중요하다는 생각이 든다.

https://leetcode.com/problems/word-subsets/description/

이번 문제는 꽤 난이도가 있었다.

분명 중간 난이도인데 나한테는 정말 어려웠다.

먼저 문제를 보자

두 개의 문자열 배열 words1과 words2가 주어졌습니다.
문자열 b는 b의 모든 문자가 다중도를 포함하여 a에 나타나면 문자열 a의 하위 집합입니다.
예를 들어, "wrr"은 "warrior"의 하위 집합이지만 "world"의 하위 집합은 아닙니다.
words1의 문자열 a는 words2의 모든 문자열 b에 대해 b가 a의 하위 집합이면 범용입니다.
words1의 모든 범용 문자열의 배열을 반환합니다.
답은 어떤 순서로든 반환할 수 있습니다.
 
예제 1 :
Input : words1 = [ "amazon", "apple", "facebook", "google", "leetcode"],
            words2 = [ "e", "o"]
Output : ["facebook", "google", "leetcode"]

예제 2 :
Input : words1 = [ "amazon", "apple", "facebook", "google", "leetcode"],
            words2 = [ "l", "e"]
Output : [ "apple", "google", "leetcode"]
 
제약 조건:
- 1 <= words1.length, words2.length <= 10⁴
- 1 <= words1[i].length, words2[i].length <= 10
- words1[i]와 words2[i]는 소문자 영어 문자로만 구성됩니다.
- words1의 모든 문자열은 고유합니다.

이 문제를 보고 내가 이해한건 2개의 문자열 배열이 주어지면,

words2의 문자가 words1에 포함되어있는지 확인하는 문제인 줄 알았다

그래서 아래와 같이 작성하여 제출했다.

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
		
        // 문자열 반복
        for(String t : words1){
            for(int i = 0; i < words2.length;i++){
            	// words2에 있는 문자가 없으면 중지
                if(!t.contains(words2[i])){
                    break;
                }
                // 마지막까지 해당 문자가 존재한다면
                else if(i == words2.length-1 && t.contains(words2[i])){
                    result.add(t);
                }
            }
        }
        return result;
    }
}

간단하게 저번에 배운 contains 함수를 사용해서 문자열에 해당 문자가 포함되는지 확인하는 코드이다.

그런데 바로 틀려버렸다..

예제 3 : 
Input : words1 =["amazon","apple","facebook","google","leetcode"]
            words2 =["lo","eo"]
내 출력 : [ ]
답안 : ["google","leetcode"]

여기서 첫번째 문제는 나는 한개의 문자가 들어있는지 비교하도록 짰는데, 문자열의 길이가 2이상이란 것과

두번째 가장 큰 문제는 "lo", "eo" 에 보면 "o"가 2번씩 들어가는데 "leetcode"에 보면 "o"가 하나밖에 안들어간다..

이중에서 두번째 문제때문에 정말 머리아팠다.

그래서 이번에는 그 부분을 수정해서 새롭게 코드를 짰다.

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
        // 해시맵 생성
        HashMap<Character,Integer> h1 = new HashMap<Character,Integer>();
        HashMap<Character,Integer> h2 = new HashMap<Character,Integer>();
        // 문자의 빈도수를 계산해서 풀어야함
        // 먼저 words2의 문자 빈도수를 계산해놔야함
        char a;
        for(String temp : words2){
            for(int i = 0; i < temp.length(); i++){
                a = temp.charAt(i);
                // 일치하는 키 값이 있다면 값 증가
                if(h1.containsKey(a)){
                    h1.replace(a,h1.get(a) + 1);
                } else{ // 없으면 생성
                    h1.put(a,1);
                }
            }
        }
        
        // 만들어진 해시맵을 기준으로 입력받은 문자열에서 개수를 세서 확인
        for(String temp : words1){
            for(int i = 0; i < temp.length(); i++){
                // 분리한 문자열에서 같은 문자가 있는지 확인
                a = temp.charAt(i);
                // 찾는 단어와 일치하는지 검색
                if(h1.containsKey(a)){
                    // 이미 존재한다면 값 증가
                    if(h2.containsKey(a)){
                        h2.replace(a,h2.get(a) + 1);
                    }else{ // 없으면 생성
                        h2.put(a,1);
                    }
                }
            }
            // 값을 넣는 동작이 모두 끝남 
            if(h1.size() == h2.size()){
                for(Character key : h1.keySet()){
                    if(h1.get(key) >= h2.get(key) && !result.contains(temp)){
                        result.add(temp);
                    }
                }
            }
            // 초기화
            h2.clear();
        }

        
        return result;
    }
}

이번에는 해시맵을 써서 빈도수를 체크하고 비교하게 짰는데

일단 3번째 예제는 맞았는데 새로운 문제가 나타났다.

예제 4.
Input : words1 =["amazon","apple","facebook","google","leetcode"]
           words2 =["e","oo"]
내 출력 : ["facebook","google","leetcode"]
답안     : ["facebook","google"]

입력으로 같은 문자열이 두개 이상 들어오는건 예상하지 못했다..

그래서 오랜 시간을 고민하다가 결국 솔루션을 찾아봤고 덕분에 해결했다.

솔루션 출처

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
		
        // 최대 빈도수
        int[] maxIndex = new int[26];
        int[] tempIndex = new int[26];
        // 문자의 빈도수를 계산해서 풀어야함
        // 먼저 words2의 문자 빈도수를 계산해놔야함
        for(String w2 : words2){
            Arrays.fill(tempIndex,0);
            // .toCharArray는 문자열을 문자단위로 쪼개줌
            for(char ch : w2.toCharArray()){
                tempIndex[ch - 'a']++;
            }
            // 서로 비교해서 더 큰값을 저장
            for (int i = 0; i < 26; ++i){
                maxIndex[i] = Math.max(maxIndex[i], tempIndex[i]);
            }
        }
        // 최대 빈도수를 구했으니 하나씩 해당하는 값을 올려서 최대 빈도수랑 비교해야함
        // words1의 값을 분리
        for(String w1 : words1){
            int[] index = new int[26];
            boolean tag = true;

            for(char ch : w1.toCharArray()){
                index[ch - 'a']++;
            }
			
            // maxIndex보다 작다면 false
            for(int i = 0;i<26;i++){
                if(maxIndex[i] > index[i]){
                    tag = false;
                    break;
                }
            }

            if(tag){
                result.add(w1);
            }
        }

        return result;
    }
}

정말 막힐때는 솔루션을 보고 내 원래 코드랑 비교하면서 배우는것도 하나의 방법인 것 같다.

https://leetcode.com/problems/counting-words-with-a-given-prefix/

주어진 접두어로 단어세기.

이번 일일 문제는 너무 간단해서 딱히 쓸 말이 없다

class Solution {
    public int prefixCount(String[] words, String pref) {
        int count = 0;
        
        for(String text : words){
        	// 문자열의 첫머리가 pref와 일치한다면
            if(text.startsWith(pref)){
                count++;
            }
        }
        return count;
    }
}

https://leetcode.com/problems/count-prefix-and-suffix-pairs-i/

이번 문제도 문자열을 비교하는 문제이다.

접두사 및 접미사의 쌍 계산 이라고 번역이 되는데 문제를 보자.

당신에게 0으로 시작하는 문자열 배열 words가 주어졌습니다.
두 문자열 str1과 str2를 인수로 받는 isPrefixAndSuffix라는 부울 함수를 정의해봅시다:

isPrefixAndSuffix(str1, str2) 함수는 str1이 str2의 접두사이면서 동시에 접미사인 경우 true를 반환하고,
그렇지 않은 경우 false를 반환합니다.

예를 들어, isPrefixAndSuffix("aba", "ababa")는 aba가 ababa의 접두사이자 접미사이기 때문에 true를 반환하지만,
isPrefixAndSuffix("abc", "abcd")는 false를 반환합니다.

이제 주어진 words 배열에서 i < j를 만족하는 인덱스 쌍 (i, j)의 수를 반환하세요. 이때, isPrefixAndSuffix(words[i], words[j])가 true인 경우만 포함됩니다.

그리고 예제를 보면

예제 1.
Input: words = ["a","aba","ababa","aa"]
Output: 4
Explanation: In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true.
i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true.
i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true.
i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true.
Therefore, the answer is 4.

예제 2.
Input: words = ["pa","papa","ma","mama"]
Output: 2
Explanation: In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true.
i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true.
Therefore, the answer is 2.

딱 이 예제까지만 봤을때는 아 이 문제는 0번째 배열의 값부터 시작해서 마지막 값까지 비교해서

같은 문자열이 앞 뒤에 존재하는지 확인하는 문제구나! 라고 생각했다

그래서 그대로 코드를 짜 봤는데...

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int count = 0;

        for(int i = 0; i < words.length; i++){
            for(int j = 0; j < words.length; j++){
                // 동일한 문자인지 체크
                if(!words[i].equals(words[j])){
                	// 접두사와 접미사가 동일한지 비교
                    if(words[i].startsWith(words[j]) && words[i].endsWith(words[j])){
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

여기서 포인트는 startsWith() 함수와 endsWith() 함수다.

각각 문자열 앞자리와 뒷자리 부분이 동일한지 비교하여 boolean 값으로 반환하는 함수이다.

그래서 결과는 1,2 예제는 통과 했는데 마지막 예제를 통과하지 못했다.

예제 3.
Input: words = ["abab","ab"]
Output: 0
Explanation:
이 예에서 유일한 유효한 인덱스 쌍은 i = 0 및 j = 1이고
isPrefixAndSuffix("abab", "ab")는 false입니다. 그러므로 답은 0이다.

내 코드대로 계산한다면 "abab"에는 앞 뒤로 "ab", "ab"가 들어가기에 ture, 즉 1을 반환했는데 답은 false, 0 이였다.

이것때문에 어디서부터 잘못된건지 내가 뭘 잘못 이해하고 있는지 고민하다가 결국 문제 하단에 있는 토목록에서 힌트를 얻었다.

바로 문제에 하단에 나와있는 i < j 를 확인하란 것이였다.

그말은 즉슨 i 번 부터 j까지 확인하라, i의 값이 j에 접두사 및 접미사가 되느냐? 를 물어보는 문제였다.

고로 "abab" 가 i 이고, "ab"는 j 이기 때문에 "abab"가 "ab"의 접두사나 접미사가 될순 없기 때문에 틀린것이였다.

그래서 이를 참고해 코드를 수정했다.

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int count = 0;

        for(int i = 0; i < words.length; i++){
            for(int j = i+1; j < words.length; j++){
                if(words[j].startsWith(words[i]) && words[j].endsWith(words[i])){
                    count++;
                }
            }
        }
        return count;
    }
}

더 간결해졌고 정답도 맞췄다.

항상 문제를 잘 읽고 먼저 이해한 다음에 코드를 작성해보자.

또 필요한 함수가 있는지 한번 더 체크해보고 작성해야겠다.

https://leetcode.com/problems/string-matching-in-an-array/description/

이 문제는 Input으로 여러 개의 문자열로 이루어진 리스트 타입 words를 입력받는데

예제는 아래와 같다.

예제 1.
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
해설 : "as"가 "mass"에 포함되고 "hero"가 "superhero"에 속하기 때문에 답은 ["as","hero"]가 된다

예제 2.
Input: words = ["leetcode","et","code"]
Output: ["et","code"]
해설: "et", "code" 는 "leetcode"에 속한다.

예제 3.
Input: words = ["blue","green","bu"]
Output: []
해설 : 서로 포함되는 글자가 없기 때문에 답이 없다. 

이 문제를 보고 저번에 풀었던 RansomNote 문제에서 내가 처음에 작성했던 코드가 생각났다.

이번에는 반드시 맞을 것이라 생각하고 열심히 코드를 짠 결과

class Solution {
    public List<String> stringMatching(String[] words){
    	// 중복 제거용 set
        Set<String> set = new HashSet<>();
        int len = 0;
		
        // words 문자열을 하나씩 꺼냄
        for(String temp : words){
            len = temp.length();
            // 비교용 문자열을 꺼냄
            for(String temp2 : words){
            	// 만약 문자열이 같지않고, 문자열의 길이가 비교용 문자열보다 길다면
                if(!temp.equals(temp2) && len < temp2.length()){
                    for(int i = 0; i < temp2.length(); i++){
                    	// 문자열의 길이가 초과되지 않을때 까지 잘라서 비교한다.
                        if(len+i <= temp2.length()){
                            if(temp2.substring(i,len+i).equals(temp)){
                                set.add(temp);
                            }
                        }
                    }
                }
            }
        }
        // 결과를 다시 List<String> 타입으로 변환한다.
        List<String> result = new ArrayList<>(set);

        return result;
    }
}

이렇게 지저분한 코드가 완성됐다.

제출결과 맞긴 했는데 메모리를 45.1MB나 먹고 시간도 12ms나 걸렸다.

평균적으로 꼴찌였기에 새롭게 다시 짜기로 했다.

그러다가 Java에 문자열이 포함되어 있는 여부를 확인할 수 있는 함수인 .contains( )가 있다는 것을 알았고,

그 함수를 사용해서 다시 작성하였다.

class Solution {
    public List<String> stringMatching(String[] words){
    	// 중복 제거용 set
        Set<String> set = new HashSet<>();
        
        for(int i = 0; i < words.length;i++){
            for(int j = i+1; j < words.length; j++){
            	// 해당 문자열에 포함된다면...
                if(words[i].contains(words[j])){
                    set.add(words[j]);
                }else if(words[j].contains(words[i])){
                    set.add(words[i]);
                }
            }
        }
		// List<String>타입으로 변환
        List<String> result = new ArrayList<>(set);

        return result;
    }
}

여기서 if문이 있는데 한 번 더 비교한 이유는 그냥 if(words [i]. contains(words [j])) 만 작성하면

관련된 모든 값이 다 나와서 한 번 더 반대로 검증해야 했다.

코드는 여전히 지저분하지만 결과는 확실히 좋았다.

실행 시간은 5ms가 되었고 메모리는 42.6MB가 되었다.

그래도 아직 평균에 못 미치는데 그건 다음에 다시 봐야겠다.

https://leetcode.com/problems/ransom-note/description/

해당 문제는 String 타입의 ransomNote와 magazine가 주어지는데

여기서 ransomNote 에 포함된 알파벳들이  magazine에도 동일한 개수가 들어가있는지 확인하고 Boolean값을 반환하는 문제다.

예제1.

Input: ransomNote = "a", magazine = "b"
Output: false

이경우 'a'가 magazine에 포함되어 있지 않기때문에 false를 반환한다.

예제 2.

Input: ransomNote = "aa", magazine = "ab"
Output: false

여기서도 ransomNote에 'a'가 2개 포함되어있지만 magazine에는 'a'가 1개밖에 없기 때문에 false를 반환한다.

예제 3.

Input: ransomNote = "aa", magazine = "aab"
Output: true

이 경우에는 'a'값 두개가 magazine에 포함되어 있기 때문에 true를 반환한다.

나는 처음에 이 문제를 단순히 ransomNote의 값이 magazine에 포함되는 것인줄 알고 이렇게 코드를 작성했었다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int s = ransomNote.length();

        for(int i = 0; i < magazine.length(); i++){
            if(s+i <= magazine.length()){
                if(magazine.substring(i,s+i).equals(ransomNote)){
                    return true;
                }
            }
        }
        return false;
    }
}

해당 코드는 ransomNote의 길이만큼 magazine을 잘라서 비교하는 연산을 한다.

기본적으로 표시된 테스트케이스 3개는 모두 통과했기에 이 답이 맞는줄 알았으나

예제 4.

Input: ransomNote = "aab", magazine = "baa"
Output: false
Expected: true

이 예제에서 틀리고 말았다.

왜 틀린거지 false가 맞는거 아닌가 했는데, 애초에 문제 자체를 잘못 이해하고 있었다.

저 예제에서도 문자열의 순서가 중요한게 아니라

ransomNote에 'a'가 2개 'b'가 1개 있고 magazine 에도 같은 양의 알파벳이 있는가를 비교하는 문제였다.

그래서 코드를 수정했고 정답을 맞췄다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
    	// Map 생성
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		
        // for-each문을 이용하여 magazine의 값을 순서대로 꺼냄
        for(char temp : magazine.toCharArray()){
        	// Map에 [문자,개수] 쌍으로 삽입
            map.put(temp,map.getOrDefault(temp,0)+1);
        }
        // 다시한번 for-each문을 통해 ransomNote값을 순서대로 꺼냄
        for(char temp2 : ransomNote.toCharArray()){
        	// 만약에 magazine에 해당 문자가 없다면 false
            if (!map.containsKey(temp2)){
                return false;
            }
            // 존재한다면 -1 시키고 0이 되면 Map에서 제거
            int count = map.get(temp2)-1;
            if (count > 0){
                map.put(temp2,count);
            } else{
                map.remove(temp2);
            }
        }

        return true;
    }     
}

Map을 이용해 각 문자의 개수를 세고 하나씩 비교하는 방식을 사용하였다.

이 방법이 가장 효과적인 방법은 아닌것 같은데 더 좋은 방법을 찾아봐야겠다.

https://leetcode.com/problems/middle-of-the-linked-list/description/

이 문제는 연결리스트에서 중간값을 찾아 중간부터 출력하는 문제다.

예시1.

Input : head = [1,2,3,4,5]

Output : [3,4,5]

중간값이 3이기 때문에 [3,4,5]가 출력되어야 한다.

예시2.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]

중간값이 4이기 때문에 [4,5,6]이 출력되어야 한다.

이 문제에서는 주석으로 ListNode의 구조가 주어지는데 이를 보고 출력을 결정하면 된다.

이 문제를 해결하는 핵심은 중간 노드를 어떻게 찾느냐인데,

두개의 노드를 만들어서 계산하면 된다.

fnode : 중간 지점을 반환할 노드

lnode : 2개씩 이동하며 연결 리스트를 2분할 하는 노드

즉, lnode가 2개씩 노드를 건너뛰어서 연결 리스트를 반으로 줄이고, fnode는 1개씩 이동하여 중간 지점을 정한다.

아래는 그것을 구현한 코드이다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fnode = head; // 시작 노드
        ListNode lnode = head; // 마지막 노드
		
        // 무한 반복
        while(true){
            try {
                lnode = lnode.next.next; // 마지막 노드는 2개씩 움직임
            }
            catch (NullPointerException e){ // 만약에 끝까지 도달했다면 탈출
                break;
            }
            fnode = fnode.next; // 시작 노드를 옮김
        }

        return fnode;
    }
}

여기서 아쉬운점은 내가 lnode가 끝에 다다랐을때 null을 반환하는것을 어떻게 처리할지 고민하다가

그냥 try-catch문으로 체크했는데 일단 작동은 잘 된다...;;