백준 2358 자바 - 평행선 (BOJ 2358 JAVA)

문제 : boj2358

 

  이번년도에 푼 것중 가장 쓰레기 문제였다. 사실 블로그를 작년 말에 개설 후 '쓰레기'란 단어 자체를 처음 사용하고 있다. 혹시 풀 문제를 찾고 계시는 분이라면 이 문제는 미리 패스하시고, 맞왜틀 때문에 찾아오신 분이라면 잘 찾아오셨다. 다음의 2가지를 확인해보면 풀 수 있을 것이다.

 

1. '서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개'

-> 이렇게 해두면 당연히 combination으로 생각될 것이다. 즉 입력이

1 0

2 0

3 0

이라면 1 0 - 2 0 / 2 0 - 3 0 / 1 0 - 3 0 이렇게 해서 3개라 생각(3C2)하고 풀고있었을 것이다. 하지만 어이없게도 이 문제에서는 이게 아니다. 이 문제는 설명을 무시하고 저걸 하나로 쳐야한다. 즉, 동일 x축이나 동일 y축에 점이 2개 이상 있다면 직선이 1개 있는것이다. 왜 저렇게 설명해놨는지 모르겠다 ㅋㅋ

 

2. '만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.'

-> 이 부분도 상당히 뇌절이라 생각되지만 뭐 문제야 출제자 마음이니 그럴 수 있긴하다. 아무튼 이 글을 찾아왔다면 대부분 '1'의 문제였겠지만, '2'도 헷갈릴 수 있다.

왜냐하면

1 1

1 1

이렇게 입력이 들어오면 답은 2개 이기 때문이다 ㅋㅋㅋ

 

그럼 아래와 같은 입력은 답이 뭘까?

1 1
1 1
1 0
1 0

 

이 경우엔 답이 3이다.

 

그럼

1 1

1 1

1 1

1 1

이건 어떨까? '1'과 합쳐져서 2가 답이다 ㅋㅋ

 

---

 

  애초에 푸는 방법때문에 찾아온건 아닐꺼라 생각된다. 검색해서 왔다면 맞왜틀때문에 오셨겠지.. 아무튼 해설은 적어야하니 대강 적자면, 내 경우엔 좌표압축을 통해 최대 2^31의 수를 최대 10만의 수로 압축시켰다. x축 좌표를 10만으로 압축하고, y축 좌표도 10만으로 압축해서 카운팅 후 해당 좌표에 2개 이상이 카운팅 되었다면 선이 있는게 된다.

  

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedHashMap;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int[] rArr = new int[100000];
        int[] cArr = new int[100000];
        HashMap<Integer, Integer> rComp = new LinkedHashMap<>();
        HashMap<Integer, Integer> cComp = new LinkedHashMap<>();
        int rCnt = 0, cCnt = 0;

        while (n-->0) {
            int r = nextInt();
            int c = nextInt();
            if (!rComp.containsKey(r)) rComp.put(r, rCnt++);
            if (!cComp.containsKey(c)) cComp.put(c, cCnt++);
            rArr[rComp.get(r)]++;
            cArr[cComp.get(c)]++;
        }

        long answer = 0;
        for (int i = 0; i < rCnt; i++) answer += rArr[i]>=2?1:0;
        for (int i = 0; i < cCnt; i++) answer += cArr[i]>=2?1:0;
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}