베카의에러뿌시기

LeetCode 문제 중 난이도 Easy인 Hamming Distance이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석
두 정수 사이의 해밍거리는 상응하는 위치에서 값이 다른 비트의 개수이다.
두 정수 x,y를 입력으로 받아 해밍거리를 구하여라.

* x,y는 0 이상 2^31 이하

비트연산자를 이용하면 서로 다른 비트만 1로 표시할 수 있다. 

0101 ^ 0100 = 0001

100111 ^ 101011 = 001100

입력 받은 x와 y에 XOR 연산을 하면 x와 y에서 비트값이 다른 위치의 비트를 1로 바꾸어다. 그 결과값에서 1의 개수를 리턴하면 된다. 자바에서 제공해주는 Integer.bitCount를 사용하면 1줄만에 해결이 가능하다.

하지만 왠지 이 방법은 너무 치사한(?)것 같으니 비트의 개수를 직접 세어 주자.

어떤 숫자에서 1을 빼면 마지막 1이 있는 위치부터 끝까지 비트가 바뀐다

1001100 - 1 = 1001011

그 상태에서 원래의 숫자와 AND(&)연산을 하면 맨 오른쪽의 1이 사라지게 된다.

1001100 & 1001011 = 1001000

위의 원리를 이용해 코드에 적용해 보자. x^y의 결과값이 0이 될 때까지 오른쪽에서부터 1을 차례로 없애주고 count를 1씩 늘린다. 마지막에는 count 값을 리턴한다.

연산 횟수의 최댓값은 Integer의 비트수로 상수로 정해져 있으니 시간복잡도는 O(1)이고 공간복잡도도 O(1)이다.

LeetCode 문제 중 난이도 Easy인 Power of Four이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

부호를 갖는 32비트의 주어진 정수를 가지고 그것이 4의 거듭제곱인지 판별하는 함수를 작성하라.

4의 거듭제곱을 2진수로 나타내보자. 100, 10000, 1000000,······ 첫 비트 1 오른쪽에 짝수개의 0을 가지고 있을 것이다. 4로 나누었을 때 깔끔하게 나누어 떨어지게 되므로 input/4의 값이나 input>>2의 값이 정확히 같을 것이다. 쉬프트연산자에 대해 잘 모른다면 아래 포스팅을 참고하자.

2019/03/18 - [프로그래밍문제풀기] - 쉬프트연산자

input값이 0보다 작은 경우엔 연산을 할 필요도 없다. 0보다 작거나 1일 경우에 예외처리 해 주고 아래의 코드에서는 0보다 작은 경우는 이미 처리했으니 >>산술쉬프트연산자를 쓰든 >>>논리쉬프트연산자를 쓰든 상관이 없다. 만약 함수의 앞부분에서 음수에 대한 예외처리를 해주지 않아도 결과 값에는 문제가 없겠지만 그럴 경우에 >>산술쉬프트연산자를 쓰면 굳이 할 필요 없는 -16/4 = -16>>2따위의 연산을 하게되므로 그 때는 >>>논리쉬프트연산자를 쓰는게 나겠다. (어쨌든 쉬프트연산자는 속도가 매우 빠르기 때문에 성능에는 전혀 상관이 없다!)

Worst Case(01000000 00000000 00000000 00000000)에도 쉬프트연산은 최대 15번으로 정해져 있으므로 시간복잡도는 O(1)이다. 또한 추가적인 메모리를 사용하지 않으므로 공간복잡도도 O(1)이다.

문제 출처 - https://leetcode.com/problems/power-of-four

LeetCode 문제 중 난이도 Easy인 Remove Duplicates from Sorted Array이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

정렬된 배열인 nums를 입력으로 받아 모든 요소들이 한번씩만 나타나도록 배열을 수정하고 길이를 리턴하여라. 새로운 저장공간을 사용하지 말고 input 배열을 수정하는 것으로 O(1)의 추가 메모리 내에서 해결해라.

이번 문제는 꽤 쉽다! 배열을 탐색하면서 중복값인지 아닌지 체크하고 중복값이 아닌 경우에만 앞에서부터 하나씩 저장해준다. 지금 탐색하고 있는 배열의 인덱스와 저장해야될 곳의 인덱스가 다르므로 저장해야 할 위치는 result라는 변수를 선언해서 기록한다.

