본문 바로가기

백준756

자바 6137 자바 - 문자열 생성 (BOJ 6137 JAVA) 문제 : https://www.acmicpc.net/problem/6137 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/06100/BOJ_6137.java 문제에 제시된 '예제 입력 1'을 기준으로 그림을 그려보면 다음과 같다. 위와 같이 문자열이 있고, head가 앞쪽 tail이 뒤쪽을 가르키는 포인터라 생각하면 된다. 그리고 head는 우측으로, tail은 좌측으로 진행하면서 사전순으로 더 작은 character를 선택하면 된다. (A 2021. 10. 29.
백준 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.
백준 1575 자바 - 졸업 (BOJ 1575 JAVA) 문제 : https://www.acmicpc.net/problem/1575 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1575.java 생각해야 할 부분이 많은 까다로운 문제였다. 그래도 1시간정도 걸렸으니 그저께 8시간 걸려 풀었던 문제 보다는 훨씬 나았다. 플래도 가끔씩 풀어지긴 하는데, 아직 내 실력으론 풀어도 보통 1시간 이상은 기본으로 걸리는 것 같다. 나중에 한 번 틀리고 나서 본건데, 6개월 전부터 '맞았습니다'가 하나도 없는 문제였다. 미리 채점 현황을 봤다면 아예 시도를 안해봤을수도 있을듯 ㄷㄷ 처음에 틀리고 나서는 나도 저 중에 하나가 되겠거니 했는데, 자기 전에 맞아서 꿀잠 잘 것 같다. 0.. 2021. 10. 26.
백준 16499 자바 - 동일한 단어 그룹화하기 (BOJ 16499 JAVA) 문제 : https://www.acmicpc.net/problem/16499 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16400/BOJ_16499.java 만약 N개의 문자열에 대해 알파벳 순서까지 모두 같아야 한다고 하자. 그럼 단순히 HashSet에 입력받은 단어를 넣어보면 알아서 중복값이 제거되니, 해시셋의 크기가 답이 된다. 그럼 순서만 달라야 하는 경우는 어떻게 해야 할까? 여기서 서로의 동일성을 판별할 수 있는 기준은, N개의 단어에 대해 각각 '알파벳 소문자가 몇 번씩 나왔는지' 이다. 알파벳 소문자는 총 26개 이므로, 26칸짜리 배열을 만들어 두고, 입력 받은 각 문자열에 대해 각 character를 보면서 각.. 2021. 10. 26.
백준 14881 자바 - 물통 문제 (BOJ 14881 JAVA) 문제 : https://www.acmicpc.net/problem/14881 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14800/BOJ_14881.java 처음엔 별 생각없이 brute force 정도로 생각했는데, 시간복잡도가 아닌 것 같아 다른 방법을 찾아봤다. 결론은 최대공약수 문제이다. 일단 되는 경우와 안되는 경우에 대해 생각해보자. 1. 일단 c가 a와 b 둘 모두보다 크다면 아예 불가능하다. (코드의 max>=c) 2. c가 a나 b와 동일하다면 당연히 가능하다. (코드의 a==c || b==c) 3. 다음으로 a,b의 최대공약수가 c의 공약수라면 가능하다. (코드의 c%gcd==0) 4. 마지막으로 a와 b가 서.. 2021. 10. 25.
백준 23046 자바 - 큰 수 뒤집기 (BOJ 23046 JAVA) 문제 : https://www.acmicpc.net/problem/23046 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23000/BOJ_23046.java ... 8시간 걸렸다. 주말 다 날라갔다. 처음엔 reverse에 대해 boolean으로만 처리하고 deque에 앞뒤로 boolean값에 따라 앞이나 뒤에 넣으면서 풀라는 쉬운 문제인줄 알았다. 그리고 '-' 나오기 전까지는 사실 실제로 s를 x에 더하지 않아도 되니깐, '-' 나오면 boolean값 반전시키면서 deque에 넣고, 그동안 쌓인거 저장하는 식으로 구성했다. 거기서도 시간 줄이고 충분히 가능할꺼라 생각했다. 그런데 계속 시간초과가 나길래, 거기에 deque도 .. 2021. 10. 24.
백준 9291 자바 - 스도쿠 채점 (BOJ 9291 JAVA) 문제 : https://www.acmicpc.net/problem/9291 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/09200/BOJ_9291.java 일단 실버 이상 티어는 전부 블로그에 글을 쓸까 했었는데, 문제마다 해설 필요한것만 올리던지 해야겠다. 이 문제의 경우 그냥 정확히 제시된 대로 구현만 잘 하면 된다. 실버인 이유는 어쨌든 구현이 좀 복잡할 수 있기 때문일 것 같다. 1. 각 행에 1-9가 한 번씩 등장하는지 확인 2. 각 열에 1-9가 한 번씩 등장하는지 확인 3. 각 작은 3x3 정사각형에 1-9가 한 번씩 등장하는지 확인 이렇게 3개를 하면 된다. 코드의 경우 'chkRowAndCol()'에서 1과 2를 .. 2021. 10. 24.
백준 20438 자바 - 출석체크 (BOJ 20438 JAVA) 문제 : https://www.acmicpc.net/problem/20438 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/20400/BOJ_20438.java 1. 일단 잠자는 사람들을 생각하지 않고, 출석 코드를 보내는 부분만 생각해보자. n명을 입력받고, q를 입력받아 단순히 자신과 그 배수들은 출석코드를 받았다고 할 수 있다. 이 부분까진 간단하게 구현 가능할 것이다. 2. 다음으로 잠자는 사람에 대해 어떻게 처리해야할지 확인해보자. 일단 q명 중 출석코드를 받은게 자는사람에 포함되어 있다면 그 배수한테 출석코드를 보낼 수 없다. 따라서 이 경우 해당 출석 코드는 무시된다. (23line) 다음으로, 출석 코드를 받은 사람은.. 2021. 10. 23.
백준 21941 자바 - 문자열 제거 (틀린 풀이 - 새로 작성한 풀이 링크 포함) -- 이하 틀린 풀이이다. -- 새로 작성한 풀이 : 링크 문제 : https://www.acmicpc.net/problem/21941 풀고보니 DP로만 분류되있어서(알고리즘 분류 켜놓으면 너무 치트라 꺼놨음) 약간 의아했다. 내 경우엔 그리디로 풀었다. 물론 DP를 더 간단하게 생각하는 분들이 많겠지 ㅠ 1. 일단 a의 길이가 x보다 크거나 같다면 버린다. 예제 입력2의 경우를 처리하기 위해서이다. 2. 그다음 가장 점수를 많이 주는 녀석부터 하나씩 빼낼껀데, 단순히 'x'만 판단하면 안된다. 왜냐면 다음과 같은 경우가 있을 수 있다. abcdefg 10 a 9 둘 다 '1'에서 걸러지지 않지만, 누가봐도 'a 9'를 쓰는게 이득임을 알 수 있다. 따라서 [ x / a의길이 ] 가 높은 순서대로 먼저 .. 2021. 10. 23.
백준 1294 자바 - 문자열 장식 (BOJ 1294 JAVA) 문제 : https://www.acmicpc.net/problem/1294 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1294.java 쉬운줄 알고 덤볐는데 생각보다 어려웠지만, 결국 다 풀고보니 또 그렇게 어렵진 않았던 문제. 1. 기본 로직은 어렵지 않게 생각해볼 수 있다. 3 ABC BCD CDE 만약 입력이 위와 같다고 하자. 각 문자열의 순서를 해치지 않으면서 전체 문자열이 사전순으로 앞서게 하려면 결국 각 문자열에 pointer를 뒀다고 생각하고, 해당 문자열의 pointer가 가르키는 문자 중 가장 작은걸 순서대로 빼내면 된다. 즉, 위의 경우 다음과 같이 진행된다. 1.1 시작은 아래와 같다. 화.. 2021. 10. 23.

티스토리툴바