백준 1940번 주몽 :: 마이구미

이번 글의 주제는 백준 알고리즘 사이트의 문제 "주몽"이라는 문제이다.

https://www.acmicpc.net/problem/1940

1차원 배열을 활용하여 푸는 문제이다.

아직 1차원 배열을 응용하는 법이 능숙하지 못하는 분들에게 좋은 풀이라 생각한다.
- 재채점으로 실패

 

문제는 입력되는 번호들 중 2개를 골라 합한 것이 필요한 숫자가 되는 경우의 횟수를 구하는 문제이다.

이 문제의 힌트는 고유한 번호가 주어지는 것이다.

즉, 중복되지 않는 수가 주어진다.

함정은 중복되는 경우를 체크하면 안된다.

예를 들어 필요한 숫자가 3일 때 답은 (1,2) (2,1) 로써 2개가 아닌 (1,2) 1개가 된다.

 

어떻게 접근할까?

일단 순수한 방법으로 구현을 해보겠다.

for (int i=0; i<n; i++) { for (j=i+1; j<n; j++) { if (array[i]+array[j] == m) { cnt++; } } }

n = 5일때,

i = 0, j = 1,2,3,4,

i = 1,  j = 2,3,4

i = 2, j = 3,4

i = 3, j = 4

i = 4, j = x

위와 같이 이중 반복문이 돌게 된다.

이렇게 구현을 한다면, j는 항상 i보다 크기 때문에 중복되는 경우를 제외할 수 있다.

가장 순수한 방법이라고 생각한다.

하지만 순수한만큼 불필요한 루프를 가진다.

결국 시간복잡도 O(n^2)보다는 낫겠지만 다를 게 없다.

 

그럼 어떻게 효율적이게 구현할 수 있을지 한번 보자.

본인은 이렇게 생각했다.

어차피 문제의 입력되는 수들은 고유한  번호만 주어지기 때문에 괜한 경우의 수를 생각할 필요가 없다.

하나의 수를 만들기 위한 두 수를 생각해보자.

예를 들면 8을 만들어보자.

(1,7) || (2,6) || (3,5) || (4,4) 4가지 경우가 있다.

하지만 문제는 고유한 번호 2개를 합쳐 나와야하기 때문에 (4,4) 의 경우는 제외시킨다.

그렇다면 (1,7) || (2,6) || (3,5) 경우이다.

공통점이 보이는가? 간단하다. 하나는 작고 하나는 크다.

펼쳐보자.

1,2,3,4,5,6,7

1,2,3,4,5,6,7

1,2,3,4,5,6,7

보시다시피 위와 같이 양쪽 끝을 기준으로 시작으로 좁혀가면서 8을 만들 수 있다.

이것을 구현하면 아래와 같다.

for(int i=0;i<n;i++) {

    array[sc.nextInt()]++;

}

 

int start=1,end=m-1,count=0;

 

while(start < end) {

    if (array[start] != 0 && array[end] != 0) {

        if (start + end == m) {

            count++;

        }

    }

    start++;

    end--;

}

입력 값을 인덱스로 활용했다.

그리고 위에서 설명한대로 양 사이드를 기준으로 잡아 좁혀나갔다.

while문을 통해 왼쪽(start)은 증가시키면서 오른쪽(end)은 감소시키면서 판별하였다.

 

이렇게 접근함으로써, 입력갯수의 절반만큼만 루프를 돌면 된다.

그러므로 첫번째 순수한 방법과는 비교하는 횟수가 데이터가 클수록 엄청나게 차이가 난다.

 

더 좋은 방법은 너무나 많다.

이렇게도 접근할 수 있다는 것을 알아두길.

필요하다면.. GitHub에 올려두었다. 참고하길 바라겠다.

 

Github 

https://github.com/hotehrud/acmicpc/blob/master/math/1940.java