작은 기록공간

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가 나왔다.

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

2번째 프로젝트의 시작

이번 주부터 2번째 프로젝트가 시작되었다.

이번 프로젝트는 Spring을 활용하여 웹 페이지를 만드는 게 목표인 프로젝트로써

저번 프로젝트가 DB설계만 했다면 이번에는 직접 설계한 DB를 활용하여 실제로 구현하는 프로젝트이다.

프로젝트를 하기 앞서 새로운 팀원들과 인사를 나눴는데 이전에도 그랬지만 모두 열정이 넘치는 분들이어서 좋았다.

Spring을 아직 경험해보지 못한 분도 계셨고 이전 직장에서 사용해보거나 나처럼 프로젝트를 진행해 보신 분도 계셨다.

그래서 일단은 설날에 프로젝트에 필요한 Spring을 공부해오기로 하였고 이 기회에 나도 리마인드 하는 시간을 가지기로 했다.

프로젝트 구성을 하기전...

이번 프로젝트에선 모두 모여서 이전 프로젝트에서 맘에 안 들었거나 문제가 되었던 부분에 대해서 소통하고 진행하였다.

팀원들은 여러 가지 의견을 내주었고 이러한 분위기가 정말 마음에 들었다.

또한 프로젝트에 대한 아이디어를 각자 한 개 이상으로 상세하게 구상해서 모두에게 발표하는 식으로 선정하였다.

회의 끝에 2개의 프로젝트가 남았는데 하나는 일정관리 사이트, 나머지 하나는 팀프로젝트 관리 사이트였고,

최종적으로 팀 프로젝트 관리 사이트가 선정되었다.

이전 프로젝트에 대한 기억

이전에 나는 졸업작품으로 Spring을 활용하여 '웹 주문 키오스크 시스템'을 만든 적이 있었다.

이때 우리 팀의 문제점을 생각해 보면

1. 버전관리 문제

      -> 모든 프로젝트 파일을 디스코드로 공유했었다.

2. 기능 명세서는 있었지만 상세한 API 명세서의 부재

    -> 이 때문에 프런트엔드와 백엔드 사이에서 어떻게 값을 넘겨주고 받을 건지에 대한 정의가 없어서 많은 혼선을 겪었다.

3. DB 이름 규칙 부재

   -> DB 이름에 대한 규칙이 정확히 없었기에 서로 다르게 작성하다 마지막 통합과정에서 충돌이나 많은 수정을 해야 했다.

4. 처음부터 너무 많은 기능을 설계

   -> 너무 많은 기능을 설계한 탓에 제 기한에 맞추느라 급급했고 완성했지만 미처 공개하지 못한 기능도 있었다.

5. Spring에 대한 이해도 부족

   -> 왜 이렇게 써야 하는지, 왜 이렇게 작동하는지 모르고 그냥 이렇게 해야 한다!라고 생각해서 썼던 것들이 많았다.

대충 정리하면 이런 문제들이 있었고 이번 프로젝트에서는 같은 실수를 하지 않기 위해 많은 공부를 해야겠다고 생각했다.

시작이 반이다

프로젝트를 시작하기 전 팀원들과 많은 이야기를 나누었고 일단 시작하기 전부터 계획을 확실하게 잡았다.

먼저, 위에서 말했던 '처음부터 너무 많은 기능의 설계' 부분에 대한 한계를 정했다.

최소한의 기능 즉, 최소한 우리의 프로젝트가 동작하는 기준치를 설정했고 생각보다 아주 많이 낮췄다.

물론 많은 기능을 넣으면 좋지만 우리에게 주어진 시간은 단 2 달이고, 이 안에 모든 걸 완성할 수 있다는 생각은 들지 않는다.

그렇기에 처음부터 최소치를 정하고 이제 모두 완성되고 난 이후에 시간이 남는다면 하나씩 추가하는 방향으로 설정하였다.

오늘 친구와 스터디를 하면서 API 명세서를 작성하는 것이 도움이 될 것이라고 배웠다.

아직 팀원들에게 말하진 않았지만 이 부분도 같이 도입하여서 확실한 규칙이나 기능을 설정하면

더 빠르고 효과적인 구현을 할 수 있을 것이라 생각한다.

이렇게 프로젝트 초기에 기반을 잘 다져놔야 그 위에 어떤 건물을 지어도 튼튼하고 안정적으로 운영할 수 있다고 생각한다.

그리고 지금까지 배운 것들을 제대로 활용하려면 이 기회에 적용하는 게 맞다고 생각한다.

최종적인 목표

처음 팀원들끼리 회의하던 내용 중에 하나는 우리 팀의 최종 목표를 어디까지로 할 것이냐였다.

