본문 바로가기

알고리즘/문제 풀이14

[프로그래머스] 전화번호 목록(JAVA) / 해시 Level2 https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 컬렉션 함수를 잘 이용하면 간단히 풀릴 문제였는데 적절한 사용을 못하고 슬라이딩 윈도우로 풀다가 인덱스바운더리 에러만 맛봤다... 가슴이 아파서 정리해둔다 내가 참 간과한 것이 있는데, String 배열도 배열이라 Arrays.sort() 가 사용가능 하다는 점, 그리고 사전순서대로 정렬이 된다는 점이다. 대체 왜 막연히 길이가 짧은 순서대로 정렬이 된다고 생각했던 걸까... 아래와 같이 시험해보.. 2023. 3. 17.
[프로그래머스] 위장(JAVA) / 해시 Level2 https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 경우의 수 성질을 이용하면 간단하게 해결될 문제였는데... 삽질을 엄청 했다. 쉽게 풀 수 있는 문제를 순열까지 구현해서 돌려가며 코딩했는데... 케이스 하나에서 시간초과가 나서 실패했다. 틀린 코드 5개 종류의 옷이 입력으로 주어졌다고 했을 때 1개 종류만 입을 경우, 2개 종류만 입을 경우 ... 등을 구하고 각 경우마다 해당 종류의 옷이 몇개 인지 확인해서 경우의 수를 구했다. 시간을 .. 2023. 3. 17.
[프로그래머스] 합승 택시 요금(JAVA), 다익스트라, 2021 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 school.programmers.co.kr 풀이 다익스트라를 이용해 최단거리를 구하는 문제다. 주의할.. 2023. 2. 27.
[프로그래머스] 파괴되지 않은 건물(JAVA), 2차원 배열 누적합, 2022 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 누적합을 이용해서 시간복잡도를 줄이는 문제는 처음봤다... 정확도 테스트케이스는 간단히 브루트포스로 풀면 맞출 수 있으나 그 경우 O(N*M*K) 가 되어 효율성 테스트케이스가 모두 시간초과가 난다. 효율성 테스트를 통과시키기 위해선 누적합 개념을 알고 있어야 한다. (효율성 정답률이 2%도 안되는 걸 보아 개념을 알았어도 이용할 생각을 하기는 쉽지 않아 보인다..^^) 누적합 arr = [3, .. 2023. 2. 23.
[백준] 6087 : 레이저 통신(JAVA), 다익스트라 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 방향을 회전시킨다기에 시뮬레이션 문제인가 싶어서 삽질을 했다. 결론적으로 C에서 C까지 최소 개수의 거울(최소비용)을 사용하는 경로를 찾는 다익스트라 문제였다. 기본적으로 다익스트라를 적용시키되, 주의해야할 점은 (x,y) 지점에 오기 까지 사용한 비용(거울의 수)가 같더라도 직전 방향에 따라 다음 지점에서의 비용이 달라지기 때문에 같은 비용까지는 우선순위 큐에 넣어주어야 한다는 점이다... 2023. 1. 25.
[백준] 2749 : 피보나치의 수 3 (JAVA) / 피보나치 수 구하는 방법, 재귀, 메모이제이션, 행렬) https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 전형적인 피보나치 문제인데, 골2길래 뭔가 싶어 풀어봤다. 이 문제의 주의할 점을 몇가지 뽑자면 입력값 n의 크기가 10^18 로 매우 크다. int 형이 아닌 long 으로 입력을 받아야한다. n번째 피보나치 수를 구하기에, n이 매우 크므로 재귀방식이 아닌 행렬을 사용해풀어야 하지만 이 또한 n이 크기 때문에 O(n) 으로는 해결하기 애매하다. 1,000,000 으로 나눈 나머지를 출력한다는 부분이 힌트. 결론적으로 피사노 주기(Pisano Period)를 이용하여 풀어야하.. 2023. 1. 19.

티스토리툴바