▼ 문제 링크 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 이 문제는 많은 시행 착오 끝에 내가 생각한 일반적인 방법(비트가 1개 혹은 2개가 다른 모든 경우의 수를 비교하는 방법)으로는 효율성 테스트를 통과할 수 없다는 것을 깨닫고 결국 집단 지성의 힘을 빌린 문제였다. 내가 처음 생각했던 방법으로는 정확성은 통과한 거 같은데 효율성에서 막히더라 🥲 아무튼 찾아본 바로는 풀이 방법이 다음과 같다. 주어진 숫자가 짝수일 때 짝수를 비트로 바꾸면 1 0 0 0 (= 8)처럼 맨 마지막 비트가 0이 된다. 이때, 비트가 1개 또는 2개가 다르면서 가장 작은 수 = 자연스럽게 마지막 비트 0을 1로 바꾼 수가 된다. 즉, 주어진 수에서 1만 더해주면 된다. 주어진 숫자가 홀수일 ..

▼ 문제 링크 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 우리가 흔히 하는 캔x크러쉬사, 프x즈팝 같은 게임을 구현하는 문제다. 그런데 이제 그 게임에서 블록을 터트릴 수 있는 방법 중, 단 하나, 2x2 블록만 터지도록 설계하면 된다. STEP1. 2x2 행렬을 살펴보면서 터트릴 블록 찾기 그림1처럼 2x2 총 4개의 블록이 모두 같은 블록인 경우를 찾아야 한다. 단, 이때 왼쪽의 라이언 블록처럼 2x2가 서로 겹쳐도 상관 없다! 물론, 겹쳐도 상관 없지만 터질 라이언 블록의 총..

▼ 문제 링크 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 처음에는 문제를 읽고 다음과 같이 단순한 과정을 거쳐 풀이를 시도했다. 1) k개의 숫자를 제거한 모든 조합의 숫자 구하기 2) 1)에서 구한 숫자 중에서 가장 큰 수 구하기 그러나, 이렇게 했더니 1, 11, 12번 테스트케이스 말고는 전부 시간 초과로 실패했다. 😢 한참을 고민해 본 결과, 이건 내가 지금처럼 생각해서는 시간 초과를 해결할 수 없을 거라고 생각했고... 결국 구글링의 힘을 빌렸다. 😭 💡문제 해결 포인트 이 문제에서는 숫자의 순서가 뒤섞이지 않는다! 문제 내 설명에 이런 문장이 있다. "예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. ..

▼ 문제 링크 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 괄호를 회전한다는게 당최 무슨 말인지...? 했는데 알고보니까 회전... 이라기 보다는 한 칸씩 앞으로 민다는 말이 더 맞는 것 같다. 문제에서 주어진 예제를 살펴보자. 왼쪽으로 '회전'이란 말 대신, 왼쪽으로 '한 칸씩 이동'이라고 생각하면 쉽다. 아래 그림처럼 맨 앞의 괄호가 밀려서 맨 뒤로 이동하는 것이다. 이렇게 괄호를 이동시키는 과정을 괄호의 개수-1만큼 반복한다. 이 문제를 해결하기 위해 일단 첫번째로 주어진 괄호가 개폐가 옳은 괄호인지 아닌지 확인하고, 두번째로 이 괄호들은 한 칸씩 이동해 새로운 괄호열을 만든다. 그리고 그 괄호열을 다시 첫번째 과정인 옳은 괄호인지 확인하는 절차를 밟으면 된다. 1단계: 옳은 ..

▼ 문제 링크 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 다른 문제들 보다도 유난히 카카오에서 나온 문제들은 문제 길이가 엄청나게 길다. 상대적으로도, 절대적으로도... 그래서 문제 이해하는 데 에도시간이 소요되는 편인데, 이 문제를 풀기 위해 필요한 요건들을 정리하면 다음과 같다. 주어진 데이터베이스의 속성으로 가능한 모든 조합을 만든다. 이 조합들을 가지고 유일하게 튜플을 구분할..

▼ 문제 링크 Max Consecutive Ones III - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 0과 1로만 이루어진 배열과 숫자 k가 주어진다. 이때, k개 만큼 0을 1로 바꿀 수 있다. k는 0부터 배열의 개수까지 모두 가능하며, 0을 k개만큼 1로 바꿨을 때, 가장 긴 연속된 1의 개수를 구해야 한다. Binary Tree를 사용한 사람도 있지만, 우리는 훨씬 쉽게 "Sliding Window" 기법을 사용해 답을 구할 수 있음 "Slidin..

▼ 문제 링크 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 그 옛날 오락실 게임기에서 랭킹에 올라갈 만큼(보통 10~20등 내외) 기록을 세우면 닉네임을 입력하라는 화면이 뜬다. A부터 Z까지, 보통 3자리, 종종 4자리 닉네임을 입력할 수 있곤 했다. 조이스틱을 위로 올리면 A -> B로, 반대로 아래로 내리면 B -> A로 이동한다. 좌우로 이동해서 닉네임 자리를 옮길 수 있다. 즉, 이 문제는 이 오락실 게임기로 주어진 닉네임을 입력할 때 움직여야 할 최소 횟수를 구하는 문제다. ..

▼ 문제 링크 CountNonDivisible coding task - Learn to Code - Codility Calculate the number of elements of an array that are not divisors of each element. app.codility.com 역시나 정답은 맞췄지만, 시간 복잡도에서 실패한 케이스 기존 배열의 값을 새로운 배열의 index로 전환하고 해당 index의 값을 기존 배열의 값의 총 개수로 변환하는 게 풀이의 핵심이었다. 이게 무슨 말이나면 original[i] = k 이고 original배열에서 값 k가 배열 original 내에 전부 n개 있을 때 이 배열을 new배열에 위에서 언급한 방법대로 바꾸면 new[k] = n 이 된다. # 풀..