나와 다른 팀원 2명은 배포까지 하기를 원했고 다른 분들은 Spring에 대해서 많이 배워가는 것이 목표였다.

개인적인 생각으로 물론 프로젝트를 진행해서 Spring에 대해 배워가는 건 매우 중요하고 핵심적인 일이라고 생각하지만

마지막으로 배포까지 하면 더 많이 배울 수 있을 것이라 생각한다.

그리고 나 또한 이번 프로젝트로 Spring에 대해서 더 확실하게 배워서 성장하고 싶다.

이전에 했던 프로젝트는 삽질 그 자체였지만 이제 삽질한 구덩이에 튼튼한 기반을 세워서 높은 건물을 세우고 싶다.

지금까지 배웠던 것들을 활용하여 성공적으로 프로젝트를 완성하고 배포하는 것이 목표이다.

Ps.
아직 부족한 부분이 많지만 그래서 더 좋다고 생각한다.
그만큼 아직 배울 것도 많고 얻을 수 있는 것도 많기 때문이다.

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://www.acmicpc.net/problem/2231

이 문제는 부분합을 구하는 문제인데,

알고리즘을 보니 브루트포스 알고리즘으로 분류되어 있어서 정말 무식하게 풀었다...

내가 생각한 건 1부터 주어진 수까지 1씩 값을 증가시키면서 숫자를 한 자리씩 분리해서 더했다

여기서 num/2를 한 이유는 범위를 반 정도라도 줄이기 위해서 사용했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int result = 0;
        int sum = 0;
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        // i 부터 num 까지 반복
        for (int i = num/2; i < num; i++) {
            // 자릿수 더하기
            for (int j = 0; j < String.valueOf(i).length(); j++){
                // i번째 숫자를 한자리씩 분해하여 정수형으로 바꾼 다음 sum에 더함
                sum += Character.getNumericValue(String.valueOf(i).charAt(j));
            }
            sum += i;

            if(sum == num) {
                result = i;
                break;
            }
            // 초기화
            sum = 0;

        }
        System.out.println(result);
    }
}

정말 끔찍하게 풀었지만 일단 맞긴했다;;

아마 브루트포스 알고리즘이 아니었으면 바로 틀렸을 것 같다.

여기서 더 개선할 수 있는 방법을 생각해 보면

1. 뒷자리 수부터 차례로 내려간다

2. 자릿수 분해를 문자열로 나누는 게 아니고 산술연산으로 나눈다.

이 정도가 생각난다.

그래서 한번 Copilot 한테 내 코드의 문제점과 가장 좋은 설루션이 뭐가 있냐고 물어봤다.

이 문제는 분해합 (Decomposition Sum)에 관한 문제로, 문제의 입력 숫자 N에 대한 생성자 M을 찾는 것입니다.

주어진 해결 방법은 전체 숫자를 순차적으로 검사하므로 시간복잡도가 높다는 단점이 있습니다. 이를 개선할 수 있는 방법을 제안드릴게요.

더 나은 방법
실제로 이 문제를 해결하는 더 좋은 방법은 역시 브루트포스를 사용하는 것이지만, 모든 숫자를 다 검사할 필요는 없습니다. 다음의 방법으로 계산을 줄일 수 있습니다:

1. 최소 탐색 범위 설정:
   - 보통 생성자의 범위는 N - 9\*자릿수 정도로 한정할 수 있습니다. 예를 들어, 입력 숫자가 100이라면, 100 - 9\*3 = 73부터 시작할 수 있습니다. 이는 각 자리 숫자가 9인 최대 경우의 수를 고려한 것입니다.

2. 생성자 계산:
   - 각각의 숫자에 대해서 각 자리의 숫자 합을 구하고 이를 더해 나갑니다. 이를 통해 분해합을 계산합니다.

다음은 개선된 코드 예제입니다:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int result = 0;

        for (int i = Math.max(1, num - 9 * String.valueOf(num).length()); i < num; i++) {
            int sum = i;
            int temp = i;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }

            if (sum == num) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

설명
- 범위 설정: `num - 9 * String.valueOf(num). length()`를 이용해 최소 탐색 범위를 설정합니다.

                    예를 들어, `100`인 경우 `100 - 9*3 = 73`부터 시작합니다.
- 생성자 계산: `i`의 각 자릿수를 더하는 방식으로 분해합을 계산합니다.

이렇게 하면 불필요한 계산을 줄여 성능을 개선할 수 있습니다. 이 방법을 사용하면 좀 더 효율적으로 문제를 해결할 수 있을 거예요. Happy coding! 🎉

솔직히 범위를 저렇게 까지 줄일 수 있을 줄은 생각도 못했다.

for문에 대한 설명을 조금 더 자세히 물어봤는데

