코딩 공부 블로그

Given a string s consisting of words and spaces, return the length of the last word in the string. A word is a maximal substring consisting of non-space characters only. 첫 번째 일단 풀었는데, runtime이 2ms라서 다시 풀어야한다. runtime 0ms되기까지! class Solution { public int lengthOfLastWord(String s) { String[] words = s.trim().split("\\s+"); int count = words.length; String res = words[count-1]; return res.length()..

- Time Limit Exceeded 발생 찾아보니 Time Limit Exceeded는 시간복잡도가 높아서 발생한다고 한다. 해당 문제는 O(logn)의 시간복잡도 조건이 있다. class Solution { public int searchInsert(int[] nums, int target) { int fir = 0; int last = nums.length-1; while(fir

class Solution { public int romanToInt(String s) { Map m = new HashMap(); m.put('I', 1); m.put('V', 5); m.put('X', 10); m.put('L', 50); m.put('C', 100); m.put('D', 500); m.put('M', 1000); int res = 0; for(int i=0; i

두개의 트리의 leaf value를 비교하는 것이다. 두 leaf value가 같다면 true를 반환하고, 다르면 false를 반환한다. 처음에는 이해하지 못하고 너비 우선이랑 깊이 우선에서 고민하고 있었다. class Solution { public boolean leafSimilar(TreeNode root1, TreeNode root2) { List rootValue1 = new ArrayList(); List rootValue2 = new ArrayList(); comparsionLeaf(root1, rootValue1); comparsionLeaf(root2, rootValue2); return rootValue1.equals(rootValue2); } private void comparsion..

- DFS(깊이 우선 탐색) 사용 public class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { return 0; } int currentVal = (root.val >= low && root.val high){ return rangeSumBST(root.left, low, high); } else { return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high); } } } Backtracking 알고리즘을 사용했다. 이것도 O(n)이다.

if문으로 간단하게 푸는 문제입니다. c언어로 풀었습니다. 문제는 아래 링크와 같습니다. 문제 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net 코드 및 풀이 #define _CRT_SECURE_NO_WARNINGS #include int main(void) { int A, B, C; scanf("%d %d", &A, &B); scanf("%d", &C); if (B + C < 60) printf("%d %d", A, B+C); else { int hour = (B + C) / 60; int min..

Baekjoon 백준, 9012번 자료구조 괄호 문제 풀이 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS..

Baekjoon 백준, 10828번 자료구조 스택 문제 풀이 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주..