본문 바로가기

프로그래머스25

[알고리즘] 프로그래머스 - 다음 큰 숫자 1. 문제 2. 나의 풀이 처음에는 직접 binaryNumber를 구하는 메소드와 binary로 변환했을 때 1의 갯수를 구하는 메소드를 짰는데 효율성 테스트에서 실패하였다. 찾아보니까 Integer를 binaryString으로 바꿔주는 메소드와 Integer에서 2진수로 변환했을 때 1의 개수를 반환해주는 메소드가 있었다. 해당 메소드를 사용하니 효율성 테스트를 통과할 수 있었다. binaryString으로 바꾸는 부분의 경우 구현을 살펴보니 비트 단위로 조작하는 부분이 있었다. 이 부분은 좀 더 찾아봐야할꺼 같다. Integer.toBinaryString(n); Integer.bitCount(n); class Solution { public int solution(int n) { int answer .. 2021. 11. 20.
[알고리즘] 프로그래머스 - 올바른 괄호 (Stack) 1. 문제 2. 나의 풀이 전형적인 Stack 문제로 반복문을 통해서 문자열을 순회한다. 문자가 '(' 일 경우에는 Stack에 넣어주고 ')'일 경우에는 Stack에서 제거한다. 만약 더이상 제거할게 없는데 ')' 문자가 오면 올바른 괄호가 아니다. 또한 문자열을 모두 순회하고나서 Stack에 '('가 남아있다면 괄호가 제대로 닫히지 않고 끝났기 때문에 올바른 괄호가 아니다. import java.util.*; class Solution { boolean solution(String s) { boolean answer = true; Stack stack = new Stack(); int len = s.length(); for(int i=0;i 2021. 11. 15.
[알고리즘] 2018 카카오 블라인드 - 프렌즈4블록 1. 문제 2. 문제 풀이 블록을 아래로 내리는 부분이 좀 까다롭고 나머지는 문제에 주어진대로 풀면 되는 문제였다. 1. 주어진 1차원 배열을 2차원 배열로 옮긴다. 2. 2*2영역이 같을 경우 해당 영역을 check 2차원 배열에 true로 표시한다. 3. check 2차원 배열에 true로 표시된 공간을 블록이 터졌다는 의미로 "*"로 바꾼다. 4. 블록을 터트린 후 위에 있던 블록들을 아래로 내린다. 블록을 내리는 downBlock() 메서드의 경우 하나라도 내려간 블록이 있으면 해당 열의 블록을 내리는 작업을 다시 반복하였다. 내려가는 블록이 없을 경우 다음 열을 검사한다. import java.util.*; class Solution { public static int solution(int m.. 2021. 2. 3.
[알고리즘] [2020 카카오 블라인드] 괄호 변환 1. 문제 문제를 딱 보면 엄청나게 많은 조건들이 있다. 사람은 한번에 여러가지를 기억하지 못하기 때문에 조건을 이해하는데 시간이 오래 걸렸다. 2. 나의 풀이 문제를 봤을 때 재귀를 이용하는 문제라는 것을 알았다. 우선 문제의 조건대로 주어진 문자열의 길이가 0일 경우 빈 문자열을 반환하게 하고, 현재 문자열이 올바른 괄호 문자열일 경우 해당 문자열을 그대로 반환했다. 또한 문자열 u는 균형잡힌 괄호 문자열이므로 문자열 w를 u와 v로 나누어주는 getBalanceIndex() 메서드를 만들어 주었다. 여기서 return할 때 1을 더해주어 문자열 u와 v를 구분하는 인덱스를 구한다. 그리고 u가 올바른 괄호 문자열일 경우는 문자열 u에 v를 다시 나누는 재귀함수를 호출해서 더해준다. u가 올바른 괄호.. 2021. 1. 18.
[알고리즘] [2020 카카오 블라인드] 문자열 압축 1. 문제 2. 나의 풀이 처음에 리스트에 단어를 넣지 않고 현재 단어와 다음 단어를 구해서 풀려고 했더니 인덱스를 벗어나는 등의 엄청난 시간 낭비가 있었다. 비효율적이지만 푸는게 우선이니 스트링 리스트를 먼저 하나 선언하고 리스트에 단어를 집어 넣는데, 마지막 단어의 경우는 남은 단어를 모두 넣도록 처리했다. 리스트에 넣은 단어가 현재 인덱스의 단어와 뒤의 단어를 비교해서 같을 경우 몇개가 같은지 개수를 세어 주었고, 같지 않은 경우는 count가 1일 경우와 1보다 클 경우로 나누어서 문자열 앞에 숫자를 붙여줄지 안붙여줄지를 정하였다. 그리고 마지막 단어의 경우는 마지막 단어와 그 앞의 단어가 같은 경우와 같지 않은 경우로 구분하여 숫자를 붙여줄지 안붙여줄지를 정하였다. import java.util.. 2021. 1. 18.
[알고리즘] 2020 카카오 인턴십 - 보석 쇼핑 (Two Pointers Algorithm) 1. 문제 이번 문제는 2020 카카오 인턴십에 출제된 보석 쇼핑이라는 문제이다. 2. 문제 풀이 처음에 어떤 알고리즘과 자료구조를 사용해야할지 감을 못잡아서 제대로 접근을 하지 못했었다. 이번 문제는 하나의 1차원 배열에서 left, right를 0으로 두고 left와 right를 조작해서 원하는 값을 찾는 투포인터스 알고리즘(Two Pointers Algorithm)문제이다. 1. 우선 현재 map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류보다 작을 경우 right를 1씩 증가시켜주면서map에다가 넣는다. 2. map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류와 같을 경우 left를 하나 증가 시켜주고 map에 들어있는 보석의 개수가 0개이면 map에서 해당 key를 삭제.. 2021. 1. 13.