1. String.valueOf(num). length() : 

num을 문자열로 변환하여 길이(자릿수)를 구하고,

2. num - 9 * String.valueOf(num). length():

탐색의 최소 범위를 설정하기 위해서 num에

1의 자리 숫자 중에 가장 큰 9를 자릿수와 곱한 값을 뺀다.

예를 들어, num이 100이라면, 100 - 9 * 3 = 73이 된다.

3. Math.max(1, num - 9 * String.valueOf(num). length()):

음수를 피하기 위해서  1보다 작다면 1을 반환한다.

정말 죽었다 깨어나도 이렇게 생각하진 못했을 것 같다

다음으로 while문에서는

while (temp > 0): temp가 0보다 클 때까지 반복합니다.

• sum += temp % 10: temp의 마지막 자릿수를 sum에 더합니다.
• temp /= 10: temp를 10으로 나누어 마지막 자릿수를 제거합니다.

이렇게 자릿수를 더하고 그 결과를 입력받은 값과 비교에서 같으면 반복문을 종료하고 출력한다.

정말 여러모로 많이 배울 수 있는 시간이었다.

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로 양호한 성적이 나왔다.

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

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

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

이번주에 배운 것

이번 주는 저번 주에 이어 Java에 대해 더 깊이 배웠다.

배열, 오버로딩, 오버라이딩, 상속, 다형성 등을 다루었고,

내가 이해하고 있던 것보다 더 심화된 내용을 배워 많은 것을 얻을 수 있었다.

원래 나는 '이 함수는 원래 이런 역할을 하는거지' 하고 사용했지만,

강의에서는 세세한 동작 과정을 알려주어 생각했던 것보다 훨씬 유익했다.

예를 들어 예외 처리의 경우, 보통 try-catch문을 사용하지만 특별한 경우가 아니면 해당 오류에 대한 Exception을 할당하거나,

범위가 넓다면 catch (Exception e)로 쓰는 것이 일반적이었다.

여기서 왜 catch (Exception e)로만 해도 모든 에러가 잡히는지에 대해

바로 이전에 배운 상속 개념을 가져와서 설명해주시니 구조적으로 이해가 됐다.

덕분에 몰랐던 사실들도 많이 배울 수 있었다.

인텔리제이의 오류 해결

Java 실습을 할 때는 항상 인텔리제이를 사용하는데,

처음 인텔리제이를 사용할 때부터 지금까지 프로젝트를 실행할 때 가끔 프리징이 걸려서 강제종료를 해야하는 상황이 발생했다.

강사님 뿐만 아니라 Windows 노트북을 사용하는 모든 수강생들이 불편을 겪었다. (Mac은 해당이 안됐다)

이유를 알 수 없는 오류로 계속 흐름이 끊기는 일이 빈번했는데,

이번에 그 해결법을 찾아 공유하여 다시 쾌적하게 강의를 들을 수 있게 되었다.

이 문제를 해결하지 못했다면 강의를 듣는 내내 인텔리제이에 대한 불쾌감만 더 늘어났을 것 같다.

코딩 테스트 연습

원래 대략 2주전만 해도 코딩테스트 스터디 모임이 있었다.

그런데 왜 과거형이냐면 있었는데 갑자기 어느순간 공중분해가 되어버려서 혼자서 매일 따로 문제를 풀고있다.

요즘은 매일 LeetCode에서 일일문제를 풀어 블로그에 게시하고 있고, 하루 종일 고민해도 안풀리면 그냥 솔루션을 보고

내 코드와의 비교 분석과 솔루션을 분석하며 공부하고 있다.

한 주를 마무리 하며...

이번 한 주는 저번보다 조금더 알차게 보내고 있다는 생각이 든다.

매일 코테 문제를 풀고, 블로그에 글쓰고, 깊이 있는 강의를 듣고, 또 정리하고...

이번년도는 시작부터 꽤 순항하고 있다는 생각이 든다.

ps.
블로그에 서식 기능이 있는거 같던데 서식을 하나로 통일해야겠다.

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;
    }
}

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

인텔리제이 프로젝트 실행 시 무한 로딩 해결 방법 (Windows만 해당)

버전: 24.3.x

1. 메인 메뉴로 이동 -> 도움말-> 작업 찾기 (또는 Ctrl+Shift+A / Cmd+Shift+A)

2. "레지스트리"를 입력하고 처음 찾은 항목을 선택

3. 열린 대화 상자에서 입력을 시작하여 profiler.widget.in.run.console -> 비활성화 (체크해제)

출처 - https://youtrack.jetbrains.com/issue/IDEA-363384/IDE-hangs-after-running-same-Java-code-several-times-Run-button-shows-a-spinner-forever

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;
    }
}