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..

문제 살펴보기 int 자료형 배열이 주어진다. 배열의 인덱스는 일차에 해당하고, 각 숫자는 해당 일차의 주식 매매가를 의미한다. 예를 들어 [3, 5, 9]와 같은 배열이 주어진 경우 다음과 같은 의미를 가진다. 인덱스 0, 숫자 3 -> 0일차, 주식 가격 3 인덱스 1, 숫자 5 -> 1일차, 주식 가격 5 인덱스 2, 숫자 9 -> 2일차, 주식 가격 9 주어진 배열을 바탕으로, 주식을 구매하고 다시 팔아서 수익을 남기려고 한다. 최대 얼마의 수익을 낼 수 있을까? 생각의 흐름 1. 구매하는 일자(인덱스)는 판매하는 일자(인덱스)보다 빨라야 한다. 2. 이중 반복문을 사용할 경우 계산 시간이 너무 길어져 시간 초과가 된다. 이 문제의 핵심! 2번 이유로 인해 이중 반복문을 사용할 수 없다. 최저값과..

문제 살펴보기 주어진 문자열에서 숫자를 찾아 모두 더하되, 숫자가 아닌 "Z"를 만나면 이전에 더했던 값을 지워야 한다. 생각의 흐름 우선 주어진 문자열을 split() 메서드를 이용해 배열 형태로 바꾼다. 반복문을 이용해서 현재 문자열이 "Z"가 아니면 현재 인덱스에 해당하는 값을 누적하고, "Z"면 이전 인덱스에 해당하는 값을 뺐다. 처음 풀 때는 stack을 떠올리지 못해서, stack을 사용해서 다시 풀었다. stack을 사용할 경우, 현재 문자열이 "Z"이면 .pop() 메서드를 이용해 마지막에 쌓은 값을 제거해주면 된다. 풀어보기 Stack을 사용하지 않은 경우 String[] arr = s.split(" "); int answer = 0; for(int i=0; i

문제 살펴보기 주어진 int 자료형 배열을 이용해 이진 탐색 트리(Binary Search Tree)를 만드는 문제이다. * 이진 탐색 트리 : 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가진 트리 구조를 의미한다. 생각해보기 만약 주어진 배열이 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이라면? 위와 같은 모습의 이진 트리가 만들어져야 한다. (*점선은 빈 노드를 의미합니다) 그러기 위해서는 우선, 배열에서 부모 노드에 저장할 값을 꺼낸다. 그러고 나서 해당 값을 기준으로 2개의 묶음으로 나눈다. [0, 1, 2, 3, 4] 5 [6, 7, 8, 9, 10] 트리의 다음 단계로 넘어간다. 각 묶음에서 다시 부모 노드에 저장할 값을 꺼내고,..

트리 구조에서 모든 노드를 한 번씩 방문하여 처리하는 것을 트리 순회(Tree Traversal)라고 한다. 1. 전위 순회 (Preorder Traversal) 1) 부모 노드를 방문한다. 2) 왼쪽 하위 트리를 순회한다. 3) 부모 노드의 오른쪽 하위 트리를 순회한다. 예시) 1 > 2 > 4 > 5 > 3 > 6 > 7 2. 중위 순회 (Inorder Traversal) 1) 왼쪽 하위 트리를 순회한다. 2) 부모 노드를 방문한다. 3) 오른쪽 하위 트리를 순회한다. 예시) 4 > 2 > 5 > 1 > 6 > 3 > 7 3. 후위 순회 (Postorder Traversal) 1) 왼쪽 하위 트리를 순회한다. 2) 부모 노드의 우측 하위 트리를 순회한다. 3) 부모 노드를 방문한다. 예시) 4 > 5..

문제 살펴보기 주어진 구슬 중 n개를 꺼낸다고 할 때, 가능한 경우의 수를 세서 반환하는 문제이다. 생각하기 관련 공식이 주어져 있어서, 공식만 적용하면 해결될거라고 생각했지만... 큰 함정이 숨어있었다. 바로 자료형의 범위이다. 이 문제에서는 팩토리얼을 다룬다. 그러다 보니 숫자의 값이 순식간에 커져서, 숫자를 있는 그대로 다룰 경우 int 자료형은 물론이고, double 자료형으로도 감당이 되지 않는다. (13! 에서 이미 int 자료형의 범위를 크게 뛰어넘고, 21! 까지 가면 long 자료형의 최대값의 5배보다도 큰 값을 가진다..) 아주 기본적이면서 중요한 개념인데, 몇 번 실행하고 오류화면을 본 후에야 떠올렸다.... 문제를 푸는 방식은 크게 두 가지로 나눌 수 있을 것 같다. 1. BigIn..

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

문제 살펴보기 이번 문제는 주어진 문자열에서 가장 마지막에 위치한 단어의 길이를 계산하는 문제이다. 예를 들어 주어진 문자열이 "Hello World"이면, 마지막에 사용한 단어가 World이므로 그 길이인 5를 반환하면 된다. 생각의 흐름 처음에는 문자열을 뒤에서부터 검사해 공백을 찾은 후, 공백 다음 문자부터 문자열이 끝날때까지의 길이를 세면 된다고 생각했으나 예시로 주어진 문자열 중 끝부분에 공백이 있는 문자열이 있었다. 예를 들면 " Hello World " 같은 문자열이다. 문자열의 끝 부분에 공백이 있으므로, 앞서 생각했던 방법을 적용하면 단어를 찾을 수 없다... 그래서 문자열에서 마지막으로 사용된 단어의 시작 인덱스와 끝 인덱스를 찾은 후, 길이를 계산하기로 했다. 풀어보기 // 단어의 길..

문제 들여다보기 괄호로 이루어진 문자열이 주어지며, 문자열 내에서 괄호가 정상적으로 사용되었는지 판단해 true 또는 false를 반환하는 문제이다. 괄호가 정상적으로 사용되었는지를 판단하는 규칙은 다음과 같다! 1. 모든 괄호는 먼저 열린 후에 닫혀야 한다. 2. 괄호를 열고 닫을 때 그 짝이 같아야 한다. 3. 서로 다른 종류의 괄호가 교차되어선 안된다! 예를 들어, 문자열이 " ] ( ) { } "인 경우 1번 규칙에 어긋난다. 만약 주어진 문자열이 " ( } " 인 경우, 2번 규칙에 어긋나며, 주어진 문자열이 " [ { ] } ( ) "인 경우, 3번 규칙에 어긋난다. 규칙에 어긋나면 결과로 false를 반환해야 한다. 생각의 흐름 처음에는 숫자, 문자를 단순 비교할 때처럼 이중반복문으로 풀려고..

부트스트랩이란? 부트스트랩은 css나 javascript로 작성된 디자인, 기능을 모아 둔 프론트엔드 프레임워크이다. 웹페이지를 디자인하려면 색깔, 요소 배치, 사각형의 곡률, 드롭다운 메뉴 등 신경써야 할 것이 많은데 부트스트랩을 사용하면 이러한 작업을 쉽게 할 수 있다. 부트스트랩을 사용하려면 부트스트랩 코드가 작성된 파일을 직접 다운받거나 cdm, npm방식 등으로 추가해서 사용하면 된다. 내 경우 파일을 직접 다운받아 사용하였으며, 사용한 파일은 각각 bootstrap.min.js와 bootstrap.min.css이다. 부트스트랩을 잠깐 사용해보면서, 부트스트랩 사용법은 공식 홈페이지에 아주 잘 정리되어 있어서 따로 정리할 필요가 없다고 느꼈지만 부트스트랩이 사용하고 있는 그리드 시스템은 알아두면..