본문 바로가기

분류 전체보기361

[448]Find All Numbers Disappeared in an Array leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ 다음 출처를 참고하여 해결하였습니다. ergate.tistory.com/entry/LeetCode-448-Find-All-Numbers-Disappeared-in-an-Array 중요한 성질 두 가지를 기억하면 됩니다. N: 배열의 길이 1. 배열 내의 값이 [0,N-1] 또는 [1,N] 범위 내로 주어진다면 이를 인덱스로 활용할 가능성이 높습니다. 2. 중복유무와 관계없이 한 번이라도 등장한 값과 등장하지 않은 값의 차이는 인덱스상에 표시할 수 있습니다. 위 1, 2번 성질을 활용하여 한 번이라도 등장한 숫자는 number는 arr[number-1] 숫자를 음수로 바꿔줍니다. 중복 방문하지.. 2020. 9. 18.
[169]Majority Element leetcode.com/problems/majority-element/ 숫자가 나오는 갯수를 HashMap으로 관리한 후 절반이상 등장한 숫자를 리턴해주면 됩니다. HashMap map = new HashMap(); public int majorityElement(int[] nums) { for (int i = 0; i (nu.. 2020. 9. 18.
[136]SingleNumber leetcode.com/problems/single-number/ 두 가지 이유로 XOR을 통해 해결할 수 있습니다. 1. XOR은 결합법칙과, 교환법칙이 성립합니다. 2. 자기 자신과의 XOR 결과는 0 입니다. 10^10 = 0, A^A = 0 주어진 리스트의 1개를 제외하고는 모두 2개라는 성질을 이용하면 ABCDEDCBA 위 예시 숫자를 교환법칙을 사용해서 두 쌍씩 괄호로 묶어줍니다. (AA)(BB)(CC)(DD)E 여기에 XOR을 하게 되면 결국 0 ^ E 만 남게 되어 하나짜리 E만 남는 형태입니다. public int singleNumber(int[] nums) { int xorResult = 0; for (int i = 0; i < nums.length; ++i) { xorResult = .. 2020. 9. 18.
[BOJ]19236번: 청소년 상어 www.acmicpc.net/problem/19236 시뮬레이션 문제입니다. 어떻게 움직여야하는 지는 문제 꼼꼼히 읽어보면 아실테니 그것보다는 푸시면서 신경써야할 예외케이스에 대해 말하겠습니다. 1. DFS로 푸시든 BFS로 푸시든 매 상태의 2차원 그래프는 서로 분리되어 있어야 합니다. 그냥 매 깊이 갈 때 마다 copy를 하시든, 아니면 가공하고 다시 원상복귀를 하시든 매 상태는 구분되어야 합니다. 즉 탐색하고 빠져나오면 다시 원래 상태에서 다음 탐색을 시작해야된다는 의미입니다. 이게 머릿속에서 꼬이시면 시뮬레이션은 답이 없습니다. 2. 물고기들이 이동하는 시점을 처리할 때 각 물고기는 한 번만 이동해야 합니다. 저 같은 경우는 그냥 2차원 배열 다 뒤지면서 숫자 작은 것부터 이동시켰는데요. //BA.. 2020. 9. 17.

티스토리툴바