본문 바로가기
뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT (Java, Level 2) 처음 풀이 1. 두 문자열을 소문자 (or 대문자)로 변환 2. 각 문자열을 두 글자씩 쪼갠 후 영문자 쌍일 때만 Map의 원소로 삽입 3. 두 맵을 비교하여 교집합 크기 / 합집합 크기를 구하여 자카드 유사도를 구한다. - 교집합의 크기 : 두 맵에서 같은 key끼리의 value 값의 최소값 - 합집합의 크기 : 두 맵의 value 값들의 총합 - 교집합의 크기 final int INTEGER = 65536; public int solution(String str1, String str2) { String newStr1 = str1.toLowerCase(); String newStr2 = str2.toLowerCase(); Map subStrMap1 = splitStr(newStr1); Map subS.. 2022. 6. 19.
[3차] 방금그곡 - 2018 KAKAO BLIND RECRUITMENT (Java, Level 2) 처음 풀이 멜로디 전처리 #이 붙은 음은 글자 수가 달라 처리가 어려우므로 소문자로 바꿔준다. publicString makeNewMelody(String melody) { return melody.replace("C#", "c") .replace("D#", "d") .replace("F#", "f") .replace("G#", "g") .replace("A#", "a"); }//makeNewMelody() end 연주 시간 구하기 public int getDuration(String startTime, String endTime) { StringTokenizer stForDuration = new StringTokenizer(startTime, ":"); int startTimeHour = Intege.. 2022. 6. 19.
로봇 청소기 - 백준 14503 (Java) https://www.acmicpc.net/problem/14503 풀이 1. 현재 위치에서 왼쪽으로 90도씩 회전하면서 해당 방향으로 이동할 수 있다면 이동한다. 2. 이동한 위치에서 또 왼쪽으로 90도씩 회전하면서 해당 방향으로 이동할 수 있다면 이동한다. 3. 만일 모든 방향으로 이동할 수 없을 경우, 현재 위치에서 1칸 뒤 (현재 방향에서 반대 방향)가 빈 칸이면 (청소를 이미 했더라도) 현재 방향을 유지한 채 이동하고, 1칸 뒤가 벽이라면 작동을 멈춘다. 현재 위치에서 조건 따지고, 이동하고서도 똑같이 조건 따지고... 하는 과정이 계속 진행되는 형태라 재귀로 접근했다. 입력을 받고 여러 변수를 초기화하고 재귀 메서드를 처음 호출하는 main() static boolean[][] isVisite.. 2022. 6. 17.
가르침 - 백준 1062 (Java) 풀이 일단 a, n, t, i, c 알파벳은 기본적으로 배워야한다. 각 단어에서 앞 "anta"와 뒤 "tica"를 뺀 가운데 부분에서 a, n, t, i, c를 제외한 문자가 있으면 이를 list에 따로 저장한다. 그리고 해당 list에서 알파벳을 하나씩 선택하면서, 현재까지 선택한 알파벳으로(a, n, t, i ,c 포함) 몇 개의 단어를 커버할 수 있는지 매번 체크한다. 총 배울 수 있는만큼 알파벳을 배운 상태면 백트래킹으로 이전 분기로 돌아가 list에 있는 다른 알파벳을 선택하면서 커버할 수 있는 단어의 최대 숫자를 갱신한다. 알파벳을 선택할 때에는 순서가 상관없고, 중복을 허용하지 않기 때문에 조합이다. public class Main { static int words, max, total =.. 2022. 6. 8.
암호코드 - 백준 2011 (Java) 나의 풀이 맨 처음엔 각 자릿수를 1자리 혹은 2자리로 나누는 전체 경우의 수를 구하면 된다고 생각해 DFS로 접근하려 했다. 하지만 주어진 암호의 자릿수가 최대 5000자리라 다른 방법을 고민해야했다. dp로 접근이 가능해보여 시도했다. 그리고 암호가 잘못된 경우가 어떨 때인지 생각해보니 '0'을 고려해줘야 했다. 0의 앞자리가 1 혹은 2가 아닐 경우 잘못된 암호 그 이유는 0은 10, 20일 때만 해석이 가능하기 때문이다. 이를 토대로 규칙을 찾아보면 다음과 같다. dp[n] = dp[n-1] (맨 마지막 숫자가 0이 아닐 때) + dp[n-2] (뒤 두 자리의 수가 10이상 26이하일 때) dp[n]은 n자리 암호 해독이 가능한 경우의 수 이를 토대로 코드를 작성하면 아래와 같다. public s.. 2022. 5. 31.
리모컨 - 백준 1107 (Java) https://www.acmicpc.net/problem/1107 전체 풀이 1. 시작점인 100에서부터 "+, -"만으로 target까지 이동하는 횟수를 구한다. 2. 2-1 사용할 수 있는 숫자가 없을 경우 1에서 구한 수를 출력하고 끝낸다. 2-2 사용할 수 있는 숫자로 이루어진 수 중 target과 가장 가까운 수를 구하고, 해당 수와 target까지의 거리와 해당 수의 자릿수를 더한다. 3. 1과 2-2에서 구한 수 중 최솟값을 출력한다. main() static ArrayList impossibleList = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader bf = new Buf.. 2022. 5. 31.
포도주 시식 - 백준 2156 (Java) https://www.acmicpc.net/problem/2156 처음 풀이 맨 처음 문제를 읽고는 DFS 쪽으로 접근해볼까 했는데 조건이 포도잔이 최대 10000개까지라서 안될 거라 생각했다. 그래서 dp쪽으로 한번 접근해봤다. 연속된 3개의 와인은 마실 수 없다 이 조건을 어떻게 dp 풀이 방식에 적용할 수 있을까 고민했다. dp[x] 는 x번째 와인까지의 최댓값인데 이를 3가지 경우로 나눠서 각각 dp[x][0], dp[x][1], dp[x][2]에 해당 값을 저장한다. dp[ x ][ 0 ] -> x번째까지 연속된 와인이 0개인 경우의 최댓값, 즉 x번째 와인을 선택하지 않은 경우 -> dp[x][0] = dp[x-1][0], dp[x-1][1], dp[x-1][2] 중에 최댓값이 된다. dp[ .. 2022. 5. 24.
기타리스트 - 백준 1495 (Java) https://www.acmicpc.net/problem/1495 처음 풀이 문제 읽고 처음 생각난 풀이는 DFS를 이용한 풀이었다. 곡이 진행되고 다음 곡이 진행되기 전에 볼륨을 조절하고, 볼륨이 범위 안에 있다면, 새로운 볼륨으로 다음 곡을 진행하고, 또 그 다음 곡이 진행되기 전에 볼륨을 조절하고.... 중단 조건은 다음에 진행할 곡의 index가 전체 곡 개수와 같을 때이다. 즉 마지막 곡을 연주하고 나서 볼륨을 max값과 비교해 최대값으로 갱신한다. 위 과정을 코드로 나타내면 다음과 같다. public static void dfs(int now, int index, int total, int limit) { if (index==total) { max = Math.max(max, now); ret.. 2022. 5. 22.
창고 다각형 - 백준 2304 (Java) https://www.acmicpc.net/problem/2304 처음 풀이 1. 기둥 정보 입력 받아 각 기둥에 대해 Pole 객체를 만들고 List에 저장, 위치를 기준으로 정렬 static class Pole { int location; int height; public Pole(int location, int height) { this.location = location; this.height = height; } } public static void main(String[] args) throws IOException { int totalPole = Integer.parseInt(bf.readLine()); StringTokenizer st = null; List poleList = new Ar.. 2022. 5. 19.
에디터 - 백준 1406번 (Java) 처음 풀이 1. 커서를 포인터로 생각하여 현재 커서 위치에 해당하는 index값을 저장할 pointer 변수를 둔다. 2. StringBuilder에 문자열을 담아두고, StringBuilder 메서드인 deleteCharAt()과 insert()를 이용해 명령값과 현재 pointer 값에 따라 내부 문자열을 수정한다. public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(bf.readLine()); //현재 문자열 맨 마지막에 커서 위치해야 한다. int.. 2022. 5. 14.

티스토리툴바