beepbeep

문제 살펴보기 숫자가 들어있는 배열이 주어진다. 이 배열에 있는 모든 숫자는 2개씩 들어있으며, 딱 한 숫자만 1개 들어있다. 1개만 있는 숫자를 찾아서 반환해야 한다. 단, 숫자를 찾는 코드의 시간 복잡도는 0(n) (= linear runtime complexity) 이어야 하고, 공간 복잡도는 0(1) (=constant extra space) 이어야 한다. 생각의 흐름 단일 반복문과 비트 연산을 활용하면 주어진 요구사항을 지킬 수 있다... 비트 연산자 중 XOR을 사용하면 되고, XOR의 규칙을 이용하면 된다. x ^ 0 = x x ^ y = 0 또한 XOR은 교환법칙이 성립한다. 따라서 다음과 같이 풀 수 있다. x ^ y ^ x = x ^ x ^ y = y 풀어보기 int num = 0; f..

문제 살펴보기 이진수 형태의 문자열이 2개 주어진다. 두 이진수 문자열을 이진수 계산법을 합산한 후, 그 결과를 반환하는 문제이다. 생각의 흐름 처음에는 주어진 두 문자열을 십진수로 바꿔서 더하고, 그 값을 다시 이진수로 만들어 반환하려고 했다. 하지만 이 방법은 주어진 문자열이 아주아주아주 길면 사용할 수 없다. 문자열, 즉 String 객체는 JVM의 heap 메모리가 허용하는 만큼 길어질 수 있지만 int 자료형은 -2^32 ~ (2^32)-1 까지, long 자료형은 -2^64 ~ (2^64)-1 까지만 가능하다. 그래서 아주 긴 문자열이 주어지면 오버플로우가 발생한다.. 문제에서도 위 방법을 사용해 제출하면 중간에 걸리게 된다(testcase 중에 아주 긴 문자열이 주어지는 케이스가 있다). 그..