베카의에러뿌시기

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

  문제해석

주어진 first와 second를 이용해 "first second third" 형태의 텍스트로 first바로 다음에 second가 오고 바로 뒤에 third가 오는 경우를 고려하여라.

각각의 경우에 third를 answer에 추가하고 answer를 리턴하라.

1 처음엔 text 내에 third가 몇개인지 알 수 없으므로 크기가 고정된 배열 대신 리스트를 이용하자.

2 text에 있는 단어들을 문자열 배열 words에 넣어준다.

3 words[i]가 first이고 words[i+1]이면 words[i+2]를 answer에 추가한다.

4 마지막으로 answer를 배열로 변환하여 리턴한다.

코드로 나타내면 다음과 같다.

위 코드의 시간복잡도는 O(n), 공간복잡도는 O(n)이다.

문제출처 - https://leetcode.com/problems/occurrences-after-bigram/

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

  문제해석

2진 행렬 A를 입력으로 받아 수평으로 뒤집은 다음 숫자를 반대로 바꾸고 결과를 반환하라. 

수평으로 뒤집는것은 각 줄의 이미지가 뒤집히는 것이다. 예를들어 [1,1,0]을 수평으로 뒤집으면 [0,1,1]이 된다.

반대로 바꾸는것은 0은 1로, 1은 0으로 변환하는것이다. 예를들어 [0,1,1]은 [1,0,0]이 된다.

설명이 복잡해 보일때에는 Example을 보자. 우리가 해야 할 일은 입력 배열을 좌우로 뒤집은 뒤 0은 1로, 1은 0으로 바꿔서 반환해주기만 하면 된다.

위의 예시의 첫번째 행을 보자. A[0][2]을 temp에 넣고 A[0][2]에는 A[0][0]의 값과 1의 XOR 연산값(0을 1로, 1을 0으로)을 넣어주자. 위의 예시에서는 가운데 열인 A[0][1]은 temp에 넣을 필요 없이 A[0][1]^1만 해주면 되지만 열이 짝수인 경우에는 temp에 넣고 값을 서로 바꾸어주어야 한다. 반복문으로 전체 행에 연산해준다. XOR연산을 잘 모른다면 아래 비트연산자 포스팅을 참고한다.

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

이 방법의 시간복잡도는 O(n)이고 공간복잡도는 O(1)이다.

문제 출처 - https://leetcode.com/problems/flipping-an-image/

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

  문제해석

레몬에이드 가판대에서 각 레몬에이드의 가격은 $5이다.

레몬에이드를 사기 위해 줄에 선 손님들은 순서대로 한명씩 주문한다. 각각의 손님들은 $5, $10, $20 셋 중에 하나의 지폐를 내고 레몬에이드를 하나씩 주문한다. 정확하게 거스름돈을 돌려주어서 순수한 거래는 손님이 $5씩 지불한게 되어야 한다.

처음에 잔돈 없이 시작해서 모든 손님들에게 정확한 거스름돈을 돌려줄 수 있는 경우에만 true를 리턴하라.

가지고 있는 지폐 수를 체크하기 위해서 5달러 지폐의 수는 five, 10달러 지폐의 수는 ten이라는 변수에 넣는다. 20달러는 거스름돈으로 나갈 일이 없으므로 체크할 필요 없다. 5달러 지폐를 받으면 five+1, 10달러지폐를 받으면 ten+1을 해준다.

20달러 지폐를 받은 경우에는 두가지로 나눌 수 있다. 거스름돈을 10+5 합쳐서 줄 수도 있고 만약에 10달러가 없으면 5+5+5로 줄 수도 있다. 가지고 있는 5달러와 10달러 지폐가 음수가 되는 때가 있다면 거스름돈을 정확하게 돌려줄 수 없는 것이다.

한가지 유의할 점은 if(five<0 || ten<0) return false는 for문 안에 있어야 한다. 그렇지 않으면 지폐수가 음수였다가 다음 손님들에게 지폐를 받는, 실제로 존재할 수 없는 경우에도 true를 리턴한다.

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

  문제해석

학생의 출석기록을 의미하는 String을 입력으로 받는다. 출석기록은 3가지 문자로만 이루어져 있다

A : 결석

L : 지각

P : 출석

결석이 한번을 넘거나 연속으로 두번 넘게 지각하는 경우가 없어야만 상을 받는다. 해당 학생이 상을 받을 수 있는지 없는지 리턴하라.

이 문제는 정규식을 이용해 1줄의 코드로 풀 수 있다. 정규식에 대해 잘 모른다면 아래 포스팅을 참고하자. {n}은 n번 반복이라는 뜻이다.

2019/03/30 - [프로그래밍문제풀기] - JAVA 정규표현식 (Regular expression)

