xor eax, eax

중복을 허용하지 않는 조합을 만들줄 아는지에 대해 묻는 질문이었다. 원하는 개수에 도달했는지 확인하는 int depth 변수 하나와 dfs 내에서 for loop의 현재 인덱스를 저장하는 int index 변수 2가지를 선언하여 각각 관리하는 것이 조합을 만드는 방법이었으나 본인의 경우 index와 depth를 하나의 변수로 처리하려고 하여 주어진 케이스만 맞고 내부 테스트 케이스가 대부분 틀리는 결과가 나왔다. String을 Alphabetic으로 관리하고자 하면 TreeSet을 이용하기. String 내의 char를 Alphabetic으로 정렬하려면 char[] -> sort -> 변수 초기화. import java.util.*; class Solution { //course를 돌면서 number마다..

다리의 길이만큼 0 (큐에 들어갈 수 없는 어떤 값)을 큐에 추가하여 다리를 구현하고 매초마다 큐에서 remove와 add를 해주면서 weight와 index를 관리해준다. 해당 '초'에 다리에서 트럭이 내려가면(remove 값이 0이 아니면) 새로운 트럭이 올라올 수 있으므로 weight 측정을 가장 먼저 구현해야 한다. 해당 문제는 시간이라는 축을 값으로 구현한다는 아이디어만 생각하면 쉬운 문제이지만 이 아이디어를 얻기가 쉽지 않아 고려해야 될 것이 엄청 많게 느껴진다. import java.util.*; class Solution { public int solution(int bridge_length, int weight, int[] truck_weights) { int answer = 0; //다..

정규표현식의 편리함을 느끼게 된 해설이 있어서 작성한다. 1. skill_trees를 for loop 돌린다. 2. replaceAll("[^" + skill + "]", "")를 통해 String skill에 포함된 char가 아닌 모든 값을 제거한다. 여기서 사용된 정규표현식은 [^]인데 대괄호 내에 문자가 아닌 모든 것을 고르라는 표현식이며 replaceAll([^], "")을 통해 char를 제거한 것이다. 3. 문제의 조건이 처음의 스킬을 배워야 다음 스킬을 배울 수 있는 것이었으므로 어떤 스킬을 어떤 순서로 배우든간에 정답이 되려면 반드시 처음 스킬부터 순서대로 배워야한다. 즉 스킬트리가 "ABC"일때 정규화 이후의 검사해야할 스킬트리가 "BC"라면 indexOf를 하면 0이 아닌 1이 나올 ..

문제 자체는 아주 쉬운 난이도였지만 해당 문제를 풀면서 String 정렬에 대해 눈에 띌 정도로 차이를 발견하여 작성한다. 해당 문제는 마지막에 정답을 리턴할때 String의 오름차순으로 정렬해서 리턴해야 했는데 Map을 항상 정렬 상태로 유지시켜주는 TreeMap 자료구조를 사용하거나 HashMap을 이용하고 마지막에 문제 조건에 따라 정렬을 시행하고 리턴하는 방법이 있었다. TreeMap 이용 import java.util.*; class Solution { //Map public int[] solution(int[] fees, String[] records) { Map map = new TreeMap(); Map isOut = new HashMap(); ... int[] answer = new in..

DFS + Pruning을 이용하여 푸는 백트래킹 문제였다. 2차원 배열을 다루는 문제이므로 2차원 배열을 선언하여 x,y 값에 따라 퀸을 놓는 플래그를 세워서 푸는 방법도 있겠지만 아래의 풀이 방법은 두 개의 축 중 하나를 고정시켜서 마치 1D의 배열을 푸는 것처럼 이용하는 방식이다. 여기서 값을 저장할 1D 배열은 index로 row 값을 갖고 index의 value로 col을 갖는다. 풀이의 흐름은 다음과 같다. 1. 가능한 한 많은 변수를 전역변수화시킨다. 해당 문제에서는 파라미터 n, return 할 answer, row와 col 값을 저장하는 1D 배열을 선언한다. 2. DFS로 row를 아규먼트로 넘긴다. (0, 0)부터 시작할 것이므로 0을 넘김. 3. DFS에서는 언제나 탈출 조건과 반복..

이 문제의 핵심은 방향 지정과 값을 별개로 보는 것이다. 방향과 값은 전혀 다른 속성으로 방향도 바꿔주고 값도 바꿔주는 2가지 작업을 일련적으로 해야하는 것이다. 1. 이전 값을 담을 노드를 하나 선언한다. Linked List에서 마지막 노드는 null을 가르키기 때문에 이 새로운 노드도 null로 선언한다. 2. head가 존재하는 동안에 라는 제한 조건을 걸어준다. 1번에서 말했듯이 마지막 노드는 null을 가르키기 때문에 null이라면 마지막에 도달했다는 의미를 가진다. 2-1. 마지막 head에서도 작업을 해야 reverse가 되기 때문에 head.next가 아닌 head가 null인 경우를 체크한다. 방향 3. 현재 노드의 다음 노드를 저장한 후에 현재 노드가 1번 노드를 바라보게 한다. 3-..

비트마스크를 이용하는 방법은 비트로 마스킹을 한다는 단어 자체의 의미대로 기존의 값을 이용하지 않고 비트로 바뀐 0과 1, 그리고 그 비트들의 위치만으로 값을 결정하는 방법이다. 비트마스크는 값, 위치 2가지 값으로 모든 경우의 수를 유니크하게 나타낼 수 있으므로 순열이나 조합을 생성할 때 사용할 수 있다. 이 문제에서도 순서가 상관없는 모든 조합을 만들어야 하기 때문에 비트마스크를 이용하여 풀이한다. 비트마스크를 이해하는데 핵심은 마스크가 어떠한 값을 나타내는 것이 아니라 마스크를 값에 씌워 보이는 값만 체크한다는 것이다. {"사과", "복숭아", "바나나"}가 있을때 이 배열이 111이 되는 것이 아닌 010과 같은 비트마스크를 씌워 "복숭아"만 추출해내는 것이다. 비트마스크를 이용한 문제 풀이의 흐..

BFS, DFS 문제를 풀때는 다음과 같은 순서로 사고를 하도록 하자. 1. 재귀적인 특징을 가지거나 백트래킹을 이용해야 하는 완전탐색의 문제를 풀어야 할 때는 DFS e.g. 순열 조합 깊이를 이용한 문제를 풀어야 할 때는 BFS e.g. 최단 거리 구하기 1-1. 최단 거리를 구하는 문제에서 DFS를 사용하게 되면 매 노드를 방문 표시를 하면서 경우의 수를 구해나가기 때문에 다시 무를 방법이 없다. (백트래킹을 통해 최적의 해를 구하지 않는다면) 매 순간 최선의 선택을 하는 BFS가 최단 거리를 구할 때 가장 적합하다. 2. 주어지는 파라미터를 전역 변수로 넘긴다. 필수는 아니지만 코드가 더 간결해진다. 2-1. 2차원 배열의 경우 y,x 좌표를 받는 노드 클래스를 생성한다. 이 역시 필수는 아니지만..

전체적으로 구현력을 보는 간단한 문제였다. 이 문제의 가장 핵심은 중복 요소를 어떻게 다루느냐였는데 중복은 허용하되 중복에 대한 카운트가 잘 되어야 하므로 Map 구조를 사용했고 전체 합집합에는 교집합에 대한 카운트가 2번 되어있으므로 교집합을 한 번 제거해주는 과정이 필수이다. 이 중복 체크만 잘 해준다면 쉽게 구현할 수 있는 문제라고 생각한다. 2022-08-15 풀이 추가 import java.util.*; import java.util.regex.Pattern; class Solution { Map map1 = new HashMap(); Map map2 = new HashMap(); int inter, union; void helper(String str, Map map) { var length ..

문제 자체는 매우 간단한 편이지만 DFS를 주어진 메서드 자체를 recursion하는 경우를 기록에 남겨둔다. dfs는 콜스택이거나 스택구조를 이용하는 것이므로 dfs 메서드를 굳이 만들지 않고 기존의 메서드를 recursive하게 호출해서 실행하여도 된다. class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode temp = root.left; root.left = root.right; root.right = temp; invertTree(root.left); invertTree(root.right); return root; } }