본문 바로가기

Algorithm65

[프로그래머스] 보석 쇼핑 자바 문제 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 풀이 ✔️ 알고리즘 1. Set 자료구조를 이용하여 보석의 종류 개수를 구함. 2. gems배열을 편하게 카운팅 하기 위하여 HashMap으로 보석이름과 인덱스를 매칭해줌 3. gems배열을 순회하면서 모든 종류의 보석을 담았을 경우 인덱스 갱신해줌 - sidx, eidx 둘 다 처음으로 지정한 후 모든 보석의 종류를 담을 때까지 eidx를 증가한다. - 이 때, 증가하면서 나온 보석들을 종류별로 카운팅해주는데 sidx를 다음 값으로 옮겼을 때, 같은 보석일 경우 바로 갱신을 해주고, 다른 보석일 경.. 2022. 4. 25.
[백준] 2461번 대표 선수 자바 문제 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 문제 풀이 학급 대표선수 간 최대 최소 차가 최소가 되기위해서는 최대한 비슷한 값끼리 묶여있어야 하므로 모든 학생들을 학급 표시만 해둔 채로 정렬시켰다. 그리고 두 개의 인덱스 변수로 첫번째 선수를 마킹해두고, 뒤로 가면서 모든 학급이 다 찰때까지 두번 째 인덱스를 증가시켜 나갔다. 그 때의 최솟값을 갱신하면서 첫번째 인덱스를 증가하면서 나갔는데 시간초과가 떴다. 이를 개선하기 위해서 한 학급에서 나온 대표선수를 표시해두기 위해 boolea.. 2022. 4. 25.
[백준] 20365번 블로그2 자바 문제 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 문제 풀이 어차피 연속된 색깔은 한 번에 가져와서 처리할 수 있으므로 연속된 색깔을 묶어줘야 한다. 'BBRBRBBR' → 'BRBRBR' 로 생각해서 처리해도 된다는 말이다. 처음에 char배열을 이용해서 첫 값을 넣고 그 뒤 값부터 반복을 돌면서 문자가 다를경우에만 체크해서 배열에 넣어줬다. 근데 생각해보니 어차피 연속되지 않으니까 무조건 brbr... 또는 rbrb...이런식으로 갈텐데 굳이 문자를 다시 압축해서 가지고 있을 필요가 없었음.. 따라서 .. 2022. 4. 20.
[백준] 17472번 다리 만들기2 자바 문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 풀이 BFS+DFS+크루스칼 이렇게 세개를 각각 적용해서 풀었다. 문제는...더럽지만...그냥 저 3개의 알고리즘 연습하는 데는 나쁘지 않은 것 같다... 1. 각 섬들 네이밍 해주기 : 다리를 만드려면 섬이 다른 걸 알아야 하기 때문 → DFS이용 2. 각 섬을 이을 수 있는 다리의 최소비용 구하기 → BFS이용 : 이 때 다리는 한 방향으로만 나아갈 수 있기 때문에 상하좌우의 for문을 먼저 쓰고 각 방향에 대해 bfs적용 3... 2022. 4. 20.
[백준] 9935번 문자열 폭발 자바 문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 풀이 이 문제를 풀면서 자바의 String 관련 내장함수를 찾아보았는데, 생각보다 많은 함수들이 있었고 이걸 이용해서 문자열을 하나하나 탐색하고 갱신하면서 풀었다. - indexOf( ) : 문자열에서 특정 문자가 시작되는 인덱스 리턴 - substring(시작idx, 끝idx-1) : 문자열 중 특정 부분을 뽑아내 리턴 - startWith( ) : 문자열이 지정한 문자열로 시작하는지(인자값) - replaceAll( ) : 문자열 중.. 2022. 4. 20.
[백준] 23742번 Player-based Team Distribution 자바 문제 23742번: Player-based Team Distribution 플레이어 $N$명이 $1$개 이상의 팀으로 나누어 게임을 진행하려 한다. 플레이어는 각각 정확히 한 팀에 속해야 한다. $i$번째 플레이어는 같은 팀에 속한 인원 수와 $a_i$를 곱한 것만큼의 점수를 www.acmicpc.net 문제 풀이 일단, 양수팀은 인원이 많으면 많을 수록 그 배수로 늘어나므로 양수팀끼리 묶는다. 또, 팀은 1명 이상이기만 하면 되므로 음수는 각각 다 1인 팀으로 묶는다. 양수가 많이 큰 수 이면 음수를 데려와서 그 인원수를 곱했을 경우 기존 점수합보다 더 커질수도 있으므로 음수팀에서 음수값이 더 작은 플레이어를 데려와 양수팀과 합쳐서 점수합을 갱신해나간다. 이때, 음수는 -값이 작은 것부터 넘긴다. 왜냐.. 2022. 4. 18.

티스토리툴바