해싱6 [자바] 백준 18114 - 블랙 프라이데이 (boj java) 문제 : boj18114 1. 한 개만 선택해서 C가 되는 경우 (코드 19~22line 참고) 이 경우는 간단하다. N개를 입력받으면서 해당 값이 C인 경우를 찾으면 된다. O(N) 2. 두 개를 선택해서 C가 되는 경우 (코드 24~31line 참고) 이 경우도 어렵지 않다. 미리 N개를 입력받으면서 배열에도 기록해두고, HashSet에도 기록을 해둔다고 해보자. 이후 배열을 순회하면서 현재 보고 있는 값이 A라고 할 때, HashSet에 C-A가 존재하는지만 확인해주면 된다. 주의점은 A != C-A 여야 한다(동일한 물건을 두 개 고르면 안되고, 모든 물건은 무게가 다르므로 A와 C-A가 동일할 수 없다). O(2N) 3. 세 개를 선택해서 C가 되는 경우 (코드 32~41line 참고) 이 경우.. 2022. 7. 21. 백준 19585 자바 - 전설 (boj 19585 java) 문제 : boj19585 다른 의미로 전설이었다. 보통은 포기하고 넘어갔을텐데 이론상(?) 가능할 것 같아서 계속 하다보니 오기가 생겨서 끝까지 해보기로 했었다 ㅋㅋㅋ 풀고보니 자바한정으로 통과하기 어려운 문제였다. 시간초과난 로직으로 다른 언어론 통과가 되더라 ㅠ 시도한 내용들은 이하와 같다. 1. 이왜플(이게 왜 플래)을 외치며 모든쌍을 HashSet에 넣었다가 당연히 시간초과(이하 TLE). -> 색상과 닉네임이 둘 다 최대 4000개씩 이므로 모든 쌍을 만들면 O(4000^2) 이라고 대충 생각해서 해봤었다. 하지만 String이란 점을 간과했다. String + String이 결국 두 문자열 길이의 합 만큼 시간복잡도가 들어가므로, 실제론 O(4000^2 * (1000+1000)) 이다. Str.. 2022. 4. 15. 백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8. 백준 1501 자바 - 영어 읽기 (BOJ 1501 JAVA) 문제 : https://www.acmicpc.net/problem/1501 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1501.java 문제 자체는 해싱처리만 알면 풀 수 있는 문제인데, 설명이 너무 불명확하다 ㅡㅡ.. N개의 단어에 포함되지 않는 단어가 포함된 문장은 '0'을 출력해야한다.. 대체 문제 어디에 그 내용이 적혀있는데 ㅠ 뭐 굳이 억지로 찾아보자면 '각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.' 부분일 것 같긴하다만.. 1. 첫 문자와 끝 문자는 무조건 같아야 한다. 그 내부의 문자들은 소문자 a~z, 대문자 A~Z로 나눠서 카운팅하면 ababa, aabb.. 2021. 11. 12. [자바] 프로그래머스 - 위장 [코딩테스트 연습 Lv2] [ 문제 링크 ] [ 코드 링크 ] 문제 출처 : 프로그래머스 코딩 테스트 연습 각 의상 종류에 해당하는게 몇 가지씩인지만 알면 된다. 이 때 의상 이름의 경우 '같은 이름을 가진 의상은 존재하지 않습니다.' 에 따라 의미가 없으므로 버려도 된다. 즉, 예제1의 경우 의상 이름은 필요없고 아무튼 headgear 2 eyewear 1 라는 점만 알면 되며, 사실 종류명도 별로 상관없다. 동일한지만 hashing을 통해 확인할 수 있으면 된다. 그럼 계산은 어떻게 해야하냐면, 옷이 2종류라고 치면 2칸을 둬보자. 'ㅇㅇ' 첫번째 칸은 headgear를 입거나 입지 않을것이고, 2번째칸은 eyewear를 입거나 입지 않을 것이다. 그럼 경의의 수는 (2+1) * (1+1) 이 된다. 여기서 +1은 '입지 않는.. 2021. 11. 8. 백준 3409 자바 - 문자 방정식 (BOJ 3409 JAVA) 문제 : https://www.acmicpc.net/problem/3409 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03400/BOJ_3409.java 첫 다이아 티어 성공한 문제이다. 사실 골드나 플래도 제대로 못풀다보니 다이아급은 쳐다도 안봤었는데 얼마나 어려운지 볼려고 도전해봤다(보통 티어랑 알고리즘 분류는 끄고푸는데, 문제 검색을 실버, 골드, 플래 전체 체크하고 순서 랜덤으로 두고 검색해서 푸는 편임). 결과는 의외로 쉬웠다. 안쫄고 이제 다야도 한번 덤벼봐야겠다. 풀고보니 다른 분들은 DP(다이나믹 프로그래밍)으로 다들 분류를 설정해뒀던데 내 경우엔 그냥 dfs로 풀었다. 이 문제의 경우 문제만 놓고 보면 복잡해보일.. 2021. 10. 28. 이전 1 다음
