[BOJ/JAVA] 백준 7453번 : 합이 0인 네 정수

2022. 1. 21. 15:31

7453번: 합이 0인 네 정수

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

www.acmicpc.net

풀이

N개의 배열 크기를 갖고있는 4개의 배열의 값을 다 더했을 때 0을 만들 수 있는 개수를 찾는 문제입니다.

처음에 시간이 12초로 넉넉하기 때문에 완전탐색을 사용했습니다. 4000*3999*3998*3997의 시간복잡도로 11억 9천..으로 12초 정도 걸릴 것으로 예상하고 풀어봤지만, 시간 초과로 통과되지 않았습니다.

두번째론 HashMap을 사용해서 1/2번째 배열을 모두 더한 값, 3/4번째 배열을 모두 더한 값을 HashMap에 넣은 뒤 두 HashMap을 더했을 때 0이되는 수를 찾아서 해결해봤지만 시간 초과로 통과되지 않았습니다. ~~(O(N^2))라고 생각했는데 왜 안되는지...~~ ==> 찾아보니 해시 충돌 시 O(N)이 되서 시간 초과가 난 것 같습니다.

세번째로 upperbound, lowerbound로 풀었습니다. 값을 찾을 시 가장 오른쪽의 인덱스와 가장 왼쪽의 인덱스를 통해 찾는 값이 몇개인지 이분 탐색을 통해 찾고 인덱스의 차를 통해 개수를 더해주는 방식입니다. 기존 해시 충돌시 O(N)의 시간복잡도가 나오는 hashmap대신 이분탐색으로 O(log n)으로 풀어보려했습니다. 하지만 해당 방식도 시간 초과로 통과되지 않았습니다.

네번째로 투포인터를 사용해서 풀었습니다. AB를 더한 배열은 왼쪽 index부터, CD를 더한 배열은 오른쪽 index부터 안쪽으로 가며 AB[왼쪽index]+CD[오른쪽index]가 0일시 같은 값이 몇개인지 구해주고 곱해서 개수를 더해줍니다. 이때, count를 세는 자료형을 long으로 해주어야합니다. count는 최대 16000000인데, count가 두개이므로 16000000*16000000으로

256000000000000가 되어 int 범위를 초과하기 때문입니다.

성공 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N;
	static long answer;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		answer = 0;
		int[][] array = new int[N][4];
		int[] AB = new int[N * N];
		int[] CD = new int[N * N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 4; j++) {
				array[i][j] = in.nextInt();
			}
		}

		int index = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				AB[index] = array[i][0] + array[j][1];
				CD[index] = array[i][2] + array[j][3];
				index++;
			}
		}

		Arrays.sort(AB);
		Arrays.sort(CD);
		
		twoPoint(AB, CD);
	}

	private static void twoPoint(int[] AB, int[] CD) {
		int left = 0;
		int right = N*N-1;
		
		while(left<N*N && right >-1) {
			int valueOfAB = AB[left];
			int valueOfCD = CD[right];
			int sum = valueOfAB+valueOfCD;
			
			if(sum<0) {
				left++;
			}else if(sum>0){
				right--;
			}else {
				long count1 = 0, count2 = 0;
				while(left<N*N && valueOfAB==AB[left]) {
					left++;
					count1++;
				}
				while(right>-1 &&valueOfCD==CD[right]) {
					right--;
					count2++;
				}
				answer+= count1*count2;
			}
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

실패 코드

dfs

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N, answer;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.nextInt();
		answer = 0;
		array = new int[N][4];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 4; j++) {
				array[i][j] = in.nextInt();
			}
		}
		
		dfs(0, 0);
	}
	
	private static void dfs(int index, int sum) {
		if(index == 4) {
			if(sum == 0) answer++;
			return;
		}
		
		for(int i = 0 ; i < N; i++) {
			dfs(index+1, sum+array[i][index]);
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

HashMap

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N, answer;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.nextInt();
		answer = 0;
		array = new int[N][4];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 4; j++) {
				array[i][j] = in.nextInt();
			}
		}
		
		Map<Integer, Integer> map1 = new HashMap<>();
		Map<Integer, Integer> map2 = new HashMap<>();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0 ; j< N; j++) {
				int value1 = array[i][0]+array[j][1];
				int value2 = array[i][2]+array[j][3];
				
				if(map1.containsKey(value1)) {
					map1.put(value1, map1.get(value1)+1);
				} else {
					map1.put(value1, 1);
				}
				
				if(map2.containsKey(value2)) {
					map2.put(value2, map2.get(value2)+1);
				} else {
					map2.put(value2, 1);
				}
			}
		}
		
		map1.forEach((key, value) ->{
			if(map2.containsKey(key*-1)) {
				answer += value*map2.get(key*-1);
			}
		});
		
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

upperbound / lowerbound

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N, answer;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		answer = 0;
		int[][] array = new int[N][4];
		int[] AB = new int[N * N];
		int[] CD = new int[N * N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 4; j++) {
				array[i][j] = in.nextInt();
			}
		}

		int index = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				AB[index] = array[i][0] + array[j][1];
				CD[index] = array[i][2] + array[j][3];
				index++;
			}
		}

		Arrays.sort(CD);
		
		for (int key : AB) {
			int upper = upperBound(CD, key * -1);
			int lower = lowerBound(CD, key * -1);
			answer += (upper - lower);
		}
	}

	private static int upperBound(int[] array, int find) {
		int left = 0;
		int right = array.length;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (array[mid] <= find) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return left;
	}

	private static int lowerBound(int[] array, int find) {
		int left = 0;
		int right = array.length;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (array[mid] < find) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return left;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 2961번 : 도영이가 만든 맛있는 음식 (0)	2022.02.09
[BOJ/JAVA] 백준 7569번 : 토마토 (0)	2022.02.07
[BOJ/JAVA] 백준 1561번 : 놀이 공원 (0)	2022.01.19
[BOJ/JAVA] 백준 16930번 : 달리기 (0)	2022.01.17
[BOJ/JAVA] 백준 12919번 : A와 B 2 (0)	2021.12.07

선장 일지