2364 - Count Number of Bad Pairs (Java)
·
LeetCode
문제https://leetcode.com/problems/count-number-of-bad-pairs/description/  풀이문제는 i 일 때 j - i != nums[j] - nums[i]. 인 쌍을 몇 개 찾느냐인데 이 문제는 반대로 생각해야 쉽게 풀린다.  우선 위 식을 "정리" 해볼 수 있는데, 정리하면 nums[j] - j != nums[i] - i 형태로 만들 수 있다. 이제 반대로 생각해보자. 총 쌍의 개수에서 우리는 위 조건에 부합하지 않는 쌍을 찾으면 답을 구할 수 있다.위 조건의 반대는?  j > i 일 때  nums[j] - j == nums[i] - i 이다. 이 말을 풀어보면 내가 j일 때 나보다 작은 값 i 가 있을때 nums[j] - j == nums[i] - i 를 ..
380 - Insert Delete GetRandom O(1) (Java)
·
LeetCode
문제https://leetcode.com/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150  풀이set 의 형태에서, random 값을 뽑아낼 수 있는 자료구조를 만드는 문제이다. 우선 insert 와 remove 를 O(1)에 할려면 set이나 map과 같은 자료구조는 필수적으로 필요하다. 그리고  random 값을 O(1)로 뽑아내기 위해서는 리스트나 배열이 필수적이다. 해당 배열의 사이즈를 활용해서 랜덤 인덱스를 뽑고, 그 값에 한 번에 접근할 수 있으니 말이다. 난 map 과 배열의 조합으로 문제를 해결했다.  우선 배열의 끝을 가리키는 lastIdx 를 선언하고, 이를 -1로 초기화 한다. 다음은 ..
LV3 - 단속 카메라 (Java)
·
프로그래머스
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제의 핵심은 자동차의 진출 지점을 기준으로 오름차순 하는것이다. Case 1. [1]   | ---------------------- | [2]          | ----------------------|[3]                                  | --------------- | 눈으로 봤을 때 위 문제의 답은 2임을 알 수 있다. 우선 첫번째 차량을 위해 카메라가 한 대 필요하..
1283 - 단축키 지정 (Java)
·
백준
문제https://www.acmicpc.net/problem/1283 풀이우선 단축키의 등록 여부를 확인하기 위한 캐릭터 Set을 하나 준비한다. 이후 입력을 받으면 공백을 기준으로 String 을 분리하여 String 배열을 만든다. 우선 나뉜 단어의 첫번째 문자가 단축키가 되는지 확인하기 위해 문자열 반복문을 돌며 첫번째 단어가 Set에 추가되어있는지 확인한다. 이 때 대소문자를 구분하지 않는다고 했기에 uppercase 나 lowercase 로 통일하여 검사한다. 만약 첫단어가 추가되지 않은 단축키면 [ ] 괄호를 추가하여 해당 문자열을 업데이트 하고, 출력시켜준다. 첫단어가 추가되지 않았다면 2중 반복문을 돌면서 추가되지 않은 단축키를 찾으면 된다. 코드import java.util.*;impor..
18405 - 경쟁적 전염 (Java)
·
백준
문제https://www.acmicpc.net/problem/18405 풀이아주 조금의 응용이 들어간 bfs 문제였다. 우선 바이러스가 존재하는 위치를 queue에 저장했다. 단, 바이러스가 여러종류가 있기 때문에 map 을 활용해서 key로 바이러스 번호를 설정하고 그 값으로 해당 바이러스 위치를 가지고 있는 queue 를 꺼내올 수 있도록 설정했다. 이후에는 bfs 를 수행하는데, 이 때 전염이 1회 된다는 점을 주의해야한다. 가장 최근에 전염된 바이러스만 자신 주변으로 감염을 시키기 때문에 queue에는 최근 전염된 바이러스들의 위치만 존재해야하고, 다음에 queue를 넣을때도 마찬가지여야 한다. 숫자가 낮은 바이러스부터 전염되기 때문에 작은 숫자의 바이러스의 queue 부터 접근했고,해당 queu..
2239 - 스도쿠 (Java)
·
백준
문제https://www.acmicpc.net/problem/2239  풀이dfs 를 활용하여 푸는 문제이다. 배열의 앞쪽에서부터 작은값을 하나씩 대입해보고, 해당 값이 스도쿠 조건에 맞는지 검사하는 식으로 풀이가 가능하다. 정답이 여러개일경우 사전순으로 출력하라하였기에, 작은 값을 우선적으로 넣어주는 방식으로 풀이했다. 우선 값을 입력받고, 이 때 0의 개수를 체크했다. 추후에 0의 개수가 0개가 된다면 정답을 발견한것으로 판단하기 위한 용도이다. 이후 2중 for문으로 0 값이 있는 위치를 찾은다음, 해당 위치에 1부터 값을 넣어본다. 선정한 값이 가능한지 여부를 확인하고 (가로, 세로, 3*3 공간) 가능하다면 [1] 배열에 값을 세팅해주고,  [2] 0의 개수를 줄여주고 dfs로 다음 위치를 찾아..
22251 - 빌런 호석 (Java)
·
백준
문제https://www.acmicpc.net/problem/22251 풀이설명이 괜히 어렵게 되어있는거 같은데 대충 정리하면 n자리수의 층을 가진 엘레베이터가 있고 최대층과 현재층이 주어질 때, 현재층에서 다른 층으로 갈 수 있는 방법을 구하는 것이다. 이 때 반전이라는 개념을 사용하고, 그 횟수의 제한을 둔다. 우선 각 수를 배열로 나타내었다. 꺼져있는 부분은 0, 켜져있는 부분은 1로 나타냈고그 이후에는 숫자 변형시 필요 반전 개수를 map 에 저장해뒀다.Map> 형태로 구현하였으며cnt = map.get(1).get(3) 라고 했을때 이는 1에서 3으로 바꿀때 필요 반전 개수가 cnt 개라는 뜻이다. 이렇게 구현한 다음 현재층에서 다른 층으로 이동할 수 있는지를 알아봐야 하는데,최대층이 정해져있기..
Iterable, Iterator, ListIterator
·
자바
컬렉션 프레임워크에서, Iterator 를 사용해서 객체를 순회하고 값을 확인할 수 있다. 예시를 보자. Set set = new HashSet();set.add(1);set.add(2);set.add(3);Iterator iterator = set.iterator();while (iterator.hasNext()) { System.out.println(iterator.next());}// 결과는 1 2 3 순서대로 출력.  Iterator 는 뭐고, iterator() 메소드는 어떻게 호출되는걸까? Iterable 인터페이스 자바에서 Iterator 인터페이스는 컬렉션의 요소를 순차적으로 접근하는 방법을 제공하는 인터페이스이다. 아래 도식도를 보자.  컬렉션 인터페이스는 Iterable 인터페이스..
5397 - 키로커 (Java)
·
백준
문제https://www.acmicpc.net/problem/5397 풀이커서를 이동하고, 중간에 값을 삽입하고, 삭제하고 하는 등의 요건을 살펴보면 이 문제가 연결리스트 문제라는걸 알 수 있다. 구현은 단순하다, LinkedList와 ListIterator 를 선언하고 입력받은 값을 순회하면서 로직을 처리한다. "" 또한 마찬가지이다. "-" 가 나올경우에, 가장 앞을 가리키고 있는지 확인하고 (커서가 가장 앞) , 그게 아니라면 연결리스트에서 값을 삭제하고, iterator 를 한 칸 앞으로 이동시켜준다. 그 외에 일반 문자열은 현재 iterator 가 가리키고 있는 위치에 넣어주면 된다. 코드import java.util.*;import java.io.*;public class Main { p..
3055 - 탈출 (Java)
·
백준
문제https://www.acmicpc.net/problem/3055 풀이두 스텝으로 진행하면 된다. 1. 물을 먼저 퍼트린다. 2. 고슴도치가 이동할 수 있는 칸을 보고 이동처리를 한다. ※ 물 퍼트리기 우선 물 퍼트리는건, "*" 기준으로 상하좌우로 범위안에 들면서, 빈칸이어야 한다. (".")이 경우에, 임시 배열을 만들어서 새롭게 퍼지는 칸을 체크하고,마지막에 한번에 원본 배열에 물 값을 세팅해주면 된다. ※ 고슴도치 이동 처리 이거는 bfs 로 하면 되는데, 중요한게 있다.한 단계마다 고슴도치가 이동 할 수 있는 걸 모두 체크해야하기에,bfs 수행시 queue 에 들어가 있는, 같은 스텝의 데이터들을 모두 꺼내서 bfs 를 수행해야한다. 일반적으로는 bfs 는 queue에 있는값을 하나씩 꺼내면..