Algorithm

[JAVA] 백준 2143번 【G3.두 배열의 합】

문제 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 각 배열의 부분합을 전부 구한다. List sumsA = new ArrayList(); n = Integer.parseInt(br.readLine()); A = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::valueOf).toArray(); for (int i = 0; i < n; i++) { long res = 0;..

[JAVA] 백준 18869번 【G5.멀티버스 Ⅱ】

문제 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 풀이 위 문제를 풀기 위해서는 좌표 압축을 사용해야한다. 좌표 압축에 대한 문제를 하나 풀어보면 좋다. 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 좌표 압축을 하면 아래와 같은 결과가 나온다. 즉, 특..

[JAVA] 2021 KAKAO BLIND RECRUITMENT 【합승 택시 요금】

문제에서 요구하는 답을 간략하게 표현하면, (출발지점 → 경유지점) 요금 + (경유지점 → 무지 목적지) 요금 + (경유지점 → 어피치 지점) 요금 = 최종 요금 위 식으로부터 구해진 최종 요금의 최솟값을 답으로 출력하면 된다. 처음에 푼 방식은 시간 초과가 계속 발생했는데 for(int i=1;i

[JAVA] 2021 카카오 채용연계형 인턴십 【거리두기 확인하기】

맨해튼 거리가 사실상, 테이블을 제외한 두 응시자 사이의 격자 거리이므로 각 룸마다, 응시자(P)가 발견됐을 때 bfs()를 실행시켜 그 응시자와 가장 가까운 다른 응시자를 찾을때까지 루프문을 돌리고 발견되면 거리를 리턴하도록 bfs()를 구현하였다. 가장 가까운 응시자의 거리가 2이하인지 체크한 뒤, 2이하라면 0을 기록하도록 로직을 구성하였다. import java.util.*; class Solution { String[][] map; boolean[][] checked; Queue q; int[] dr = {1,-1,0,0}; int[] dc= {0,0,1,-1}; public int[] solution(String[][] places) { int[] answer = new int[5]; Arra..

[JAVA] 2020 카카오 인턴십 【수식 최대화】

문자열을 어떻게 처리할까 굉장히 많이 고민했던 문제였다. 정규식을 사용하는게 코드가 더 간결해질 것 같아서 정규식을 사용했다. 그리고, 연산자는 + - * 3개만 주어지기 때문에, 연산자 우선순위를 직접 명시해서 선언해주었다. "*+-","+*-","*-+","+-*","-*+","-+*" 위와 같은 6가지 경우가 있을 수 있다. 먼저 정규식 "\\d+|\\S" 를 사용하면, 숫자와 연산자로 나눌 수 있다. 그리고, 정규식을 바탕으로 분리한 원소들을, 순회하면서 숫자라면 스택에 집어넣고, 연산자이면서 우선순위에 해당하는 연산자라면 스택에 있던 숫자를 빼서 연산처리 한 뒤, 넣어놓는 방식으로 표현식을 변환시켰다. 우선순위가 "*+-" 라고 가정했을때 "100-200*300-500+20" 이 식은 "100-..

[JAVA] 2019 카카오 개발자 겨울 인턴십 【징검다리 건너기】

일단 stones 배열의 크기가 200000개이므로, 이중 for문을 절대 사용하면 안된다. 따라서 배열의 원소값으로 이분 탐색을 해서 값을 찾아야 한다. [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 예제 처럼 위와 같은 경우에서 전체 3을 감소하면 [-1 1 2 0 -1 -2 1 -1 2 -2] 가 되는데, 0이하인 원소가 3개 연속으로 존재하는 구간이 생기므로 답이 3이 되는것이다. 만약 2를 감소하면 [0 2 3 1 0 -1 2 0 3 -1] 이 되어 0이하인 원소가 3개 연속으로 존재하지 않기 때문에 다음 사람이 건너갈 수 있다. 따라서, 전체에 x를 감소시켰을 때, 0이하인 돌이 연속으로 k개 이상 존재하는 x값을 이분탐색으로 구하면 된다. 초기값을 left = stones 배열의 최..

[JAVA] 2020 KAKAO BLIND RECRUITMENT 【괄호 변환】

처음에 )()(() 인 경우 u= [ )( ] 와 v= [ )(() ] 로 나눈 뒤 "()" + "()" +"()" 가 되어서 "()()()" 인줄 알았지만, 과정이 좀 달랐다. )( 에서 앞 뒤 문자열을 제거하면 "" 빈 문자열만 남는다. 따라서, '(' 를 붙이고 v= [ )(() ] 를 다시 1단계부터 진행한 문자열을 붙이고 ')' 를 붙인다. v = [ )(() ] 를 다시 1단계를 시작하면 u = [ )( ] 와 v = [ () ] 로 나눌 수 있으므로 u는 또 다시 빈 문자열이 되고 '(' 를 붙이고 v = [ () ] 를 다시 1단계부터 진행한 문자열을 붙이고 ')' 를 붙인다. v를 대상으로 또 1단계를 진행하면, 완전 문자열이므로 () 가 반횐된다. 따라서 일련의 과정을 run() 이라고..

[JAVA] 2018 KAKAO BLIND RECRUITMENT【프랜즈4블록】

코드량 실화인가ㅋㅋㅋ 뭔가 알고리즘 문제를 풀었다는 느낌보다는 프로그램을 하나 만든 느낌이다. 문제 자체는 쉬웠고, 가장 헷갈렸던 부분은 블록을 제거하고 옮기는 부분이었다. 이부분은, StringBuilder를 사용해서 해결했는데, 나는 제거한 블록을 "0"으로 기록해놓았었다. 따라서, 위와 같은 상황에서, 첫번째 열을 출력하면, TTT00T 와 같이 출력된다. 따라서, 0이 아닌경우에만 StringBuilder에 합쳐주면, TTTT 를 얻을 수 있다. 그리고 행의 갯수가 일치해야하므로 행의 갯수만큼 "0"을 더하면 TTTT00 이 된다. 두번째 열을 예로 한번 더 설명해보면, MT000T 인 상황에서 MTT 로 만든 뒤, MTT000 으로 만들어주는 것이다. 이렇게 변환한 문자를 map에 열 단위로 기..

[JAVA] 2019 KAKAO BLIND RECRUITMENT【오픈채팅방】

map에 로 저장해 나간다. Enter로 입력되면 입력될때마다 map에 바로 입력과 업데이트를하고, Change인 경우에도 업데이트만 해주면 간단하게 해결된다. 외부에서 닉네임을 바꾸고 들어오는 경우도 Enter로 처리되기 때문에 신경쓸 필요가 없다. import java.util.*; class Solution { HashMap map; public String[] solution(String[] record) { String[] answer = {}; map = new HashMap(); for(String rec : record){ String [] info = rec.split(" "); if(info[0].equals("Enter")){ map.put(info[1],info[2]); }else ..

[JAVA] 2022 KAKAO BLIND RECRUITMENT【주차 요금 계산】

문제 자체는 간단했다, 코드량이 많았을 뿐.ㅎ HashMap 자료형을 이용해서, 자동차가 IN 인 경우 [자동차 번호 = key, 자동차 입차시간 = value] 로 저장한다. 자동차가 OUT인 경우 map에서 입차시간을 추출한 뒤, 이용시간을 구한다. 이용시간은, 다른 map에 [자동차 번호 = key , 주차장 이용시간 = value ] 로 기록해두고, 입차시간을 기록하는 map에 있던 데이터는 삭제한다. 삭제하는 이유는, 나중에 출차 내역이 없는 out하지 못한 차를 확인하기 위해서이다. 그렇게, 이용시간을 다 기록한 뒤, 출차하지 못한 차가 있는지 확인하고, 이용시간에 추가한다. 그리고 주어진 요금 정산 방법대로 계산한 뒤, 자동차 번호 오름차순으로 정렬해서 반환하면 끝이다 // 입차 이후 출차 ..

[JAVA] 2018 KAKAO BLIND RECRUITMENT【n진수 게임】

10진법 수를 n진법에 맞는 문자열로 반환하는 convert() 메서드를 정의하였고 0부터 n진법으로 변환한 문자열을 계속 더해서 길이가 t*m 이상이 될때까지 더했다. 게임에 참가하는 인원이 m명이고, 미리 구할 숫자가 t일때, 만약 튜브의 순서가 m명중에 m번째 순서인 경우가 제일 늦은 순서인 경우이므로 문자열을 t*m까지만 구하면 되기 때문이다. 그리고 do-while 루프문으로 주어진 튜브의 순서에 맞게 t개가 될때까지 문자열을 더해서 답을 구했다. // 진법 n class Solution { String[] unit = {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"}; public String solution(int n, in..

[JAVA] 2018 KAKAO BLIND RECRUITMENT【압축】

map을 사용해서, 기본적으로 A~Z 까지 저장한 뒤, map에 키로 존재하지 않을 때까지 idx를 ++해서 문자를 더하고, map에 추가해주는 방식으로 풀면 되는 간단한 문제였다. import java.util.*; class Solution { HashMap map; List ans; public int[] solution(String msg) { setUp(); int idx = 0; while(idx

[JAVA] 2018 KAKAO BLIND RECRUITMENT 【뉴스 클러스터링】

주어진 문자열을 문자로만 이루어지는 조합을 만들어서 Map에 개수와 기록한다. (예시,["fr":2,"re":1,....]) 두 문자열을 조합별 갯수를 기록한 Map을 이용해서 교집합 수를 구한다. 교집합수는 중복도 허용하므로, 각 Map에 기록되어있는 수의 최솟값으로 기록한다. 그리고 (합집합 수 - 교집합수)가 분모, 교집합 수가 분자가 되어 답을 구한다. import java.util.*; class Solution { HashMap mapA; HashMap mapB; public int solution(String str1, String str2) { int answer = 0; mapA = new HashMap(); mapB = new HashMap(); getCombination(mapA,st..

[JAVA] 2022 KAKAO TECH INTERNSHIP 【두 큐 합 같게 만들기】

문제 자체는 간단하다. 왼쪽 큐 총합이 커지면, 왼쪽 큐 원소를 빼서 오른쪽 큐로 옮기고 오른쪽 큐 총합이 커지면 오른쪽 큐 원소를 빼서 왼쪽 큐로 옮기면 된다. 그리고[1,4] [4,8] 과 같이 주어지면 무한 루프가 돌 수 있기 때문에, while문 탈출 조건을 (두 큐의 길이 합*2) 이상 반복되면 탈출하도록 설정해놨다. 최악의 경우를 가정해서 생각해봤다. 큐1 [1 2 3....n] // 큐 2 [1 2 3 ....m] 큐1 [n] // 큐 2[1 2 3 ...m 1 2 3....n-1] (약 n-1번 소요) 큐1[1 2 3 ....m] // 큐2[1 2 3 ....n] (약 m+1번 소요) 큐 1과 큐2의 원소가 완전히 바뀌려면 n+m번이 소요되고 다시 큐1이 처음 큐1원소로 돌아가려면 n+m번..

[JAVA] 2020 카카오 인턴십 【보석 쇼핑】

Map을 이용해서 보석 종류별 갯수를 기록한다. 그리고 L을 0으로 잡고, gems[L] 이 Map에 존재하면서, 값이 2이상으로 존재하는 경우 값이 1이 될때까지 L을 증가시킨다. 그러면, 제일 앞쪽에 중복으로 존재하는 보석을 제외시킬 수 있다. 그리고, Map의 size 즉, 기록된 보석의 갯수가 보석 종류 수와 일치하면 모든 보석이 존재하는 구간임을 의미하므로 정답을 갱신하고, 이미 기록된 길이보다 작은 경우에만 갱신한다. import java.util.*; class Solution { public int[] solution(String[] gems) { int[] answer = new int[2]; int cnt = new HashSet(Arrays.asList(gems)).size(); in..