'2024/09/13'에 해당되는 글 2건

https://hwan-shell.tistory.com/23

처음에 문제를 받고 번역기를 통해 문제를 접했을 때 '이게 뭔 소리지?' 라고 느꼈습니다.  문제의 규칙도 잘 이해가 안가고....

그러다가 인터넷에 다른사람이 어떻게 풀었는지 보고, 몇번의 실행과정을 거치니 이해가 갔습니다.

쉽게 설명하자면!!

1. 홀수개의 배열이 주어집니다.(무조건)

2. 홀수개의 배열 요소중(정수) 단 하나의 요소만 제외하곤 모두 중복되는 숫자입니다.

ex)[1,1,2,2,4,5,5] = 4, [1,2,3,4,5,6,1,2,3,4,5] = 6, [1,2,1,2,2,2,3,2,3,2,7] = 7

3. 중복되는 숫자를 제외한 값을 리턴하면 됩니다.

4. 중복되는 숫자는 2개씩 짝을 이루게 됩니다.

ex)[1,3,2,3,1,2,4] 이렇게 배열 요소가 있다면,

a[0]과 a[4]이 짝, a[1]과 a[3]이 짝, a[2]와 a[5]이 짝. 이런식으로

즉, 배열요소중 짝이 없는 정수 1개를 찾아라!! 입니다.

소스 코드

int solution(int A[], int N) {
    int i, result = 0;
     
    for(i = 0; i < N; i++)
        result ^= A[i];
     
    return result;
}​

다른 예제

우선, 제 힘으로 푼 문제가 아닙니다. 문제 자체가 이해가 가질 않아 구글링을 통해 문제 관련 자료를 찾던 중

누가 풀어놓은 소스코드를 봤고, '아차!! ' 하고 깨달으면서 제 자신의 부족함을 느꼈습니다.

애초에 짝을 이뤄 중복되는 숫자를 지우고 하나의 숫자만을 남기게 하려면 XOR로 해결이 가능하고,

제가 이걸 진작에 알았다면 관련 자료를 찾지는 않았을 것입니다.

그래도 문제 풀이에 대해 이해는 했으니 적어보겠습니다.

XOR은 암호화 할때도 주로 쓰이는 알고리즘 입니다. 중복을 제거할때도 좋은 녀석이죠.

XOR은 숫자가 같으면 0, 숫자가 다르면 1을 반환합니다.

ex) 1111 xor 1111 = 0000,  1010 xor 1010 = 0000,   0101 xor 1010 = 1111.

저 문제 풀이방법은 result라는 변수에 어떤 정수와 xor을 하면 순서와 상관없이 

'한 요소'를 제외한 모든 요소가 중복을 제거하게 되고(0으로 만들어 버리죠),

마지막엔 중복이 안된 한 요소만 남게되는 것입니다.

https://hwan-shell.tistory.com/16

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

문제.

설명

쉽게 설명하자면 정수N을 2진수로 표현했을때 1과 1사이의 0의 Gap 즉, 0의 갯수를 구하는 문제 입니다.

단, 1과 1사이의 0의 갯수 중 가장 긴 값을 반환해야 합니다.

ex)

10000001001 -> 6

100000 -> 0(1과 1사이의 0의 갯수가 아님으로)

111110 -> 0(마찬가지)

1011 -> 1

1010101 -> 1

이정도 예시와 결과면 충분히 이해하셨으라 생각합니다.

저는 C언어로 문제를 풀었고 앞으로도 C로 풀 생각입니다.

소스코드

int solution(int N) {
    int num = 0, count = 0, flag = 0, result = 0;

    do {
        num = N % 2;
        N /= 2;

        if (num == 1)
            flag++;
         
        if(flag == 1 && num == 0){
            count++;
        }else if(flag == 2){
            if(result < count){
                result = count;
                count = 0;
                flag = 1;
            }else{
                count = 0;
                flag = 1;
            }
        }
    } while (N > 0);

    return result;
}

저는 flag를 이용해 1을 만남 시점에서 count를 세게 했으며 flag가 2가 되면 초기화 하는식으로 했습니다.

do ~ while() 문을 통해 2진수의 마지막 자릿 수 까지 계산하도록 했습니다.