1. 서론해시 + 조합으로 금방 풀리겠지라고 접근했다가 고려하지 못한 케이스 때문에 시간을 오래 잡아 먹었던 문제이다. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2. 본론이 문제의 핵심은(1) 옷 여러벌을 같은 종류에서 고르면 안됨 (중복 x)(2) 1, 2, ... n 가지 입는 경우의 수를 더해야 함 (조합) 으로 해시 + 조합론 을 활용한 문제풀이가 적합하다. 때문에 필자는 다음과 같이 구조를 짜보았다.(1) n과 r 을 파라미터로 갖는 조합 함수 `comb()` 구현(2) 입력 ..

1. 문제로마자를 숫자로 변환하여 반환하는 함수를 구현하는 문제이다. 2. 풀이이 문제의 핵심은 로마자의 결합여부 확인이다. 문제의 TestCase1 처럼 단순한 문자는 그냥 숫자를 더하면 된다."III" III = 3. 하지만 로마자는 IV = 4 와 같이 결합이 가능하다."MCMXCIV" M = 1000, CM = 900, XC = 90 and IV = 4. 결합되어 있는 문자 케이스를 잘 보면, 앞에 있는 문자의 값보다 뒤에 있는 문자의 값이 더 크다. CM의 경우 'C' = 100, 'M' = 1000 이고 CM = 900이다.즉, CM 은 M-C 이다. 이 원리를 이용하면 쉽게 풀 수 있다. class Solution { public int romanToInt(String s) { ..

■ 문제두 개의 배열이 주어질 때 이를 합치고 중앙값을 반환하는 함수를 구현하는 문제이다. ■ 풀이이 문제는 중앙값을 구하는 것이 핵심일 것 같다.필자는 다음과 같은 방식으로 구현했다.리스트로 배열 합치기 리스트 정렬중앙값 구하기여기서 중앙값을 구할 땐 길이의 홀수/짝수 여부 두가지 케이스로 생각했다. 짝수일 때 - ([size / 2] + [size / 2 -1]) / 2.0홀수일 때 - [size / 2] / 2.0class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { double answer = 0; ArrayList lst = new ArrayList(); for(..

■ 문제문자열 s 중 중복되지 않은 부분배열의 최대길이를 구하는 문제이다. ■ 풀이처음 설계를 할 때 자료구조 사용 없이, String.substring() 을 사용하여 풀고자 했다.i->끝까지 for 문 순회하면서 시작하는 첫번째 startChar 를 추출startChar 인덱스를 제외하고 뒤의 문자들을 substring() 으로 서브 문자열 추출이 과정에서 서브 문자열에 startChar 포함 여부 확인있으면 x없으면 최대 길이 업데이트 이러한 설계로 풀려고 하였으나 반례가 존재했다.startChar 가 아닌 다른 중복되는 문자에 대한 예외처리가 필요하다.예를 들어 "abcabcbb" 일때, c가 4번째 a가 startChar 일 경우, 뒤에 "a" 가 없기 때문에 해당 케이스는 통과하지 못한다. 때..

■ 문제배열에서 요소 2개를 더했을 때 target 이 나오는 인덱스를 구하는 문제이다. ■ 풀이현재 문제에서는 시간제한이 딱히 명시되어 있지 않다.실제로 브루트포스 알고리즘을 써서 완전탐색을 해도 풀이는 가능하다. 하지만 실제 코테에서는 완전탐색으로 풀 수 있는 Constraints 의 문제가 나오지 않을 것 같아 다른 방법을 생각해보느라 시간이 좀 걸렸다. a + b = target 이 나오는 공식에서 해결이 가능한 미지수는 a 또는 b 와 target 이다.[2, 7, 11, 15] 를 예시로 들어봤을 때 index = 0 일 경우, 2+b = 9 이다. 즉, 단순 for 순회에서 9-2 인 값을 O(1) 로 찾을 수 있는 설계를 하면 된다.이를 위해 HashMap 을 사용했다.for 문을 돌며 H..

■ 문제j - i != nums[j] - nums[i] 가 성립되는 부분 배열의 수를 찾는 함수를 구현하는 문제이다. ■ 풀이처음 풀 때 Constaints 조건을 못보고 완전탐색으로 풀었다가 Time Limit 이 걸렸다.class Solution { public long countBadPairs(int[] nums) { int size = nums.length; long answer = 0; for(int i = 0; i  최대 10,000 배열이 있기 때문에 완전 탐색으로 풀면 O(N^2) 이라 10000*10000 연산을 해야한다.이를 해결하기 위해선 조건을 재해석 해야 한다. j - i != nums[j] - nums[i] 를 j-nums[j] != i..

1. 문제요약하자면 a c 또는 a > b 입출력 예시를 보면 문제를 더 자세히 이해할 수 있고, 제한시간은 3초 이내이다. numbers가 100이 최대이므로 단순 조회 및 비교 로직으로 구현하여도 제한시간을 초과하는 케이스는 발생할 것 같지 않다.2. 풀이isZigZag 함수를 static 으로 구현하여 지그재그 여부를 확인하는 과정을 구현했다.static int isZigZag(int a, int b, int c){ if(a c) return 1; else if(a > b && b 3. 결어서류합격한 회사에서 CodeSignal 플랫폼에서 코테를 보길래 처음 CodeSignal 이라는 사이트를 사용해봤다. 처음 봤을 땐 영어로 된 문제에 잔뜩 긴장했으나 막상 읽어보니 어려운 단어는 ..