문제 설명
정수를 저장한 배열, 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 [자바]
//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
- 풀이
가장 기초적인 방법이다.
맨 첫줄에 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 으로 정렬할 필요 없어 시간을 단축시킬 수 있음 )
문제에서 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수라고 되어있기 때문에 비교를 위해 max 에는 가장 작은 값으로, min 에는 가장 큰 값으로 초기화를 해준다.
그리고 반복문에서 각 토큰을 가져와 기존 max 의 값보다 큰지, 기존 min 의 값보다 작은지 비교하면서 수행하면 된다.
- 성능 차이
위에서 부터 순서대로
채점 번호 : 17995776 - BufferedReader + 배열 X
채점 번호 : 17995764 - BufferedReader + 배열
채점 번호 : 17995743 - Scanner + 배열
보면 바로 알 수 있듯이 입력 방법에서 Scanner 와 BufferedReader 의 메모리, 시간 차이는 어마어마하다.
또한 배열을 사용하면 최악의 경우 시간복잡도가 O(N^2) 이지만 배열을 사용하지 않고 즉시 비교하는 경우 시간복잡도가 O(N) 이므로 훨씬 시간이 단축되는 것을 볼 수 있다.
- 정리
알고리즘을 풀 때 물론 해당 조건대로 풀지 않아도 푸는 방법이야 많다.
그러나 일단 기본적으로 배열 목록의 문제인 만큼 배열을 이용하여 풀이를 하고, 그 다음에 배열을 이용하지 않고 풀어볼 수 있으면 그 때 다른 알고리즘으로 풀어보는 것이 좋다고 생각한다.
또한 배열을 굳이 정렬을 하지 않고도 배열 원소를 검사하여 할 수도 있다.
즉, 여러분들이 알고리즘을 구성할 때 시간복잡도와 특정 메소드, 생성자 등 다양한 요성들을 고려하여 최선의 시간복잡도를 찾아보는 것이 중요하다.