사용하지 않는 가장 작은 숫자 찾기 - sayonghaji anhneun gajang jag-eun susja chajgi

Question

문제 설명

정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다.

제한 조건

arr은 길이 1 이상인 배열입니다.
인덱스 i, j에 대해 i ≠ j이면 arr[i] ≠ arr[j] 입니다.

입출력 예

arr	return
[4,3,2,1]	[4,3,2]
[10]	[-1]

✅SOL_1

def solution(arr):

arr.remove(min(arr))

if len(arr)==0:

arr.append(-1)

return arr

cs

리스트 arr에서 가장 작은 수 min(arr)을 찾아 제거해야 한다. remove를 사용하여 값을 찾아 삭제하도록 한다. 이때 arr에 값이 하나만 있었을 경우 가장 작은 수를 삭제하면 리스트는 빈 리스트가 되어 길이 len(arr)이 0이다. 이 경우 if문을 통해 리스트에 -1을 append한다. return은 리스트 arr자체를 반환한다.

리스트에서 del, remove, pop으로 값을 삭제할 수 있다. 먼저 위의 코드에서 사용한 remove는 삭제하고자 하는 데이터를 입력하여 삭제하도록 한다. del과 pop는 삭제하고자 하는 값의 위치(인덱스)를 입력하여 삭제하도록 한다.

a = ['하나', '둘', '셋']

위와 같은 리스트 a가 있을 때, '둘' 값을 삭제하고자 한다면 각각 아래와 같이 작성할 수 있다. '둘' 값의 인덱스는 1이기 때문에 pop과 del에서는 인덱스 1의 값을 삭제하도록 한다.

a.remove('둘')

만약 remove에 입력한 값이 리스트에 두개 이상이면 가장 앞에 있는 것을 삭제한다.

a.pop(1)

pop함수는 입력 값에 아무것도 작성하지 않고 < a.pop() >와 같이 작성하면 맨 뒤의 값을 삭제한다. 또한 pop은 뺀 인덱스의 데이터 값을 출력한다. 따라서 삭제보다는 값을 꺼낸다고 생각하면 된다.

del a[1]

del을 사용할땐 슬라이싱 기능으로 < del a[:1] >와 같이 작성하면 인덱스 0, 1의 값 부분을 전체 삭제할 수 있다

Q. 배열내에서 존재하지 않는 0보다 큰 가장 작은 양수값을 찾아라.

A. 5

소팅 안 하고 루프 한 번만 돌려서 해 볼려고 별에 별 짓을 다 해 봤는데

안 되더라... 결국에는 소팅 -_-

루프 한번으로 정렬하는 방법은 없는 건가라는 의문에 빠졌다.

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int findVal = 1;
        Arrays.sort(A);
        for(int i : A){
            if(i > 0 & i == findVal){
                findVal++;
            }
        }
        return findVal;
    }
}

[백준] 10818번 : 최소, 최대 - JAVA [자바]

2020.02.27 17:59
JAVA - 백준 [BAEK JOON]/1차원 배열

https://www.acmicpc.net/problem/10818

10818번: 최소, 최대

첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

www.acmicpc.net

문제

매우 간단한 문제다!

※ 주의할 점

N 개의 정수를 공백으로 구분해서 주어진다.

3가지 풀이방법을 제시한다.

기본적으로 배열 문제인 만큼 배열을 이용한 방법을 통해 입력방법을 달리하여 Scanner 와 BufferedReader 을 통해 입력받아본다.

그리고 배열을 이용하지 않는 방법을 통해 풀어보고자 한다. 즉, 아래와 같다.

배열 + Scanner
배열 + BufferedReader
배열 X + BufferedReader

풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();
		int[] arr = new int[N];
        
		for (int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
        
		in.close();
		Arrays.sort(arr);
		System.out.print(arr[0] + " " + arr[N - 1]);
	}
}

가장 기초적인 방법이다.

맨 첫줄에 N을 입력받아 해당 크기의 배열을 선언한 뒤 arr 배열 원소에 각각 입력받은 값을 넣어주는 방법이다.

그리고 최댓값과 최솟값을 찾는 방법은 매우 쉽다.

우리에겐 Arrays.sort() 라는 메소드가 있다.

이 메소드는 배열에 저장된 원소 값을 오름차순으로 정렬해주는 메소드다.

이 메소드를 활용하여 정렬하면 최솟값은 배열의 첫번째 원소(index 0)에, 최댓값은 배열의 마지막 원소(arr.length-1)에 있을테니 이를 출력하면 된다.

( 물론 정렬할 필요 없이 방법 3처럼 원소 하나씩 꺼내와서 써도 된다. - 아래 방법3 참고 )

- 방법 2

BufferedReader 을 쓰는 방식이다.

readLine() 을 통해 입력 받기 때문에 공백도 같이 입력되니 StringTokenizer를 통해 분리해주려 한다.

나머지 알고리즘은 똑같다.

그리고 반드시 자료형 타입을 잘 보아야 한다.

st.nextToken() 은 문자열을 반환하니 Integer.parseInt()로 int 형으로 변환시켜준다.

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;


public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		int index = 0;
		int[] arr = new int[N];
		while(st.hasMoreTokens()) {
			arr[index] = Integer.parseInt(st.nextToken());
			index++;
		}
		
		Arrays.sort(arr);
		System.out.print(arr[0] + " " + arr[N - 1]);
	}
}

보다시피 일단 입력받은 정수들을 배열에 저장하기 위해서 StringToken 에 들어있는 모든 토큰들이 없어질 때까지 배열에 모두 담는다.

(참고로 hasMoreTokens() 는 StringTokenizer 에 토큰이 남아있으면 true, 비어있으면 false를 반환한다.)

- 방법 3

근데 배열을 굳이 써줄 필요가 있을까? 메모리만 잡아먹고, 배열의 원소 정렬에서 최악의 경우 시간복잡도가 N^2 이기 때문에 너무 불필요하게 시간을 낭비한다.

그러면 어떻게 하면 시간하고 메모리를 적게 낭비시킬까?

이에 대한 해결은 다음 두 가지를 통해 대부분 해결할 수 있다.

배열을 사용하지 않는다.
입력받은 문자를 즉시 비교한다. ( 그러면 시간복잡도가 N 으로 정렬할 필요 없어 시간을 단축시킬 수 있음 )

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		Integer.parseInt(br.readLine());	//첫 줄 N 은 안쓰이므로 입력만 받는다.
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		int max = -1000001;
		int min = 1000001;
		
		while(st.hasMoreTokens()) {
			int val = Integer.parseInt(st.nextToken());
			if(val>max) {
				max = val;
			}
			if(val<min) {
				min = val;
			}
		}
		System.out.println(min + " " + max);
	}
}

문제에서 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수라고 되어있기 때문에 비교를 위해 max 에는 가장 작은 값으로, min 에는 가장 큰 값으로 초기화를 해준다.

그리고 반복문에서 각 토큰을 가져와 기존 max 의 값보다 큰지, 기존 min 의 값보다 작은지 비교하면서 수행하면 된다.