알고리즘 정리
skarltjr / algorithm Goto Github PK
View Code? Open in Web Editor NEW알고리즘 정리
algorithm's Introduction
algorithm's People
Contributors
Watchers
Forkers
sj2305algorithm's Issues
1/13 카카오톡 공채 괄호변환 문제 - 스택을통한 괄호짝 확인
study web service ++
package algo;
import java.util.PriorityQueue;
import java.util.Stack;
public class Solution {
int position = 0;
public String solution(String p) {
String answer = "";
if (p.length() == 0)
{
return p;
}
//1. 일단 균형잡힌 괄호 문자열로 분리
int left = 0;
int right = 0;
for (int i = 0; i < p.length(); i++)
{
if (p.charAt(i) == '(')
{
++left;
} else if (p.charAt(i) == ')')
{
++right;
}
if (left == right)
{
position = i+1;
break;
}
}
//todo 문제가 아래를 재귀로 수행할 때
String u = p.substring(0, position);
System.out.println(u+" -- u");
String v = p.substring(position, p.length());
System.out.println(v + "--v");
//2. 분리된 문자열 u가 올바른 문자열인지 판단
boolean check = checkCorrection(u);
// - 올바르다면 -> v에 대해 과정 반복한걸 u에 덧붙여서 리턴
if (check == true)
{
return u + solution(v);
}
// - 올바르지않다면 ->
if (check == false)
{
String newOne = "";
// 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
newOne = "(";
// 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
newOne = newOne + solution(v);
// 4-3. ')'를 다시 붙입니다.
newOne = newOne + ")";
// 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
u = u.substring(1, u.length());
u = u.substring(0, u.length() - 1);
for (int i = 0; i < u.length(); i++) {
if (u.charAt(i) == '(') {
newOne += ")";
} else {
newOne += "(";
}
}
// 4-5. 생성된 문자열을 반환합니다.
return newOne;
}
return answer;
}
//올바른 괄호 문자열인지 판단 매 서드
boolean checkCorrection(String string)
{
int left = 0;
int right = 0;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < string.length(); i++) {
if (string.charAt(i) == '(') {
++left;
stack.push('(');
} else if (string.charAt(i) == ')') {
++right;
if (i % 2 == 0 && stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return true;
}
}
12/2 모바일프로그래밍 웹뷰 코드 임시저장
메인액티비티
public class MainActivity extends AppCompatActivity {
EditText edtUrl;
Button btnGo, btnBack,btnHome;
WebView web;
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
getSupportActionBar().setDisplayShowHomeEnabled(true);
edtUrl = (EditText) findViewById(R.id.edtUrl);
btnHome = (Button) findViewById(R.id.btnHome);
btnGo = (Button) findViewById(R.id.btnGo);
btnBack = (Button) findViewById(R.id.btnBack);
web = (WebView) findViewById(R.id.webView1);
WebSettings webSettings = web.getSettings();
webSettings.setJavaScriptEnabled(true);
web.addJavascriptInterface(new WebAppInterface(this), "Android");
web.setWebViewClient(new CookWebViewClient());
WebSettings webSet = web.getSettings();
webSet.setBuiltInZoomControls(true);
btnGo.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
web.loadUrl(edtUrl.getText().toString());
}
});
btnBack.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
web.goBack();
}
});
btnHome.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
web.loadUrl("http://본인아이피:8080/");
}
});
}
class CookWebViewClient extends WebViewClient {
@Override
public boolean shouldOverrideUrlLoading(WebView view, String url) {
return super.shouldOverrideUrlLoading(view, url);
}
}
}
액티비티 메인xml
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:tools="http://schemas.android.com/tools"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
android:orientation="vertical" >
<LinearLayout
android:id="@+id/linearLayout1"
android:layout_width="match_parent"
android:layout_height="wrap_content" >
<EditText
android:id="@+id/edtUrl"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_weight="1"
android:hint="URL을 입력하세요."
android:singleLine="true" >
</EditText>
</LinearLayout>
<WebView
android:id="@+id/webView1"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:layout_weight="1"
android:clickable="true" />
<LinearLayout
android:id="@+id/linearLayout2"
android:layout_width="match_parent"
android:layout_height="wrap_content" >
<Button
android:id="@+id/btnBack"
android:layout_marginLeft="42dp"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="이전" />
<Button
android:id="@+id/btnHome"
android:layout_marginLeft="30dp"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="홈" />
<Button
android:id="@+id/btnGo"
android:layout_marginLeft="30dp"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="이동" />
</LinearLayout>
</LinearLayout>
manifest
<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
package="com.example.webview">
<uses-permission android:name="android.permission.INTERNET" />
<application
android:usesCleartextTraffic="true"
android:allowBackup="true"
android:icon="@mipmap/ic_launcher"
android:label="@string/app_name"
android:roundIcon="@mipmap/ic_launcher_round"
android:supportsRtl="true"
android:theme="@style/AppTheme">
<activity android:name="com.example.myapplication.MainActivity">
<intent-filter>
<action android:name="android.intent.action.MAIN" />
<category android:name="android.intent.category.LAUNCHER" />
</intent-filter>
</activity>
</application>
<uses-permission android:name="android.permission.INTERNET"/>
</manifest>
웹앱인터페이스
package com.example.myapplication;
import android.content.Context;
import android.webkit.JavascriptInterface;
import android.widget.Toast;
public class WebAppInterface {
Context mContext;
/** Instantiate the interface and set the context */
WebAppInterface(Context c) {
mContext = c;
}
/** Show a toast from the web page */
@JavascriptInterface
public void showToast(String toast) {
Toast.makeText(mContext, toast, Toast.LENGTH_SHORT).show();
}
}
12/25
12/06
12/14
1/11 가장 큰 수 - Comparator + Arrays.sort
study web service ++
package algo;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String solution(int[] numbers) {
String answer = "";
String[] temp = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
temp[i] = String.valueOf(numbers[i]);
}
Arrays.sort(temp, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return (o2 + o1).compareTo(o1 + o2);
}
});
System.out.println(temp[0]);
if (temp[0].equals("0")) {
answer += "0";
}else{
for (int i = 0; i < temp.length; i++) {
answer += temp[i];
}
}
return answer;
}
}
12/04
12/20
1/21 HTTP + 구명보트
1/2 스킬트리문제
1/1 카카오프렌즈 컬러링북문제
1/29 mvc 재정리 + 단어변환
package algo;
public class Solution {
static int min = 10000;
public int solution(String begin, String target, String[] words) {
int count = 0;
boolean change = false;
boolean[] visited = new boolean[words.length];
// 1. 타겟이 words안에 없으면 못바꾸기 때문에 미리 검증
for (int i = 0; i < words.length; i++) {
if (words[i].equals(target)) {
change = true;
}
}
if (change == false) {
return 0;
}
// 2. dfs
dfs(begin,target,count,words,visited);
return min;
}
public void dfs(String origin, String target, int count, String[] words, boolean[] visited) {
// 모든 단어를 돌면서 만약 방문하지않고 한 글자만 변경한다면 next
// 이 때 count+1
if (origin.equals(target) && count < min) {
min = count;
return;
}
for (int i = 0; i<words.length; i++)
{
if (visited[i] == false && check(origin,words[i]))
{
visited[i] = true;
dfs(words[i],target,count+1,words,visited);
visited[i] = false;
}
}
}
public boolean check(String first,String second) { // 한 글자만 변경하는지 체크
int num = 0;
for (int i = 0; i < first.length(); i++) {
if (first.charAt(i) != second.charAt(i)) {
num++;
}
}
if (num == 1) {
return true;
}
return false;
}
}
12/28
Spring security
12/16
스프링부트 총 복습
1/22 HTTP + 네트워크
package algo;
import java.util.*;
public class Solution {
int current = 0;
public int solution(int n, int[][] computers)
{
Set<Integer> count = new HashSet<>();
int[] record = new int[n];
for (int i = 0; i < n; i++)
{
record[i] = -1;
}
for (int i = 0; i < n; i++)
{
search(i,computers,record);
current++;
}
for (int i = 0; i < n; i++) {
if (record[i] != -1)
{
count.add(record[i]);
}
}
return count.size();
}
public void search(int index,int[][] computers,int[] record)
{
for (int i = 0; i < computers[index].length; i++)
{
//연결이되어있으면
if (computers[index][i] == 1 && record[i]==-1) {
record[i] = current;
if (i != index)
{
search(i,computers,record);
}
}
}
}
}
1/23 HTTP + JPA정리 + 2 x n타일링
package algo;
import java.util.*;
public class Solution {
public int solution(int n)
{
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 2;
for (int i = 2; i < n; i++)
{
// [0]에는 1만 올 수 있고
// [1]에는 [0]-1 [1]-1 or [0]-2-[1]
// [2]에는 [0]-1 [1]-1 [2]-1 or [0]-1 [1]-2-[2] or [0]-2-[1] [2]-1
arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
}
return arr[n-1];
}
/** 1번. 재귀는 시간초과가 나왔다.*/
/* public int solution(int n)
{
// 맨 앞부터 하나씩 최선의 선택 dp
recursive(n);
return count;
}
public void recursive(int n)
{
if (n - 1 >= 0)
{
recursive(n-1);
}
if (n - 2 >= 0)
{
recursive(n-2);
}
if (n == 0)
{
count++;
return;
}
}*/
}
12/29
1/20 HTTP + 전화번호목록 + 위장
package algo;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Arrays.sort(phone_book, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Integer.compare(o1.length(), o2.length());
}
});
//문자열 길이대로 정렬
for (int i = 0; i < phone_book.length; i++) {
for (int j = 0; j < phone_book.length; j++) {
if (phone_book[j].startsWith(phone_book[i]) && i!=j) {
return false;
}
}
}
return answer;
}
}
12/23
12/21
12/18
skarltjr/Memory_Write_Record#5 (comment)
+
restApi
2/4 베스트 앨범
package algo;
import java.util.*;
/**
* 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범
* 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
* 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
* 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
* genres[i] 는 i 번쨰노래의 장르 plays[i]는 i번째 노래의 재생횟수
*
* 즉 장르별로 재생 총 재생횟수에 따라 장르 순서 정렬필요
* 장르에 포함된 노래들 재생횟수에 따라 노래 정렬필요
* 그럼 결과적으로 장르마다 가장 횟수 많은 2개씩 배열에 add /return
* */
public class Solution {
public int[] solution(String[] genres, int[] plays) {
// 1. 2개의 해쉬맵 고유번호와 장르 / 고유번화 재생횟수
HashMap<Integer, String> hashWithGenre = new HashMap<>();
HashMap<Integer, Integer> hashWithCount = new HashMap<>();
Set<String> genre = new HashSet<>();
for (int i = 0; i < genres.length; i++) {
hashWithGenre.put(i, genres[i]);
hashWithCount.put(i, plays[i]);
genre.add(genres[i]);
}
HashMap<String, Integer> genreWithCount = new HashMap<>();
// 2. 장르별 총 재생횟수 구해주고
for (String s : genre)
{
genreWithCount.put(s, 0);
}
for (int i = 0; i < genres.length; i++)
{
String str = hashWithGenre.get(i);
Integer num = hashWithCount.get(i);
genreWithCount.replace(str, genreWithCount.get(str)+num);
}
// 3. 장르별 총 재생횟수에 따라 장르정렬 내림차순으로
ArrayList<String> orderedGenre = new ArrayList<>(genreWithCount.keySet());
Collections.sort(orderedGenre, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return genreWithCount.get(o2)-genreWithCount.get(o1);
}
});
genre = new HashSet<>();
for (String s : orderedGenre) {
genre.add(s);
}
//genre는 내림차순으로 정렬되어있다
ArrayList<Integer> arr = new ArrayList<>();
//todo 장르의 순서를 알았다 - > 장르별로 최대재생 노래 2곡을 골라내야한다
for (String key : orderedGenre) {
int first = 0;
int firstIndex = 0;
int second = 0;
int secondIndex = 0;
for (int i = 0; i < genres.length; i++) {
if (hashWithGenre.get(i).equals(key)) {
if (hashWithCount.get(i) >= first) {
if (hashWithCount.get(i) == first) {
second = hashWithCount.get(i);
secondIndex = i;
} else {
second = first;
secondIndex = firstIndex;
first = hashWithCount.get(i);
firstIndex = i;
}
} else if (hashWithCount.get(i) < first && hashWithCount.get(i) > second) {
second = hashWithCount.get(i);
secondIndex = i;
}
}
}
if (first != 0) {
arr.add(firstIndex);
}
if (second != 0) {
arr.add(secondIndex);
}
}
int[] answer = new int[arr.size()];
int index = 0;
for (Integer i : arr) {
answer[index] = i;
index++;
}
return answer;
}
}
12/26
rest api test code
1/27 studywebservice 복습 + 이중우선순위큐
package algo;
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
public int[] solution(String[] operations) {
int[] answer = new int[2];
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순 맨 앞 max
PriorityQueue<Integer> minQ = new PriorityQueue<>(); //오름차순 맨 앞 min
/** {"I 4", "I 3", "I 2", "I 1", "D 1", "D 1", "D -1", "D -1", "I 5", "I 6"}; 같은 경우를 생각해야한다*/
for (int i = 0; i < operations.length; i++)
{
if (!maxQ.isEmpty() && !minQ.isEmpty() && maxQ.peek() < minQ.peek())
{
maxQ = new PriorityQueue<>(Collections.reverseOrder());
minQ = new PriorityQueue<>();
}
if (operations[i].charAt(0) == 'I')
{
if (operations[i].charAt(2) == '-')
{
// 16같은경우 1만 들어감
String substring = operations[i].substring(3, operations[i].length());
minQ.add(-Integer.parseInt(substring));
maxQ.add(-Integer.parseInt(substring));
} else {
String substring = operations[i].substring(2, operations[i].length());
minQ.add(Integer.parseInt(substring));
maxQ.add(Integer.parseInt(substring));
}
}
if (operations[i].charAt(0) == 'D')
{
if (operations[i].charAt(2) == '-' && !minQ.isEmpty())
{
minQ.remove();
}
else if (operations[i].charAt(2) != '-' && !maxQ.isEmpty())
{
maxQ.remove();
}
}
}
// 최대값이 비었는데 최소값이 존재할 수 없다.
if (maxQ.isEmpty())
{
answer[0] = 0;
answer[1] = 0;
}else{
answer[0] = maxQ.peek();
answer[1] = minQ.peek();
}
return answer;
}
}
12/05
12/24
11-29
1/19 HTTP프로토콜
1/9 소수 찾기 - 순열알고리즘 + 소수찾기
study web service ++
package algo;
import java.util.HashSet;
import java.util.Set;
public class Solution {
Set<Integer> numberSet = new HashSet<>(); // hashset은 중복자동제거
int count = 0;
public int solution(String numbers) {
int answer = 0;
/**
* 소수찾기
*
* 17 3
* [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
* 011 2
* [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
*
* */
int[] array = new int[numbers.length()]; // ex) 123456 -> 1 2 3 4 5 6 하나씩 배열에 저장
for (int i = 0; i < numbers.length(); i++) {
array[i] = numbers.charAt(i)-'0';
System.out.println(array[i]);
}
//1. 순열알고리즘
for (int i = 1; i <= numbers.length(); i++)
{
//순열함수 - n 개 중에서 r 개뽑을 때 -> i는 1개부터 length개 까지로
permutation(array,0,numbers.length(),i);
}
//2. 소수 알고리즘
for (Integer integer : numberSet) {
primeNumberSieve(integer);
System.out.println(integer + "====");
}
return count;
}
//순열함수 - n 개 중에서 r 개뽑을 때
void swap(int[] arr, int depth, int x)
{
int temp = arr[depth];
arr[depth] = arr[x];
arr[x] = temp;
}
void permutation(int[] arr, int depth, int n, int r)
{
if (depth == r) {
String newS = "";
for (int j = 0; j < r; j++) {
newS += arr[j];
}
/** 맨 앞이 0 인경우 진짜 0 을 제외하고는 이 0을 없애줘야한다*/
if (newS.charAt(0) == '0' && newS.length() > 1) {
newS = newS.substring(1, newS.length());
}
Integer sum = Integer.parseInt(newS);
numberSet.add(sum);
return;
}
for(int i=depth; i<n; i++) {
swap(arr, depth, i);
permutation(arr, depth + 1, n, r);
swap(arr, depth, i);
}
}
//소수 체크 -
void primeNumberSieve(Integer integer)
{
Integer end = (int)Math.sqrt(integer);
if (integer == 0 || integer == 1) {
return;
}
boolean prime = true;
for (int i = 2; i <= end; i++)
{
if (integer % i == 0)
{
prime = false;
}
}
if (prime == true) {
count++;
}
return;
}
}
12/15
12/2
1/3
1/26 쿼리dsl 정리
1/4 다리를 지나는 트럭문제
skarltjr/Memory_Write_Record#6 (comment)
+
studyServie
12/31 124나라
1/24 HTTP마무리 + jpa- 스프링데이터jpa
1/31 restApi 재정리 + 디스크 컨트롤러
package algo;
import java.util.*;
public class Solution {
static int total = 0;
public int solution(int[][] jobs) {
int answer = 0;
int count = 0; // 수행된 작업 수
int endPoint = 0; // 하나의 작업이 끝날 때 마지막 포인트
// jobs는 [] - 작업이 요청되는 시점 [] - 작업의 소요시간
// 1. 우선순위 큐에 순서대로 담아서 실행
// 2. 진행 범위내에서 시작하는것들 큐에 담고 다음에 실행
// 3. 이 때 여러개가 담겼다면 그 중 작업소요시간이 최소인 순으로 실행
// 4. 만약 2번에 해당하지않으면 쉬었다가 다시
// 요청시간순으로 정렬
Arrays.sort(jobs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
// 큐에 들어온놈들은 수행시간순으로 정렬
PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
boolean[] visited = new boolean[jobs.length];
q.add(jobs[0]);
visited[0] = true;
endPoint = jobs[0][0];
// 첫번째랑 시작은같은데 종료시간이 다른애들도 넣어줘야한다
for (int i = 1; i < jobs.length; i++) {
if (jobs[i][0] == jobs[0][0]) {
q.add(jobs[i]);
visited[i] = true;
} else {
break;
}
}
while (count < jobs.length)
{
int[] poll = q.poll();
total += (endPoint+poll[1]-poll[0]); // 총 수행시간에 더해주고
endPoint += poll[1];
count++; // 수행된 개수 추가
System.out.println(total);
for (int i = 0; i < jobs.length; i++) {
if (visited[i] == false && jobs[i][0] < endPoint)
{
q.add(jobs[i]);
visited[i] = true;
}
}
// 가장중요한. 만약에 0~~20까지는 쭉 진행되다가 갑자기 [500,5]가 나타나면 20~500까지 쉬다가 시작
// 근데 위에서 total += (total + poll[1]-poll[0])이거하면 poll[0]이 500인데 딱봐도 -500하면 에러
// 쉬었을 때
if (q.isEmpty())
{
for (int i = 0; i < jobs.length; i++)
{
if (visited[i] == false)
{
q.add(jobs[i]);
visited[i] = true;
endPoint = jobs[i][0];
break;
}
}
}
}
return (int)total/ jobs.length;
}
}
2/6 타겟넘버
package algo;
/**
* 주어진 numbers들로 target을 만드는 방법 수를 리턴
* */
public class Solution {
int ans = 0;
public int solution(int[] numbers, int target) {
int count = 0; // 수행한 numbers 중 숫자 개수 . 이게 length랑 같으면 종료
int total = 0; // 총합이 target이면 정답
// (+/-) ㅁ (+/-) ㅁ (+/-) ㅁ ....
// +일때
bfs(numbers,total+numbers[0],target,count+1);
// -일때
bfs(numbers,total-numbers[0],target,count+1);
return ans;
}
public void bfs(int[] numbers,int total, int target, int count)
{
if (count == numbers.length)
{
if (total == target) {
ans++;
return;
}else {
return;
}
}
bfs(numbers, total + numbers[count], target, count + 1);
bfs(numbers, total - numbers[count], target, count + 1);
}
}
11/30
12/17
1/18 자바의 예외처리
1/5 기능개발문제
all h our study webservice ++
package algo;
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int[] solution(int[] progresses, int[] speeds) {
List answer_list = new ArrayList<>();
boolean[] distributed = new boolean[progresses.length];
/**
* progresses = 먼저 배포되어야하는 순 서 대 로 작업의 진도
* speeds = 각 작업의 개발 속도
* */
while (true)
{
boolean isDist = false;
int isEnded = 0;
int turn = 0; // 순서대로 배포되어야 하기 떄문에 index 맞추기위한 변수
int count =0; // 이번턴에 배포된 개수
for (int i = 0; i < progresses.length; i++)
{
progresses[i] += speeds[i];
if (progresses[i] >= 100 && turn == i) // distr~[i] == false
{
isDist = true;
turn++;
if (distributed[i] == false) {
distributed[i] = true;
count++;
}
}
if (distributed[i] == false) {
isEnded++;
}
}
if (isDist = true && count > 0) {
answer_list.add(count);
}
//종료조건
if (isEnded == 0) {
break;
}
}
int[] answer = new int[answer_list.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = answer_list.get(i);
}
return answer;
}
}
12/01
12/19
12/13
1/16 큰 수 만들기
study web service ++
package algo;
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public String solution(String number, int k) {
StringBuilder builder = new StringBuilder();
boolean[] checked = new boolean[number.length()];
int sizeNum = number.length() - k; // 전체에서 - 버려야할 숫자 = 뽑아야할 숫자의 개수
int[] array;
int currentPoint = 0; // 최근에 뽑은 가장큰수의 지점
while (sizeNum != 0)
{
boolean next = false;
String temp = number.substring(currentPoint,number.length()-sizeNum+1);
array = new int[temp.length()];
for (int i = 0; i < array.length; i++)
{
array[i] = temp.charAt(i) - '0';
if (array[i] == 9)
{
next = true;
break;
}
}
if (next == false)
{
Arrays.sort(array,0,array.length); // 맨 앞이 결국 가장 큰 값
}else {
array[array.length-1] = 9; // 9가 가장큰값이니까
}
for (int i = currentPoint; i < number.length()-sizeNum+1; i++)
{
if (array[array.length-1] == number.charAt(i)-'0' && checked[i] == false)
{
currentPoint = i+1;
sizeNum--;
builder.append(array[array.length-1] );
checked[i] = true;
break;
}
}
}
return builder.toString();
}
}
1/12 더 맵게 - 우선순위 큐
study web service ++
package algo;
import java.util.PriorityQueue;
public class Solution {
public int solution(int[] scoville, int K) {
int count = 0;
int zeroCount = 0;
PriorityQueue<Integer> q = new PriorityQueue<>(); // 큰 값대로 자동정렬 큐
/**
* 고려사항 다 0일땐?
* 리스트 사이즈가 1일땐?
* */
for (int x : scoville) // 큐에 다 집어넣고
{
if (x == 0) {
zeroCount++;
}
q.add(x);
}
//전부 0인경우는?
if (zeroCount>1 || q.size() < 2)
{
return -1;
}
while (!q.isEmpty())
{
// 맨 첫값이 가장 작은값일테고
// 가장작은값이 K보다크면 섞을필요가없으니 바로 리턴해주도록하고
if (q.peek() > K)
{
break;
}
if (q.size() == 1) {
return -1;
}
if (q.peek() < K)
{
Integer first = q.poll();
Integer second = q.poll();
Integer newOne = first + (second * 2);
q.add(newOne); //todo add로바꿔보기 - 상관없는걸 확인
}
count++;
}
return count;
}
}
1/25 스프링데이터jpa정리마무리 + 자바-멀티쓰레드 프로그래밍정리 + 프로그래머스 정수 삼각형
구하고자하는것은 최대 값.! - 배열의 각 원소가 중요한것이아니다.
package algo;
import java.util.Arrays;
/** 그리디알고리즘 0-n 까지 중 k-n까지가 최대값을 보장하면 0-k까지의 최대 경로는 변경될 수 있다.
* 그럼 반대로 여기서 맨 아래부터 상향식으로 최대값을 고르도록 하면?
* 최대값을 쌓아올리기*/
public class Solution {
int max = 0; // 최대값
public int solution(int[][] triangle) {
for (int i = triangle.length - 2; i >= 0; i--)
{
for (int j = 0; j < triangle[i].length; j++)
{
if (triangle[i + 1][j] > triangle[i + 1][j+1]) {
triangle[i][j] = triangle[i + 1][j] + triangle[i][j];
} else {
triangle[i][j] = triangle[i + 1][j+1] + triangle[i][j];
}
}
}
return triangle[0][0];
}
/* dfs는 시간초과가 나온다.
public void dfs(int row,int col,int[][] triangle)
{
//재귀의 종료조건
if (row+1 >= triangle.length)
{
total += triangle[row][col];
if (total > max)
{
max = total;
}
total -= triangle[row][col];
return;
}
total += triangle[row][col];
dfs(row + 1, col, triangle);
dfs(row + 1, col + 1, triangle);
total -= triangle[row][col];
}*/
}
1/6 주식거래 문제
all h our study web service
++
package algo;
public class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
int turn = 0;
while (true)
{
if (turn == prices.length) {
break;
}
// 비교대상
int target = prices[turn];
// 떨어지기전까지 count
int count = 0;
for (int i = turn; i < prices.length; i++)
{
if (i == turn)
{
continue;
}
// 다음으로 넘어갈 수
if (i > turn && prices[i] >= target)
{
count++;
}
// 이 경우 가격이 떨어진 것
if (i > turn && prices[i] < target)
{
count++;
answer[turn] = count;
break;
}
if (i == prices.length - 1) {
answer[turn] = count;
}
}
turn++;
}
return answer;
}
}
1/8 카카오공채 문자열압축
web service
++
package algo;
public class Solution {
public int solution(String s) {
int min = 0; // n개 단위로 자른 후 리턴되는 문자열 중 가장 작은 놈 반복문 돌때마다 min이랑 이번턴 리턴값이랑 비교해서 더 작은놈으로
/**
* "abcabcabcabcdededededede"
* 문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
* 문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
* 문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
* 문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.
* */
/**
* 절반까지가 효율성 for문 s.length /2 까지
* i갯수만큼 전 꺼랑 비교해서 같으면 n++해주고 n + 문자열로 대체
* */
if (s.length() == 1)
{
return 1;
}
min = s.length();
for (int i = 1; i < s.length(); i++) //i는 문자열을 i개 단위로 자르기
{
String result = "";// 최종 문자열
int length = 0;
int count = 1; // n개 중복 -> replace
String preWord = "";
int limit = 0; // result 마지막 이 후 index
for (int j = 0; j < s.length(); j+=i) // 전체 문자열에 대해 i개씩 잘라보기
{
String currentWord = "";
if (j + i > s.length()) {
String substring = s.substring(j, s.length());
result = result + substring;
break;
}
currentWord = s.substring(j, j + i);
if (j == 0)
{
preWord = currentWord;
}
result += currentWord;
if (j > 0 && currentWord.equals(preWord))
{
++count;
result = result.substring(0,limit);
result += (count + currentWord);
}
if (j > 0 && !currentWord.equals(preWord))
{
limit = result.length() - currentWord.length();
preWord = currentWord;
count = 1;
}
}
length = result.length();
if (min > length) {
min = length;
}
}
return min;
}
}
문자열의 길이가 1일때도 고려
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.