배열을 처음부터 끝까지 탐색해야 하므로 시간복잡도는 O(n)이고 저장할 때 필요한 변수 하나만 선언하면 되므로 공간복잡도는 O(1)이다.

문제 출처 - https://leetcode.com/problems/remove-duplicates-from-sorted-array

LeetCode 문제 중 난이도 Easy인 Single Number이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

비어있지 않은 정수 배열에서, 하나를 뺀 모든 요소들은 두개씩 들어있다. 하나뿐인 요소를 찾아라.

알고리즘은 선형시간의 복잡도(O(n))를 가져야 한다. 추가적인 메모를 사용하지 않고 가능한가?

가장 먼저 떠오른 알고리즘은 먼저 배열을 정렬 한 뒤, 배열을 처음부터 탐색해 앞이나 뒤 요소와 둘다 같지 않은 요소를 찾는 것이다.예를 들어 [1,1,2,3,3]의 경우 2가 유일한 요소로 앞의 1과도 다르고 뒤의 3과도 다르다. 코드는 다음과 같다.

이 경우에는 추가적인 메모리 사용은 없지만 Java의 Array.sort 정렬을 하는데 최대 O(nlogn) 시간이 들므로 문제의 요구사항인 선형시간 O(n)을 초과한다. 

두번째 방법은 비트연산자를 이용하는 것이다. 비트연산자를 잘 모를 경우 아래 포스팅을 참고하자.

2019/03/16 - [프로그래밍문제풀기] - 비트연산자란?

비트연산자중 ^(XOR)을 사용할 것이다. XOR연산자는 양쪽 비트가 서로 다른 경우에 1을, 같은 경우에는 0을 반환한다.

A ^ 0 = A

A ^ A = 0

A ^ B ^ A = A ^ A ^ B = 0 ^ B = B

따라서 배열의 모든 요소로 XOR 연산을 하면 두 개씩 있는 요소들은 서로 상쇄되어 사라지고 딱 하나만 있는 요소를 찾을 수 있다.

위의 코드에서 singleone이라는 정수형을 하나 추가로 사용했지만 이 경우 nums배열이 아무리 커져도 영향을 주지 않기 때문에 공간복잡도는 O(1)이고 추가적인 메모리는 사용하지 않는다고 봐도 된다.

문제 출처 - https://leetcode.com/problems/single-number

LeetCode 문제 중 난이도 Easy인 Search Insert Position이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

시간복잡도는 O(n), 공간복잡도는 O(1)로 나쁘지 않아 보이지만 이진탐색을 이용하여 속도를 좀 더 빠르게 개선 해보자.

이진탐색이라고 하니 왠지 엄청 복잡하고 어려울 것 같지만 우리는 이미 실생활에서 이진탐색을 쓰고 있다. 술자리에서 소주병 뚜껑에 있는 숫자를 맞추는 업앤다운 술게임을 생각해보자. 술래는 뚜껑에 써있는 숫자(1부터 50사이)를 사람들이 부르는 값과 비교해서 업인지 다운인지 알려준다. 한 명씩 돌아가면서 숫자를 부르고 한 바퀴 안에 숫자를 맞추면 술래가 술을 마신다. 이 때 숫자를 빨리 맞추고 싶다면 당연히 1부터 하나씩 비교하지 않는다. 맨 처음에 25를 부르면 업이냐 다운이냐에 따라 앞의 24개(1~24) 또는 뒤의 25개(26~50) 숫자들을 바로 제외할 수 있다. 이런식으로 남은 숫자들 중 중앙값을 부르고 반씩 버리면서 후보를 줄여 나간다.

이진탐색이 바로 그런 원리이다. 정렬되어 있는 배열에서 목표값을 찾기 위해 중앙의 값과 목표값을 비교한다. 코드로는 다음과 같다.

맨 처음에는 배열의 첫 인덱스인 0이 first이고 마지막 인덱스인 배열의길이-1이 last일 것이다. 중앙값(mid)을 구해 타겟값이 중간값과 일치하는지, 작거나 큰지 따져서 나머지 반을 버리고 또 중앙값을 찾는다. 이렇게 하면 시간복잡도를 O(log₂n)까지 줄일 수 있다. 마지막에 first가 last보다 크면 first를 리턴하는 부분은 배열에 목표값이 존재하지 않을 경우에 해당한다. 이 부분은 말로 설명하기보다는 직접 숫자를 넣어서 따져보는 것이 이해가 더 쉽다. 맨 위의 Example 2의 경우에 first, last, mid가 어떻게 바뀌는지 따져 보길 바란다.

