알고리즘89 5주차 알고리즘 복습 - 투 포인터 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법 - 두 개의 포인터 배치 방법 : 같은 방향에서 시작 - 첫 번 째 원소에 포인터 둘 다 배치 : 서로 다른 방향에서 시작 - 첫 번째 원소와 마지막 원소에 배치 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다. O(n^2) -> O(n) p1, p2가 자료 n개까지 중첩이 아니라 +로 연산이 됨. 대표문제 : 특정한 합을 가지는 부분 연속 수열 찾기 Main ) 특정한 수열이 주어졌을 때 연속된 부분 수열의 합이 target이 되는 구간의 좌표 시작, 끝 값 찾기 public static int[] twoPointers(int arr[], int target) { int result[] = {-1, -1}; int p1 = 0; int.. 2023. 8. 6. (백준/자바) 힌트문제2 05. 트리 - 백준 11725번 문제 : 트리의 부모 찾기 11725번: 트리의 부모 찾기 (acmicpc.net) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 강의에서 막 트리를 배워서 응용을 해봤다. - Node 클래스 : 각 노드의 data값과 부모노드 parent, 왼쪽 자식노드 left, 오른쪽 자식노드 right class Node{ int data; Node parent; Node left; Node right; public Node(int data, Node left, Node right, Node parent) { this.data = data; this.parent = parent; this.left = lef.. 2023. 7. 26. (프로그래머스/자바) 힌트문제2 04. 문자열 - 프로그래머스 : 문자열안에 문자열 코딩테스트 연습 - 문자열안에 문자열 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr String의 메소드contains를 이용해서 간단하게 풀었다. public class String_04 { public static int solution(String str1, String str2) { int answer = 2; if(str1.contains(str2)){ answer = 1; } return answer; } public static void main(String args[]){ System.. 2023. 7. 25. (백준/자바) 힌트문제2 03. 구현 - 백준 5613번 문제 : 계산기 프로그램 5613번: 계산기 프로그램 (acmicpc.net) 5613번: 계산기 프로그램 입력의 각 줄에는 숫자와 +, -, *, /, =중 하나가 교대로 주어진다. 첫 번째 줄은 수이다. 연산자의 우선 순위는 생각하지 않으며, 입력 순서대로 계산을 하고, =가 주어지면, 그때까지의 결과를 출 www.acmicpc.net 주어지는 수와 계산 결과가 int형으로 충분히 될 거라고 생각했다. queue와 stack을 이용해서 풀었다. q에 =을 제외한 모든 피연산자와 연산자를 담아놓고 q에서 하나씩 빼면서 진행. 피연산자라면 stack에 push, 연산자면 stack에서 pop하는데 중위연산이므로 stack에는 하나의 숫자밖에 들어있지않음 그래서 stack.pop 하나, q.poll하나 이렇게 피연산자를 두 개 구.. 2023. 7. 25. (프로그래머스/자바) 힌트문제2 02. 배열 - 프로그래머스 : 배열 회전시키기 코딩테스트 연습 - 배열 회전시키기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 보자마자 데크를 이용하면 되겠다는 생각이 들었다. directions이 right면 q.offerFirst(q.pollLast()); left면 그 반대 여기서 q를 배열로 바꾸기 위해서 stream을 사용했다. 리스트를 배열로 바꿀 때랑 똑같다. answer = q.stream().mapToInt(x-> x).toArray(); import java.util.ArrayDeque; import java.util.Deq.. 2023. 7. 25. (프로그래머스/자바) 힌트문제2 01. 해시테이블 - 프로그래머스 : 한 번만 등장한 문자 코딩테스트 연습 - 한 번만 등장한 문자 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해시테이블을 이용한 문제라고 알려주셔서 여기에 처음에 문자열을 찢어서 저장하려고 했는데 그러면 중복된 문자열이어도 최초 한 번은 저장을 하게 된다. 그래서 Hashtable의 gerOrdefault 메소드 사용해서 해당 문자열을 키값으로 두고 나온 횟수를 value에 저장. value값이 1인 key만 list에 저장하고 list를 정렬하여 완성했다. import java.util.ArrayList; import.. 2023. 7. 25. (백준/자바) 힌트문제1 05. 해시테이블 - 백준 10807번 문제 : 개수 세기 10807번: 개수 세기 (acmicpc.net) 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Hashtable; import java.util.StringTokenizer; public class Hashtable_05 { public static void main(String args[]) thro.. 2023. 7. 18. (백준/자바) 힌트문제1 04. 비트연산자 - 백준 2830번 문제 : 행성 X3 2830번: 행성 X3 (acmicpc.net) 2830번: 행성 X3 상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Bit_04 { public static void main(String args[]) throws IOException { BufferedReader br = new Buffere.. 2023. 7. 18. (백준/자바) 힌트문제1 03. 스택 - 백준 9012번 문제 : 괄호 9012번: 괄호 (acmicpc.net) 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택을 이용하는 너무 간단한 문제 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Stack_03 { public static void main(String args[]) throws IOException {.. 2023. 7. 18. 이전 1 2 3 4 5 ··· 10 다음 728x90
