어제오늘 알고리즘 3문제를 풀었다.
필수적인 메소드 몇가지를 배운것같다.
Integer,String,Character 들의 변환과 Array,List 의 변환이 그것이다.
3문제 공통으로 이 메소드들이 필요한걸 보면 조건이나 반복문처럼 필수적인 내용일 것이다.
뭐 변환방법은 깃헙에 올려놨으니 필요할때 가서 봐야겠다.
제일 작은 수 제거한 배열 출력하는 문제를 거진 반나절을 써서 푼거같다.
일요일에 처음 시작해서 4~5시간 하다가 포기하고 오늘에서 겨우 풀었다. 문제가 뭐였을것 같나?
접근을 이상하고 아주 어렵게 했기 때문이었지... 이게 머리가 멍청하면 몸이 고생한다고 딱 그말
대로 였다.
내가 처음 생각한 방법?
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = new int[] {4,3,2,7,-9,6,-5,8,9}; //arr 변수에 들어온 수 배열
int[] getarr = new int[arr.length]; // 여기다 넣고 정리한담에 answer에 넣을거임.
//System.out.println(getarr.length);
int savePast = arr[0]; //이전 값과 비교를 위해 선언해야하는데 처음값은 비교대상이 자신이니까 이렇게 설정
int tempI = 0; //이전 값보다 작아서 우선 빠진 값이 자기보다 더 작은 값을 만났을때 원래 자기 차례를 기억했다가 이때 그 자리로 드감
if (arr.length == 1) {
getarr[0] = -1;
}
else {
for (int i = 0; i < arr.length; i++) {
int saveCurrent = arr[i]; //현재 값은 arr 배열의 i 번째
if ( saveCurrent <= savePast) { //현재 값이 저장된 이전 작은 값보다 더 작다면
getarr[tempI] = savePast; //배열에다가 이전 작은 값이 자기가 원래 for문 돌렸을때 나타났을 기억된 i 번째에 들어감
tempI = i; //이제 기억된 i 번째는 새로 들어온 더 작은값의 i 값으로 새로기억
savePast = saveCurrent; //더 작은값을 이제 지금까지 가장 작은 값이라는 변수에 저장
//System.out.println(savePast);
}
else { //현재 값이 저장된 이전 값보다 크면
//System.out.println(saveCurrent);
getarr[i] = saveCurrent; //배열에 추가하기
}
}
}
System.out.println(Arrays.toString(getarr));
System.out.println(savePast);
}}
그래서 이게 뭔데? 설명할테니 기달려봐라
getarr 라는 수 배열 변수를 새로 선언했다. 이 변수의 배열 길이는? arr 랑 길이가 같다.
int savePast = arr[0]; 이 변수는 작은 값을 저장할거다. for 문 돌면서 지금 값이 과거 작은 값보다 작으면 이제부터 지금값이 작은값이 되면서 이곳에 저장됨. 처음값은 arr 의 0번째의 값과 같음.
int tempI = 0; i 까지의 가장 작은 값이 자신이 되어서 savePast 변수에 저장될때 앞으로 나보다 더 작은 값이 나올 수도 있으니까 그때가서는 원래 내가 있어야 할 위치에 나를 다시 넣기위해 현재의 i 값을 저장해두는 변수. 나보다 작은애 나오면 나는 이 저장된 i 순서에 나를 채워 넣을거임.
if (arr.length == 1) {
getarr[0] = -1;
이건 문제의 조건인데, 배열의 엘리멘트가 1개이면 -1을 출력하라고 해서이렇게 함.
else {
진짜는 여기부터지
for (int i = 0; i < arr.length; i++)
본격적인 for문 돌린다.
int saveCurrent = arr[i];
현재 값이 뭔지를 지칭
여기부터 if문 하나 더 들어간다
if ( saveCurrent <= savePast)
현재 값이 지금까지 나온 값들 중에서 가장 작은 값이라면 이제부터 가장작은 값은 현재 값이 되는것. savePast가 이제부터 내가 된다. 그전에 해줘야 될 일이 있지. 뭐냐고?
원래 savePast에 들어있었던 애는 이제 더이상 가장 작은값이 아니니까 원래 자기가 있었어야 할 i 순서로가서 배열에 참여해야지.
getarr[tempI] = savePast;
이거 한뒤에
tempI = i;
지금 현재 i 의 순서를 저장해야지. 다음에 지금보다 작은값 나오면 나도 저장된 원래 내 순번으로 배열하러 가야하니까.
savePast = saveCurrent; 그리고 마무리.
그렇다면 else 로 saveCurrent > savePast 라면?
그냥 배열에 넣으면되지.
else { //현재 값이 저장된 이전 값보다 크면
//System.out.println(saveCurrent);
getarr[i] = saveCurrent; //배열에 추가하기
}
자 이제 이 코딩의 문제점을 말해보자고
예를들어서 arr 의 배열이
4,3,2,7,-9,6,-5,8,9
이거였다고 치자.
가장 작은 값은 -9잖아. 그럼 저 알고리즘대로 하고 출력해보면 어떤 배열이 나오는지 알아?
[4, 3, 2, 7, 0, 6, -5, 8, 9]
-9가 들어갈 자리에 0이 남는다. 4번째 자리인데 보니까 else로 3번째랑 5번째는 저장했는데
4번째때는 배열에 저장하지 않고 savePast에 저장되니까 4번째가 공백이 생겨버린거다.
자바는 그 공백을 0으로 알아서 만든거고. 3번째 건너뛰고 5번째는 있을 수 없잖아.
그럼 그건 5번째가 아니라 그냥 4번째가 되는거니까. 또 나는 그렇게 되기를 원한거고.
기대값 : 4,3,2,7,6,-5,8,9
이 방법으로는 반드시 공백이 남고 그 공백엔 0이 들어가서 완전히 삭제하지 못하기 때문에 폐기되었다.
내가 생각한 방법인 배열을 이용하는것은 배열 엘리멘트를 다루기가 힘들기 때문에 보통은 리스트를
쓴다고 하여 리스트방법으로 바꿔본것이다.
덕분에 새 메소드도 많이 알고 주로 변환하는 메소드들을 많이 알게되어서 유익한 시간이었다.
자세한 문제 내용은 깃헙TIL에 연동 해놨다.