참고로 int는 소수점이 있는 숫자는 소수점을 버림한다. 예를 들어 (2+5)/2는 3이 나온다.

문제 출처 - https://leetcode.com/problems/search-insert-position

LeetCode 문제 중 난이도 Easy인 Length of Last Word이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

알파벳 대/소문자 그리고 공백문자로 이루어진 String s에서 마지막 단어의 길이를 구하여라.

마지막단어가 존재하지 않으면 0을 리턴한다. 단어의 정의는 공백없이 이루어진 문자열을 말한다.

Example : "Hello World"가 Input이라면 World의 글자수인 5 출력

간단한 경우부터 생각해보자.

문자열을 뒤에서부터 읽다가 s.charAt(i)에서 공백문자를 발견하면 전체 문자열의 길이에서 i+1을 빼서 공백 뒤의 문자의 개수를 구한다. 만약에 공백이 아예 존재하지 않아 for문이 끝날때까지 리턴이 발생하지 않는다면 하나의 단어로 이루어진 문자열이므로 그냥 문자열의 길이를 반환하면 된다.

* charAt(int index)는 문자열에서 해당 인덱스의 문자를 반환한다. 인덱스는 0부터 시작한다.

만약 문자열의 마지막 문자가 공백문자라면 어떨까? 위의 코드대로라면 "I am a Genius   "의 반환값은 0이 된다. 우리가 얻어야 할 값은 6이다. 이 문제를 해결하기 위해 공백문자를 만났을 경우 그 뒤에 알파벳이 있었는지 확인하고 나서 리턴을 하도록 코드를 바꿔 보자.

"I am a Genius   "라는 문자열을 알파벳을 만나기 전까지 거꾸로 읽다가 s를 만나면 hasChar를 true로 바꾼 뒤 알파벳의 개수가 늘어날 때마다 count를 늘려 준다. 그러다가 또 다시 공백문자를 만나면 그 때 count 값을 반환한다.

for문 내에서 리턴이 발생하는 경우는 hasChar가 true인 상태에서 공백문자를 만났을 때이다. 문자열의 맨 앞까지 전부 읽었는데도 리턴이 발생하지 앖는 경우는 두가지이다. 문자열 전체가 공백문자로 이루어졌거나, 문자열 전체가 한 단어 여서 공백문자가 없을 때이다. 그럴 때는 count를 리턴하면 된다. 전자라면 count가 처음에 선언한 그대로 0일 것이고 후자라면 count가 문자열의 길이와 같게 된다.

Worst Case는 문자열 전체가 공백이거나, 공백이 없는 문자열일 경우 전체 문자열을 읽어야 하므로 시간복잡도는 O(n)이고 추가적인 공간을 사용하지 않으므로 공간복잡도는 O(1)이다.

2019/02/25 - [프로그래밍문제풀기] - 빅오표기법(Big O notation)

다른 해결법도 있다. 문자열을 split()함수를 이용하여 공백문자를 기준으로 잘라 배열에 넣고 배열의 마지막 요소의 길이를 구하면 된다. 전체가 하나의 문자열이거나 전부 공백문자로 이루어진 경우에 대한 예외처리를 해 준다.

두번째 방법은 코드 단 4줄로 구현이 가능하다! 대신 새로운 배열을 위한 추가적인 메모리를 필요로 하므로 공간복잡도가 O(n)으로 늘어나게 된다.

문제 출처 링크 - https://leetcode.com/problems/length-of-last-word

LeetCode 문제 중 난이도 Easy인 Plus One이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

비어있지 않은 배열의 숫자들이 음수가 아닌 정수를 나타낸다고 하자. 그 정수에 1을 더하여라.

이 문제를 어떻게 해결할까? 먼저 Example 1과 2의 예시처럼 가장 간단한 경우의 수를 생각해보자.

배열의 맨 마지막 숫자에 +1을 해 주면 간단하게 해결 될 것이다.

** 배열(뿐만 아니라 어떤 자료형을 사용하든지간에)값이 null인지 확인하는 예외처리는 가장 기본이지만 이 문제에서는 배열이 비어있지 않다고 했으므로 파라미터로 넘어오는 digits 배열이 null이거나 배열의 length가 0인 경우에 대한 예외처리는 생략한다.

