문제풀이
-
[프로그래머스]표 편집 - JAVA문제풀이/프로그래머스 2021. 7. 10. 18:26
** 풀이가 추가되었습니다. 추가된 풀이가 정확한 풀이입니다. ** [프로그래머스]표 편집 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 풀이 🪑 올해 카카오 인턴십 코딩테스트 문제이다. StringBuilder때문에 한참 헤메였던 문제.. StringBuilder 사용을 잘 안해보다보니 append외엔 함수를 몰랐었다. insert라는 함수가 있다는 것을 알게 되기까지 너무 오래걸렸당..ㅜ ** 추가 ** 위의 방식으로 StringBuilder의 inser..
-
[백준]20010: 악덕 영주 혜유 - JAVA문제풀이/백준 2021. 7. 7. 17:08
[백준]20010: 악덕 영주 혜유 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 풀이 🪑 MST를 구하는 활용문제이다. 문제의 조건들을 정리해보자. 마을간 교역로는 양방향이다. 모든 마을은 연결되어있다. 구하는 값은 MST 비용과 MST 내에서 가장 먼 노드간의 거리이다. 🔧 이제 문제 풀이 과정을 생각해 보자. 마을 간 교역로 정보를 입력 받은 후 MST를 구한다. MST를 저장해 둔 다음 MST를 내에서 DFS로 가장 먼 노드간의 거리를 구한다. 가장 먼 노드간의 거리를 구하기 위해선 먼저, 한 정점에..
-
[백준]13392: 구간 나누기2 - JAVA문제풀이/백준 2021. 7. 6. 15:56
[백준]13392: 구간 나누기2 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 풀이 🪑 최댓값의 최솟값! 을 구하는 문제. 이런 문제는 "이분 탐색" 으로 풀 수 있는 문제들이다. (최단거리는 BFS를 떠올리듯..) 먼저 문제의 조건들을 정리해보자. N개의 수를 M개 이하의 구간으로 나눠 구간 점수의 최대 값의 최소값을 구한다. 구간 점수는 구간에 속한 수의 최대값 에서 최소값을 뺀 값이다. N개의 수를 나눌 때는 연속된 순서대로 나눠지면, 각 구간은 한개 이상의 수를 ..
-
[백준]1042: 거짓말 - JAVA문제풀이/백준 2021. 7. 5. 15:23
[백준]1042: 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 🪑 문제를 따라 조건들을 차례차례 정리해 보았다. 지민 -> 진실 OR 과장(되도록 과장 BUT 거짓말 들키기 싫어함) 진실 아는 사람 존재 -> 과장 할 수 없음. 진실을 한 번 이라도 들은 사람은 진실을 아는 사람이다. 🔧 위의 조건들을 토대로 어떻게 풀지 풀이 순서를 적어보았다. 진실을 아는 사람들의 정보를 모은다. 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원..
-
[프로그래머스]로또의 최고 순위와 최저 순위 - JAVA문제풀이/프로그래머스 2021. 7. 4. 14:55
[프로그래머스]로또의 최고 순위와 최저 순위 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이 🪑 구현, 시뮬레이션 유형의 문제이다. 🔧 로또 번호가 맞는지 확인해 주기 위해 반복문을 2중으로 사용하여 확인해 주었다. 확인하면서 '0'으로 표시된 부분의 개수도 함께 count해 주었다. 🔧 최고 순위는 최대로 로또 번호를 맞췄을때 이므로 현재 맞는 로또 번호의 개수 + '0'의 개수로 계산해 주었다. 🔧 순위를 지정하는 부분은 배열을 사용하였다. 인덱스를 로또..
-
[백준]14890: 경사로 - JAVA문제풀이/백준 2021. 7. 3. 15:00
[백준]14890: 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 🪑 조건에 따라 문제를 잘 읽고 풀어야 하는 구현 문제였다. 확인해 주어야 할 방향은 총 2가지 방향이므로 (열, 행) 열을 확인하는 함수, 행을 확인하는 함수 두개로 나누어 풀어주었다. 🔎 확인할때는 한 방향으로 확인하며 현재 계단의 높이와 다음 계단의 높이차를 확인해 주었다. 계단의 높이차가 1을 초과하면 문제의 조건에 나와있는 "계단의 높이차는 1이어야 한다"를 만족하지 못하므로 바로 false를 반환하도록 하였다. 계단의 높이차가 1이더라도 다음 ..
-
[백준]10711: 모래성 - JAVA문제풀이/백준 2021. 7. 2. 15:56
[백준]10711: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 풀이 이 문제는! 직관적인 방법으로 생각해서 풀면 시간초과가 발생하는 문제이다. 우선, 대부분 첫번째로 떠오른 풀이 방법은 다음과 같을 것이다. 모든 노드의 탐색을 반복하며 모래성이 있는 노드 주변의 8방향 노드값을 확인하여 무너지는지, 무너지지 않는지 확인한다. 위의 방법으로 푼다면 테스트 코드는 통과되겠지만 시간 복잡도 측면에서 효율적이지 못하다. 매번 모든 노드를 탐색하는 방법 보다 더 효율적인 탐색 방..
-
[백준]16947: 서울 지하철 2호선 - JAVA문제풀이/백준 2021. 6. 23. 11:40
[백준]16947: 서울 지하철 2호선 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 그래프의 탐색과 관련된 문제였다. 탐색 관련한 알고리즘을 활용하여 문제를 풀었다. 🤗 우선 풀이 과정을 다음과 같은 순서로 나눠 구현해 주었다. 싸이클이 발생하는 구간을 체크해준다. 탐색을 통해 모든 노드에서 싸이클이 발생하는 노드까지의 거리를 계산해 준다. 하나씩 차근차근 살펴보장. 🔹 싸이클이 발생하는 구간을 체크해준다. 싸이클은 언제 발생할까? 🤔 👉 그래프의 특성을 알고 있다면 쉽게 생..