본문 바로가기

PS831

백준 3273 자바 - 두 수의 합 (BOJ 3273 JAVA) 문제 : https://www.acmicpc.net/problem/3273 보통 풀고보면 풀이 방법이 비슷비슷한 경우가 많은데, 아무래도 입력값 n이 10만개 밖에 안되다보니 재밌게도 풀이방법이 매우 다양한 문제이다. 일단, 단순히 2중 반복문으로 모든 쌍을 더해보면 O(N^2)이므로 시간초과다. 그럼 그 외에 시간 내에 가능한 풀이법에 대해 보자. 일반적으로 사람들이 많이 사용한 풀이 방법은 2가지 정도 있었다. 1. 정렬 후, 모든 값을 확인하며 x-a_i가 존재하는지 이분탐색으로 확인 : 정렬 O(NlogN) + N개에 대한 이분탐색 O(NlogN) 2. 정렬 후, 투 포인터 알고리즘으로 맨앞과 맨뒤에서 시작한 포인터를 움직이며 더해봄 : 정렬 O(NlogN) + 탐색 O(N) --- 내 경우엔 b.. 2021. 11. 13.
백준 9421 자바 - 소수상근수 (BOJ 9421 JAVA) 문제 : https://www.acmicpc.net/problem/9421 일단 이 문제를 풀기 위해 필요한 부분을 살펴보자. 1. 1000000이하의 모든 소수를 알 수 있어야 한다. -> 소수판정의 경우 간단히 에라토스테네스의 체를 사용해서 100만 이하의 모든 수에 대해 미리 소수를 구해두면 된다. 2. 상근수를 구할 수 있어야 한다. 이 때 '1'이 아예 안나오는 경우가 존재하므로 무한루프로 빠지지 않도록 하는 로직이 필요하다. -> 1이 나오거나, 이미 나왔던 수가 다시 나올 때 까지(순환) '각 자리수의 제곱의 합'을 구해준다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/09400/BOJ_9421.java import.. 2021. 11. 13.
[자바] 프로그래머스 - 순위 [코딩테스트 연습 Lv3] 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%203/%EC%88%9C%EC%9C%84.java 방향 그래프로 표현할 수 있는 문제의 경우 일단 그래프로 그려보면 답이 보이는 경우가 많다. 따라서 일단 무지성으로 그려봤다. 그럼 길찾기 처럼 거리를 한번 재보자! 정확힌 어디까지 갈 수 있는지만 알 수 있으면 된다. arr[i][j]를 대해 i번에서 j번까지의 거리라고 생각하고 표를 작성하면 아래와 같다. 그럼 이쯤에서 이 문제를 풀 수 있는 아이디어를 찾을 수 있다. 저기 '5'의 경우 4명한테 져서 순위가 확정됬.. 2021. 11. 12.
백준 2811 자바 - 상범이의 우울 (BOJ 2811 JAVA) 문제 : https://www.acmicpc.net/problem/2811 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02800/BOJ_2811.java 정리하자면 결국 다음과 같다. 1. 연속된 음수 날의 개수(우울 기간)를 센다. 2. 해당 우울 기간 * 2 배 이전부터 꽃을 준다. 3. 그 중 가장 우울 기간이 긴 날들을 살펴보면서, 3배 이전부터 선물을 줬을 때 가장 많은 꽃을 사줘야 하는 경우를 고르면 된다. 그럼 내가 푼 로직은 다음과 같다. 1. 배열로 값들을 입력받는다. 2. 연속된 음수값에 대해 해당 음수값이 시작한 위치에 '우울 기간(T)'을 기입한다. 다음의 경우를 보자. 15 -4 2 5 -1 -3 4 -5.. 2021. 11. 12.
백준 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.
백준 2405 자바 - 세 수, 두 M (BOJ 2405 JAVA) 문제 : https://www.acmicpc.net/problem/2405 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2405.java 1. a 2021. 11. 12.
백준 2437 자바 - 저울 (BOJ 2437 JAVA) 문제 : https://www.acmicpc.net/problem/2437 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2437.java 일단 brute force(완전탐색)으로는 단순히 생각해봐도 2^1000 이므로 절대 무리다. 처음엔 DP류 일 것 같았는데, 결론적으로 완전 아이디어 하나로 풀리는 문제였다. 내 경우엔 공책에 막 여러 케이스 무지성으로 써보면서 확인해보다가 얻어걸렸다. 일단 '양의 정수 무게 중 최솟값' 이라는 부분에서, 최소값을 찾자마자 출력해야 할꺼라 판단하여 정렬부터 하고 생각했다. 그리고 잘 보면 애초에 '2 3 4 5 6' 이렇게 있어도 1이 없으면 1은 못만든다. 그다음으로 '1 .. 2021. 11. 12.
백준 1010 자바 - 다리 놓기 (BOJ 1010 JAVA) 문제 : https://www.acmicpc.net/problem/1010 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1010.java N=2, M=3인 경우를 보자. 이런식으로 가능하다. 그럼 좌측은 생각하지 말고, 우측 중 선택된 녀석들만 확인해보자. 위와 같다. 즉 선은 생각하지 말고, 어차피 M개 중 N개만 선택하면 되는 문제이다. 이 때 다리가 서로 겹칠 수 있다고 한다면 nPm 이겠지만, 서로 겹칠 수 없다고 했으므로 nCm이 된다. 왜냐하면 겹칠 수 있다면 다음과 같이도 놓을 수 있기 때문이다. nCm = nPm / n! 을 구하면 된다. 예를들어 N = 3, M = 5 라면 nCm = 5*4*3 .. 2021. 11. 11.
백준 5637 자바 - 가장 긴 단어 (BOJ 5637 JAVA) 문제 : https://www.acmicpc.net/problem/5637 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/05600/BOJ_5637.java 생각상으로는 그냥 공백이나 줄바꿈('\n')을 기준으로 나누면 될 것 같지만, '단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만' 라는 기준에 따라 '마침표, 숫자, 심볼, 등등등...' 이라고 써져있는 것도 단어로 취급하면 안된다! 즉, '15-16 November 2012.' 라는 문장의 경우 여기서 단어는 '-', 'November'의 두가지 뿐이다. 따라서 단순히 자바의 StringTokenizer나 split으로 공백을 기준으로 나눠서는 처리할 수 없다. 방법이 두.. 2021. 11. 10.
백준 13717 자바 - 포켓몬 GO (BOJ 13717 JAVA) 문제 : https://www.acmicpc.net/problem/13717 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13717.java 문제에 제시된 '힌트'에서는 하나씩 확인하고 있다. 물론 그렇게 해도 워낙 입력값이 적어서 충분히 가능하지만, 약간만 수식을 넣으면 더 효율좋게 풀 수 있다. Weedle 12 42 위 입력에 대해 보자. k와 m을 입력 받고 m을 k로 나눈 몫으로 현재 몇개 살 수 있는지 알 수 있다. cnt = m/k = 42/12 = 3 (몫) 그리고 m은 m%k (나머지)로 변경한다. 그럼 m = m%k = 6이 된다. 그리고 살 수 있을 때 마다 2개를 되돌려받으므로, 몫*2를 m.. 2021. 11. 10.

티스토리툴바