배열의 마지막 숫자가 9일 땐 어떨까? 위의 코드대로라면 Input값이 [5,3,9]일 경우 Output으로 [5,4,0]대신[5,3,10]이 나온다. 각 배열의 요소는 한 자리의 숫자로 이루어져야 하므로 위의 코드에서 배열의 값이 10 이상일 경우 자리수를 하나씩 올려주는 carry()함수를 추가하고 for문을 이용해 배열을 뒤에서부터 탐색하여 자리수를 올려준다.

carry(index,digits)는 인덱스와 배열 자체를 파라미터로 받아 배열의 해당 인덱스 값이 10 이상일 경우 그 값을 0으로 만들고 배열의 인덱스-1 값에 +1을 해준다. 이 때 digits[0]이 10인 경우에는 digits[-1]가 존재하지 않으므로 digits[1]인 경우 까지만 체크하고 일단 넘어간다.

자리수를 올려주는 부분은 초등학교 때 배운 받아올림이 있는 덧셈을 생각하면 된다.

이제 거의 다 왔다! 위에서는 배열의 요소가 전부 9인 경우는 고려하지 않았다. 만일 배열의 모든 요소가 9인 경우, for문을 돌고 난 뒤 배열의 상태는 [10,0,······] 일 것이다. digits[0]에서는 더 이상 앞으로 올림해 줄 수가 없으므로 이 경우에는 배열의 크기를 1 늘리고 [1,0,0,······]으로 채워주어야 한다. 

자 이제 완성된 코드를 돌려 보자!

Worst case는 배열의 모든 요소가 9일 경우 이므로 이 때 시간복잡도는 O(n), 공간복잡도도 O(n)이다.

2019/02/25 - [프로그래밍문제풀기] - 빅오표기법(Big O notation)

문제 출처 링크 - https://leetcode.com/problems/plus-one

오늘 소개할 사이트는 LeetCode.com 이다. 국내에도 코딩테스트 연습 사이트는 많지만 영어로 된 LeetCode를 추천한다.

한국에서만 일할 예정이라면 굳이 영어를 하지 않아도 괜찮다 생각 할 수도 있다. 하지만 영어로 구글링을 할 줄 알면 접할 수 있는 정보량에 차이가 있다. 이제 막 개발을 시작해서 초보적인 수준의 공부를 할 때에는 큰 차이가 없을 수도 있지만 언젠가 한국어 자료들만으로는 해결이 어려운 문제들을 접하게 될 것이다. 평소에 영어로 된 프로그래밍 컨텐츠들을 자주 접하고 영문 자료를 읽는데 익숙해 질 수 있도록 하자.

LeetCode를 이용하려면 회원가입을 해야 한다. 무료로 이용할 수 있으니 Create Account를 눌러 가입한다.

Mock 카테고리에 들어가면 모의인터뷰를 할 수 있다. 코딩테스트 뿐만 아니라 인성면접에 대한내용들도 있다. 이건 프리미엄(유료) 멤버에게만 공개되는데 아직 여기까지 할 필요는 없으니 넘어간다.

우리가 볼 것은 Problem카테고리이다. 문제의 난이도는 Easy/Medium/High로 나뉘어져 있으니 원하는 수준에 맞게 문제를 풀면 된다.

문제를 선택하고 원하는 언어를 고르면 자동으로 클래스명,파라미터,리턴값 등을 정해준다.

코드를 다 작성하고 난 후에는 오른쪽 하단의 ▶Run Code를 눌러 돌려볼 수 있다. 입력값을 바꿔 가면서 테스트 해 보고 완료되면 Submit버튼을 눌러 제출한다.

Submit을 하고 나면 내 코드에 대한 평가가 나온다. 같은 코드도 돌릴 때마다 차이가 약간 있다. 여러번 돌려서 시간의 평균 값을 내는게 아니라 한번 돌린 결과로 나오는 듯 하니 크게 신경쓰지는 않아도 된다. 어쨌든 시간이 적게 걸릴수록, 메모리를 적게 쓸수록 좋은 코드다.

Solution탭에서 해결법을 볼 수 있다. 내 코드의 속도가 너무 느리거나 메모리를 많이 썼다면 다른 효율적인 방법이 있는지 읽어본다.

Contest탭에서는 매주 전세계 개발자들이 참여하는 코딩콘테스트가 열리니 참여가능하다.