목록문제 (13)
코드 한 줄
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 문자열 배열(string array)이 주어지면, 제일 긴 공통된 접두사(prefix)의 길이를 찾아라 예제 } Input : ["apple", "apps", "ape"] Output : 2 // "ap" Input : ["hawaii", "happy"] Output : 2 // "ha" Input : ["dog", "dogs", "doge"] Output : 3 // "dog" 이 문제는 가장 긴 공통된 접두사가 첫 단어라고 가정하고, 각 문자마다 모든 단어에 비교한다. 비교하는 방식은 단어의 같은 위치에 문자가 있는지 확인한다. 만약 문자가 다르거나, 문자가 없으면 현재의 문자 위치까지만 공통된 접두사이다. int longestPrefixLen..
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수 배열(int array)과 정수 N이 주어지면, N번째로 큰 배열의 원소를 찾아라. 예제 } Input : [-1, 3, -1, 5, 4], 2 Output : 4 Input : [2, 4, -2, -3, 8], 1 Output : 8 Input : [-5, -3, 1], 3 Output : -5 이 문제는 “Quick Select”의 알고리즘을 사용하는 대표적인 문제이다. Quick select는 퀵 정렬(quick sort)를 이용하는 알고리즘이다. 퀵 정렬의 pivot을 정하고 1차 정렬을 하면 pivot의 원소 위치는 최종 정렬된 배열의 위치가 된다. 이것을 이용하여 모든 배열을 정렬 하지 않고, pivot의 값을 비교하여, 찾는 값에..
먼저 1번 문제를 들어가면 다음과 같은 화면이 나온다. 가장 먼저, 소스를 확인해보자. 위 코드를 살펴보면 유저레벨이란 쿠키가 이 문제의 핵심이란 것을 알 수 있다. 그러나, 0부터 9의 값이 들어가면 유저레벨을 1로 초기화하며, 6보다 큰 경우에도 1로 초기화 한다. 마지막 if문을 보면, 문제를 풀기위해서 유저레벨을 5보다 크게 만들어야 한다. 5보다 크면서 6보다 크지 않아야 한다... 정답은 실수를 입력하면 된다. 크롬의 확장 프로그램은 EditThisCookie를 이용해 간단히 해결해주자. 유저레벨의 쿠키값이 1로 설정되어 있는 것을 볼 수 있다. 이를 5.5로 수정하여 체크를 하고, 새로고침을 해주면 다음과 같이 해결할 수 있다. 본인은 이미 풀었기 때문에 다른 화면이 나왔다.
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. String이 주어지면, 중복된 char가 없는 가장 긴 substring의 길이와 문자열을 찾아라. 예제 } Input : aabcbcbc Output : 3 // abc Input : aaaaaaa Output : 1 // a Input : abbbcedd Output : 4 // bced 이 문제는 해쉬맵을 사용하여 char와 char의 인덱스를 저장하여 풀면 된다. string의 각 char를 보면서 해쉬맵에 있다면 substring 시작점을 char의 인덱스+1 로 두면 된다. 그리고 현재 char의 인덱스와 시작점의 거리를 계속 계산하여 가장 큰 값을 리턴하면 된다. int longestSubstringLength(String s) { ..
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수 배열이 주어지면 0이 아닌 정수의 순서를 유지하며 모든 0을 배열의 오른쪽으로 옮겨라 예제 } Input : [0, 5, 0, 3, -1] Output : [5, 3, -1, 0, 0] Input : [3, 0, 3] Output : [3, 3, 0] 이 문제는 0을 오른쪽으로 옮기는 것보다 0이 아닌 정수를 왼쪽으로 옮긴다고 생각하면 쉽게 풀 수 있다. void solve(int[] input) { int position = 0; // 0이 아닌 정수가 들어갈 곳 for (int i = 0; i < input.length; i++) { if (input[i] != 0) { swap(input, i, position); position++; ..
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수 배열이 주어지면 두 번째로 큰 값을 출력하라 예제 } Input : [10, 5, 4, 3, -1] Output : 5 Input : [3, 3, 3] Output : Does not exist. 이 문제는 가장 큰 값을 구하는 로직과 거의 똑같다. 가장 큰 값과 두 번째 큰 값을 저장할 변수를 만들고 배열 원소들과 비교하면 된다. 중요한 엣지 케이스는 배열이 0 이나 1개의 원소를 가지고 있으면 두번째 큰 값이 존재 하지 않는 것과 [3, 3, 3] 같은 경우처럼 두 번째로 큰 값은 존재 하지 않는다. 이를 계산하기 위해 두 번째 큰 값을 저장할 변수를 Integer.MIN_VALUE로 두고 for루프가 끝난 뒤 값이 변했는지 체크하면 된다..
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 주어진 String에 모든 단어들을 거꾸로 출력하라. 예제 } Input : "abc 123 apple" Output : "cba 321 elppa" 이 문제는 긴 String 을 각 단어로 나눈 다음, 각 단어를 거꾸로 하고, 모든 단어들을 합치면 풀 수 있다. public String reverseString(String s) { String words[] = split(s); StringBuilder res = new StringBuilder(); for (String word: words) res.append(reverse(word) + " "); return res.toString().trim(); } public String[] spli..
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 간격(interval)으로 이루어진 배열이 주어지면, 겹치는 간격 원소들을 합친 새로운 배열을 만들어라. 간격은 시작과 끝으로 이루어져 있으며, 시작은 끝보다 작거나 같다. 예제 } Input : {{2, 4}, {1, 5}, {7, 9}} Output : {{1, 5}, {7, 9}} Input : {{3, 6}, {1, 3}, {2, 4}} Output : {{1, 6}} 문제의 어려운 점은 간격 원소들이 무작위로 순서가 돼있는 것이다. 주로 이런 경우엔 자료구조를 써서 무작위 원소들을 쉽게 정리하거나, 원소들을 정렬하면 된다. 이 문제에선 간격 원소들을 정렬해보겠다. 간격 원소가 {start, end}로 나누어 있다고 가정하고, start로 ..
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수 배열과 타겟값이 주어지면, 합이 타겟값이 되는 두 원소의 인덱스를 찾아라. 예제 } Input : [2, 5, 6, 1, 10], 타겟값 : 8 Output : [0, 2] // 배열[0] + 배열[2] = 8 이 문제는 해쉬맵을 사용하여 원소 값과 원소 인덱스를 저장하면 쉽게 풀 수 있다. 각 배열의 원소마다 (타겟 - 원소 값)이 해쉬맵에 있는지 확인하면 된다. int[] solution(int[] input, int target) { Map map = new HashMap(); for(int i=0; i
* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 먼저, 팰린드롬(palinedrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 똑같은 단어를 말한다. 정수 n에 대하여 팰린드롬인지 알아내는 방법을 구현하면 되고, 정수를 문자열로 변경해서는 안된다. 예제} Input : 12345 Output : False Input : -101 Output : False Input : 11111 Output : True Input : 12421 Output : True 일단 엣지 케이스를 살펴보자. 정수가 마이너스면 팰린드롬이 될 수 없다. 그리고 0이 아닌 정수가 0으로 끝난다면 이 경우 역시 팰린드롬이 될 수 없다. 주어진 숫자를 전반부와 후반부로 나눈다. 예를 들어 1233210이 주어지면, 123이 전반..