Java/코딩테스트
-
프로그래머스 DP 등굣길 JavaJava/코딩테스트 2023. 4. 27. 01:14
계속 몇 가지 테스트 케이스만 틀렸었어서 열받아서 고치고 질문 확인하고 구글링하다가 푼 문제... https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 기본적으로 맨 위 가로줄, 맨 왼쪽 세로줄을 다 1로 채워주고 웅덩이를 -1 처리해서 계산했었다. - 한 좌표의 값을 구하는 것은 해당좌표 왼쪽과 위쪽을 기준으로 합쳐서 계산하는데, 왼쪽과 위 모두 웅덩이면 못가는 걸로 처리.. - 한쪽만 웅덩이면 Math.max로 그대로 값을 가져왔었다. -> ..
-
프로그래머스 Hash 문제풀이 - JavaJava/코딩테스트 2023. 4. 26. 22:45
🍡 Hash - 임의의 데이터를 고정된 크기의 대표값으로 변환해서 저장하는 것, 데이터를 해시함수(어떤 연산) 통해 해시값을 얻어냄. - 해시함수를 어떻게 정의하는지에 따라 다른 데이터여도 하나의 해시값이 될 수도 있음(해시 충돌) - 객체는 기본적으로 할당된 주소값을 이용하여 해시 값 생성 - 해시 테이블 : 해시 값을 사용하여 이에 대응하는 원본 데이터를 찾을 수 있게 해주는 자료구조로, 역함수는 존재하지 않는다 (해시는 단방향 변환, 충돌을 허용하기 때문에 역함수 존재 x) - 해시 값으로 원본 데이터에 바로 접근이 가능, 따라서 빠른 시간에 데이터 검색, 삽입, 삭제가 가능하다. 🍡 HashSet - 중복을 허용하지 않는 집합 - 데이터 순서 없음 - add : 데이터 삽입 - contains :..
-
프로그래머스 Stack / Queue 문제풀이 - JavaJava/코딩테스트 2023. 4. 21. 03:40
🍓 Stack - 후입선출 특징을 가진 자료구조 - add, pop, peek [ 괄호 회전하기 ] https://school.programmers.co.kr/learn/courses/30/lessons/76502 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [ 로직 ] - i개의 칸 만큼 원소 이동 시킨 후 괄호 가능 여부 개수를 센다. isPair함수 따로 빼서 구현 - 시작 지점을 (index + i) % chars.length 로 주면 index칸만큼 뒤에서 시작하는 효과를 낼 수 있음 - 문자열 읽으면서 여는 괄호가 나오면 스택에 닫는 괄호 형..
-
백준 23290Java/코딩테스트 2023. 4. 8. 23:25
결국 3차원 배열로 풀어야 했던 문제.. 🐟 같은 방향 보고 있는 물고기 2마리 이상이 같은 칸에 존재할 수도 있다. 이걸 되게 고민했는데 3차원 배열 쓰는게 더 편한것 같다... 🐟그리고 계속 실수했던 부분이 냄새를 삭제하는거... 상어가 움직이기 전에 각 smell[][] 감소시켜줘야한다. 상어가 움직이고 나서 감소해주면 갱신된 상태에서 감소시키는거라 계속 답이 틀림 진짜 너무 복잡했다... ㅎ 아직 코딩 멀었다~.~... 🐟 변수 temp는 방향까지 저장한 것 fishAmountMap은 단순 해당 좌표에 몇마리 있는지만 저장한 것 (상어가 먹을 때는 방향상관없이 같은 칸에 있는거 다먹으니까) static int m, s; // 물고기의 8방향 public static int[] fishX= {0, ..
-
백준 17142Java/코딩테스트 2023. 4. 8. 22:30
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 후........이거 정말 15번은 제출한 것 같다. 말이 15번이지 진짜 몇시간 내내 계속 붙들고 있었음. 계속 시간초과가 떠서 뭐가 문젠지 계속 살폈었는데 허무하게도 내가 조합 구하는 함수 재귀호출 하는 부분에서 변수를 잘못 넣었었다. 답은 제대로 나오지만 왜 시간초과가 났는지 모르겠어서 다른 분 코드보고 읽고 하다가 겨우 찾았다.... 내 코드에선 너무나 까막눈이 되는 것.. BFS쪽 잘못 짠 거 같..
-
백준 15686Java/코딩테스트 2023. 4. 6. 13:24
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 🍺 메인로직 치킨 집 중 1개씩 고르기(isSelected[i] = true), 고르는 로직 반복 -> 최종 m개가 되면 거리 count -> 각 count 받아서 계속 answer과 비교해서 count로 갱신 -> 정답 출력 🍺 필요한 변수들 static ArrayList home; static ArrayList store; static boolean[] isSelected..
-
백준 14503Java/코딩테스트 2023. 4. 6. 01:28
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 바보같이 이동 방향 배열 순서를 잘못 정의해서 한참 고민한 문제... 난이도는 삼성 기출중에 그래도 쉬운 편에 속하는것 같은데 오래 걸렸다....북-동-남-서 방향으로 가야하는데 아무 생각없이 동서남북으로 정의해뒀어서😂 🍇 케이스 정의 #1) 현재칸이 0인 경우 -> clean() #2) 주변 4칸에 청소가 되지 않은 빈칸이 있는지 탐색한다 -> ..
-
[ DFS / BFS ] 개념 및 예제 정리Java/코딩테스트 2023. 4. 5. 18:54
코딩테스트에서 자주 사용되는 완전 탐색 기법 DFS/BFS 정리 자주 나오기도 하고... 중요하기도 해서 복습겸 정리하는 포스팅! DFS 🌷특징 및 언제 사용? - 탐색 공간 자체는 크지만 깊이가 유한할 때(공간 복잡도가 작다) - 최단 경로가 아니어도 괜찮을 때 - 재귀함수로 구현 -> 현재 검사하는 상태에서 전이할 수 있는 상태라면 해당 상태로 전이 - 시작하는 부분에서 한쪽 분기 정하고 최대 깊이까지 탐색 후 다른 분기로 이동, 다시 최대 깊이까지 탐색 ... - 단절점 찾기, 단절선 찾기, 위상정렬, 사이클 찾기 등.. 🌷기본 코드 구현 시 필요한 것 - 방문 여부를 저장할 방문 여부 배열 - 재귀함수로 구현하거나 스택 활용! 🌷 로직 1. while (스택에 값이 있는 동안) 2. 방문 여부 검..