두번째 방법은 배열을 탐색하면서 A가 1번을 넘는지, L이 2번 넘게 연속인지 확인하는 것이다.

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

  문제해석

정수 배열을 입력값으로 받아 해당 배열이 중복값을 포함하고 있는지 판별하라.

아무 값이나 배열 내에서 두번 이상 나타나는 값이 있다면 true를 리턴하고 모든 요소가 유일하다면 false를 리턴해라.

첫번째 방법은 배열을 정렬한 후 앞뒤 값을 비교하는 것이다. 이전에 포스팅한 Single Number 문제의 첫번째 풀이법과 원리가 같다.

2019/03/16 - [프로그래밍문제풀기] - [코딩연습] Single Number 하나뿐인 숫자 찾기

정렬하는데 드는 시간 O(nlogn), 탐색하는데 드는 시간 O(n)으로 시간복잡도는 O(nlogn)이고 추가적인 메모리 사용이 없으므로 공간복잡도는 O(1)이다.

두번째 방법은 Set 자료구조를 이용하는 것이다. Set은 중복된 데이터를 허용하지 않는 집합이다. 만약 nums에 중복된 값이 있다면 nums의 길이와 numset의 사이즈가 다를 것이다.

ex) nums = [3,7,7,8,6] 일 경우 nums.length=5, numSet.size()=4

이 방법은 배열을 한번만 탐색하므로 시간복잡도는 O(n)이지만 numSet이라는 추가적인 공간을 사용하므로 공간복잡도는 O(n)이다.

문제 출처 - https://leetcode.com/problems/contains-duplicate/

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

  문제해석

주어진 이진 트리를 가지고 해당 트리가 거울에 비친 자신과 같은지(가운데를 중심으로 대칭인지) 판별하라.

트리는 모든 노드들이 연결되어있고 순환이 존재하지 않는 그래프이다.

나무(tree)를 거꾸로 그린 모양의 계층구조를 생각해보자. 트리(tree) 자료구조는 뿌리(root node)에서 시작해 가지가 뻗어 나가며 맨 끝에는 잎(leaf node)이 달려 있다. 우리가 잘 아는 트리구조가 있는데 바로 회사의 조직도와 컴퓨터 디렉토리이다.

아래 그림은 이진 트리(binary tree)의 예이다. 예시를 보며 몇가지 기본적인 트리 용어를 알아보자.

* 이진트리(binary tree) : 트리 중에서 각 노드의 자식 노드의 수가 2개 이하인 트리

Node(A,B,C...J) : 트리의 구성요소에 해당하는 요소들

Root Node(A) : 최상위 노드

Parent Node : 어떤 노드의 상위 노드

A는 B와 C의 부모노드이고 B와 C도 각각 D&E, F&Gd의 부모노드이다

Child Node : 어떤 노드의 하위 노드

F와 G는 C의 자식노드이고 H와 I는 E의 자식노드이다

Subtree : 어떤 노드의 부모 노드의 집합

D의 조상은 B,A이고 J의 조상은 G,C,A이다

Descendant of a node : 어떤 노드의 자식노드들의 집합

C의 자손은 F,G,J이고 A의 자손은 자기자신을 제외한 전체 노드들이다

Leaf Node(D,H,I,F,J) : 자식노드가 존재하지 않는 노드

Subtree : 어떤 트리의 안에 있는 작은 트리

트리 T의 서브트리 S는 T의 노드 중 하나와 그의 자손들로 이루어진 트리

Depth of a node : 어떤 노드의 루트노드까지의 조상의 수

루트노드의 depth는 0이고 G의 depth는 2이다

Height of a tree : 해당 트리가 가진 노드들의 depth중 최댓값

다시 문제로 돌아가보자. 트리가 좌우 대칭이려면 루트노드를 중심으로 왼쪽 서브트리를 좌우대칭한 것이 오른쪽 서브트리와 같아야 한다. 그러려면 왼쪽 서브트리의 왼쪽 자식노드와 오른쪽 서브트리의 오른쪽 자식노드의 값이 같아야 하고 왼쪽 서브트리의 오른쪽 자식노드와 오른쪽 서브트리의 왼쪽 자식노드의 값이 같아야 한다.

같은방식으로 자손노드들을 리프노드까지 탐색한다. 코드로 나타내면 다음과 같다.

13번째 줄의 (t1 == null || t2 == null)는 위에서 이미 둘다 null인 경우를 체크했으므로 t1이나 t2가 둘중 하나만 null인 경우를 체크한다.

이 방법의 시간복잡도는 O(n)이고 공간복잡도의 worse case는 트리가 일직선으로 이루어져 Height가 O(n)인 경우이므로 O(n)이다.

문제 출처 - https://leetcode.com/problems/symmetric-tree/