[Java] TreeMap 정리

1. Java TreeMap

자바에서 쓰이는 TreeMap에 대해서 알아보도록 하겠다. 한마디로 TreeMap은 Tree 구조를 띄고 있는 Map 형태라고 할 수 있다. Map 형태이기 때문에 (key, value)를 함께 저장하고 Tree 구조이기 때문에 이진트리를 기반으로 하고 있다. TreeMap은 Red-Black Tree (레드-블랙 트리)로 이루어져 있다.

2. Red-Black Tree란?

일반적인 이진탐색 트리의 경우에는 값이 전체 트리에 균형있게 분포되어 있다는 보장이 없다. 트리의 왼쪽 자식 노드와 오른쪽 자식 노드가 있을 때 값이 왼쪽으로만 들어가서 트리의 균형이 유지되지 않을 수 있다. 이를 보완하기 위해서 Red-Black Tree에서는 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여서 균형을 맞추도록 한다.

• 
  
  ex) 예를 들어 부모 노드가 7이고 4라는 값을 가지는 노드와 8이라는 값을 가지는 노드를 추가하고 싶다면, 4 노드는 부모 노드의 왼쪽 자식으로, 8 노드는 부모 노드의 오른쪽 자식으로 배치해준다. 
  
  이에 추가하여 Red-Black Tree는 다음과 같은 조건을 만족시킨다. (출처 위키피디아)
  
•  

Red-Black Tree 예시 (https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC)

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
   
   
   

3. TreeMap 사용법

트리맵은 Map의 한 종류이기 때문에 key 와 value값이 두개가 다 필요하다.

1. TreeMap 생성

TreeMap<Integer,String> mymap = new TreeMap<Integer,String>();

트리맵의 생성은 위와 같이 key와 value 값의 자료형을 <> 안에다 명시해줌으로써 생성할 수 있다.

---

 

2. TreeMap 값을 추가하기 

mymap.put(1, "안녕");

위와 같이 put이라는 메서드를 사용해서 값을 추가할 수 있는데 Map 이기 때문에 key, value 순서대로 값을 추가해주어야 한다.

---

 

3. TreeMap 값을 가져오기

System.out.println(mymap.get(1));

위와 같은 코드는 key 값이 1인 value 값을 가져와서 출력을 하겠다는 뜻이다. 우리는 1에 대응하는 value 값을 "안녕"이라고 추가해주었으므로 "안녕"이 출력될 것이다.

---

 

4. TreeMap의 가장 작은 키/ 가장 큰 키 가져오기

가장 작은 키:

mymap.firstKey();

가장 큰 키:

mymap.lastKey();

TreeMap은 항상 정렬을 하고 있기 때문에 가장 작은 키/ 큰 키를 바로 가져올 수 있다는 장점이 있다.

---

  

5. TreeMap 값을 제거하기

mymap.remove(1);

값을 제거할 때는 key값을 기준으로 제거해주게 된다. 즉 위의 코드는 키 값을 1로 가지고 있는 값을 제거하라라는 뜻이다.

---

 

6. TreeMap의 모든 값을 제거하기

mymap.clear();

모든 (key, value)의 쌍을 제거하고 싶다면, clear() 메서드를 사용해주면 된다.

---

 

7. TreeMap의 전체 값을 출력해보기

KeySet()을 활용하면 TreeMap에 저장되어 있는 Key값을 모두 다 가져올 수 있다.

for(Integer i : mymap.keySet()){ 
    System.out.println("[key 값]:" + i + " [Value 값]:" + mymap.get(i));
}

이런식으로 KeySet()을 활용하여 key와 value값을 모두 다 출력해줄 수 있다. 

 

entrySet() 을 활용할 수도 있는데 entrySet()을 활용하면 key와 value가 함께 저장되어 있는 Entry 배열을 가져올 수 있다. 

for (Entry<Integer, String> entry : mymap.entrySet()) {
    System.out.println("[Key 값]:" + entry.getKey() + " [Value 값]:" + entry.getValue());
}

 

이런식으로 출력해줄 수 있다. 

[백준] 2138번: 전구와 스위치 문제

1. 문제

1) 링크

www.acmicpc.net/problem/2138

2) 문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

3) 입력

첫째 줄에 자연수 N(2≤N≤100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

4) 출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

 

더 자세한 문제의 제한과 입출력을 보기 위해서는 위의 링크로 들어가보자!

---

2. 풀이

이 문제는 두 가지 경우로 나누어서 풀어야 한다.

첫 번째 0번 스위치를 눌렀을 경우, 두 번째 0번 스위치를 누르지 않았을 경우로 나누어서 문제를 해결해준다.

 

왜냐하면 첫 번째 스위치만 결정해주게 되면, 자신의 왼쪽에 있는 칸을 바꿀 수 있는 것은 자신 스위치밖에 더 이상 존재하지 않기 때문이다. 

다시 말해서, 왼쪽에서 오른쪽으로 가면서 한 칸씩 스위치를 검사하기 때문에 첫번째 스위치만 켜짐/꺼짐을 결정하면 1번 index의 칸 값을 바꿀 수 있는 스위치는 2번 스위치가 유일하다. 

 

따라서 첫 번째 스위치가 켜졌을 경우와 꺼졌을 경우로 나누어서 문제를 해결해준다.

먼저 첫 번째 스위치가 켜졌을 경우에 시행을 한 뒤에 꺼졌을 경우에도 다음에 시행을 해준다. 주의할 점은 이렇게 순차적으로 코드를 써주게 되면, 두번째 경우인, 첫번째 스위치가 꺼졌을 경우를 할 때 첫번째 경우의 스위치 변화에 영향을 받기 때문에 입력배열을 똑같은 곳에다가 하나 더 저장해두는 것이 필요하다. 

---

3. 코드

이것을 코드화한 것은 아래와 같다.

import java.util.*;

public class Main{
   
    static int n;
    static void change(int a[], int i){
        a[i]=1-a[i];
        a[i+1]=1-a[i+1];
        if (i+2<=n-1){
            a[i+2]=1-a[i+2];
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        int a[]=new int[n];
        int b[]=new int[n];
        String s=sc.next();
        for(int i=0; i<n; i++){
            a[i]=s.charAt(i)-'0';
        }
        s=sc.next();
        for(int i=0; i<n;i++){
            b[i]=s.charAt(i)-'0';
        }
        int c[]=new int[n];
        for(int i=0; i<n;i++){
            c[i]=a[i];
        }
        int count1=1;
        //0번 스위치를 눌렀을 경우
        a[0]=1-a[0];
        a[1]=1-a[1];
        for(int i=1; i<n; i++){
            if (a[i-1]!=b[i-1]){
                count1++;
                change(a, i-1);
            }
        }
        boolean first=true;
        for(int i=0; i<n; i++){
            if (a[i]!=b[i]){
                first=false;
            }
        }
        int count2=0; 
        //안눌렀을 경우
       
         for(int i=1; i<n; i++){
            if (c[i-1]!=b[i-1]){
                count2++;
                change(c, i-1);
            }
        }
         boolean second=true;
        for(int i=0; i<n; i++){
            if (c[i]!=b[i]){
                second=false;
            }
        }
        
        if (!first && !second){
            System.out.println(-1);
        }
        else if (!first){
            System.out.println(count2);
        }
        else if (!second){
            System.out.println(count1);
        }
        else{
            System.out.println(Math.min(count1, count2));
        }
        
    }
}

 

두 번다 시행을 해준 뒤 해당 값이 일치하는지를 한 번 더 검사한 뒤 first/ second라는 boolean 자료형을 하나 만들었다. 만약 둘다 true라면 두 번 시행 모두 가능하다는 뜻이므로 둘 중에서 작은 값을 출력해주면 되고, 하나만 가능하다면 가능한 count 값을 출력해주면 된다. 만약 둘다 가능하지 않다면 문제의 요구사항대로 -1을 출력해준다. 

Unicode, UTF-8, UTF-16, EUC-KR 인코딩에 대해 알아보자

Unicode, UTF-8, UTF-16, 인코딩 등의 용어...

한번쯤은 다 들어봤을 것이다.

하지만 그럼에도 불구하고 정확한 정의와 개념 간의 차이점에 대해 완벽하게 알지 못하는 사람들이 많을 것이다. 

---

1. Unicode

먼저 가장 큰 범주의 개념이라고 할 수 있는 Unicode부터 살펴보자.

우리는 언어를 'A', 'a', '가', '나', '다' 등 문자로 인식하지만 컴퓨터는 오로지 0과 1로만 이루어진 숫자로 인식한다. 따라서 컴퓨터가 사람의 언어를 이해하기 위해서 언어를 bit 형식의 숫자로 변환, 중개하는 역할을 유니코드가 한다고 생각하면 된다. 

 

예를 들어, 한글의 '가'는 0xac00으로 맵핑이 되고 'A'는 0x0041로 맵핑이 된다. 이런식으로 나라 별 언어가 어떻게 인덱스로 변환되는지를 살펴보고 싶다면 아래 code charts를 참고해보면 된다. 

전세계 나라들에서 사용하고 있는 언어의 문자가 어떻게 mapping되는지를 보여주고 있다. 

http://www.unicode.org/charts/

---

UTF는 Unicode를 인코딩 (encoding) 해주는 방식이라고 생각하면 된다. encoding이 필요한 이유는 human language와 컴퓨터 언어 사이의 변환이 필요하기 때문이다. Unicode에서 사람 언어와 컴퓨터 bit 사이의 mapping하는 표를 만들어 주고 그 표를 보면서 서로간의 변환을 도와주는 역할이 UTF라고 보면 된다. 

 

UTF에도 여러 종류가 있다. 대표적으로 많이 들어본 것이 UTF-8과 UTF-16일 것이다. 

UTF-8과 UTF-16의 차이는 문자 하나를 표현할 때 사용할 최소 bit의 차이에 있다. 즉 UTF-8은 문자 하나를 표현할 때 최소 8bit가 필요한 반면, UTF-16은 문자 하나를 표현할 때 최소 16bit가 필요한 것이다. 

 

2. UTF-8

이 중 더 많이 쓰이는 UTF-8 인코딩 방식에 대해 자세히 알아보자. UTF-8 방식은 가변형 인코딩 방식이라고 불린다. 이유는 한글의 경우 초성, 중성, 종성이 있기 때문에 주로 3바이트로 가변 표기 되기 때문이다. UTF-8 방식은 아스키 코드와 호환이 가능하며, 현재 대부분의 환경에서 문자열 처리의 표준으로 자리매김하고 있다. 

 

3. UTF-16

반면 UTF-16의 경우 16 bit 기반으로 문자를 인코딩하기 때문에 한글 또한 2byte로 저장될 수 있다. 영어와 한글이 모두 2byte로 처리되기 때문에 UTF-16은 가변표기 인코딩이 아니다라는 오해가 있는데, 이는 틀린 말이다. UTF-16 인코딩 방식 또한 UTF-8 인코딩과 마찬가지로 가변 표기 인코딩 방식이며, BMP 이외의 문자들은 2byte가 아닌 4byte로 인코딩 되기도 한다. 위 UTF-8 인코딩을 설명할 때 UTF-8 방식이 대부분의 환경에서 문자열 처리의 표준이라고 했는데 자바 기반에서는 UTF-16을 사용한다고 보면 된다. 또한 UTF-16의 경우 UTF-8과 달리 아스키 코드와 호환되지 않는다는 특성을 가지고 있다. 

 

4. EUC-KR

EUC-KR은 한국에서 독자적으로 사용하고 있는 인코딩 방식으로, 완성형 인코딩 방식이라고 불린다. 즉, 초성, 중성, 종성을 조합하여 인코딩을 하는 것이 아니라 완성된 상태의 문자를 2Byte로 표현하는 방식이라고 생각하면 된다. 미리 정해놓은 표를 사용하여 인코딩을 하는 것이고 각 문자마다 2byte의 값이 정해져 있는 형태이다. 

 

 

---

이런 다양한 인코딩 방식으로 자바에서도 컴파일 시 인코딩 문제가 일어나기도 한다.

해당 문제를 해결하는 법은 아래 포스트를 참고하면 되겠다.

https://www.programmingstory.com/2024/02/unmappable-character-for-encoding-ms949.html

[Java] set과 list의 차이점

1. set과 list의 차이점

기술면접을 볼 때 자주 물어보는 질문 중 하나가 set과 list의 차이점이다. 

쉬운 내용 같지만 막상 질문을 받으면 생각나지 않을 수 있으니 잘 정리해두자.

---

간단하게 한꺼번에 정리를 해보겠다.

1. Set은 중복을 허용하지 않는 반면, list는 중복을 허용한다.

2. Set은 순서가 없는 (보장되지 않는) 반면, list는 순서가 존재한다. 

=> 따라서 list는 index라는 개념이 존재하고, set은 index라는 개념이 존재하지 않는다. 

 

아래 추가적인 set과 list에 대한 개념, 그리고 각각을 java에서 구현할 때 조심해야 할 점에 대해 작성해놓았다.

---

2. set 부연설명

자세히 설명을 해보자면, set은 말 그대로 '집합'의 개념이다. 우리가 수학시간에 배웠던 집합을 생각하더라도 집합에는 중복된 원소가 들어갈 수 없다. 따라서 set collection은 중복된 원소를 하나로 계산하고 싶을 때 쓰면 유용하다. 예를 들어, for 문을 돌면서 모든 원소를 추가해주어야 하는데, 이전에 똑같은 원소가 들어간 것이 있을 경우에는 두 번 count하지 않고 싶을 때 쓰면 매우 유용하다. 

 

여기서 주의할 점이 있다. set의 경우 중복을 허용하지 않는다고 했는데, 그러면 Java 내에서 중복은 어떤 방식으로 검사를 하는가를 생각해보자. Java에서는 단순 primitive type 이외에도 다양한 객체가 존재하기 때문에 필요에 따라서 특정 객체를 set에 넣기 위해서는 같음을 어떻게 정의할 것인지에 대한 코드가 필요하다. 

 

예를 들어 hashSet같은 경우에는 hashCode(), equals()를 가지고 비교를 하게 된다. 따라서 이 경우에 set이 우리가 원하는 방식대로 중복을 처리해주기 위해서는 추가적인 구현이 필요하게 된다. 

 

set 자료구조는 빠르다는 장점을 가지고 있지만 모든 element를 순회할 때 list에 비해 직관적이지는 않다. Iterator를 사용하여 hasNext()로 순회를 하거나, 아니면 for each loop을 사용하는 방법도 가능하다.

---

3. list 부연설명

반면 list의 경우에는 우리 일상생활에서 쉽게 접할 수 있듯이 순서를 가지고 있는 자료구조이다. 따라서 원소마다 순서가 붙게 되고 그것을 index라고 주로 정의한다. 따라서 index가 정의되어 있기 때문에 똑같은 객체가 두 번 들어와도 전혀 지장이 없으며, 같은 객체더라도 set과는 달리 다른 index에 서로 같은 객체가 들어 올 수 있다. 

 

Java에서는 list 아래 ArrayList와 LinkedList가 정의되어 있고, 둘 다 자주 사용되는 자료구조이다. ArrayList는 LinkedList에 비해 빠르고 크기를 자유롭게 조절할 수 있는 배열을 뜻한다. 따라서 초기에 java의 primitive type으로 배열과 배열의 크기를 선언하지 않더라도 마음대로 객체를 추가하고 제거할 수 있다는 장점이 있다. LinkedList는 arraylist와 달리, iterator를 사용하여 모든 원소를 순회한다. 

---

중복을 허용하지 않아야 할 때 (똑같은 것을 두 번 세지 않아야 할 때 )는 set을, index를 기반으로 하여 쉽게 순회하고 싶고 순서가 필요한 경우에는 list를 쓴다고 간단히 알아두면 될 것 같다. 

enumerate란? index와 원소를 동시에 알 수 있는 내장함수

1. Python for문

for문을 돌릴 때 가장 기본이 되는 구조는 아래와 같다. 

a=[10, 11, 12, 13]
for index in range(4):
	print(index)
#result
#0
#1
#2
#3

a라는 list에서 range(4) 라고 하여 for문을 돌리면

0부터 4까지 하여 0 1 2 3이 출력된다. (또는 len() 함수를 사용해도 된다) 

 

만약 0, 1, 2, 3번에 해당되는 list의 숫자를 출력하고 싶다면 아래와 같이 적으면 된다.

a=[10, 11, 12, 13]
for index in range(4):
	print(a[index])
    
 #result
 #10
 #11
 #12
 #13

index번째에 있는 리스트의 숫자를 출력하라는 뜻이고,

각각 0번째, 1번째, 2번째, 3번째 수를 출력하여 결과적으로 10, 11, 12, 13이라는 값이 출력되게 된다. 

---

2. enumerate() 

여기서 그러면 list의 index와 index에 해당되는 숫자를 동시에 받아올 수 있는 방법은 없을까라는 생각이 들 수 있다.

그럴 때 바로 enumerate()라는 함수를 사용하면 되는 것이다. 

a=[10, 11, 12, 13]
for index, number in enumerate(a):
	print(index, number)
    
#result
#0 10
#1 11
#2 12
#3 13

파이썬에서 enumerate() 함수는 인덱스와 원소로 이루어진 tuple을 만들어 주는 함수이다.

index는 기본적으로 0으로부터 시작하게 된다.

 

위 코드에서 index가 말 그대로 list에서의 index를 의미하고, number는 해당 원소를 의미하게 된다. 이 두 변수명은 자신이 원하는 대로 설정해주면 된다.

 

따라서 위 코드를 실행하면

0 10

1 11

2 12

3 13

 

이런 식으로 출력되게 되는 것이다. 

 

생각보다 파이썬에서 for문을 돌리면서 인덱스와 원소를 함께 알아오면 편한 경우가 많기 때문에

enumerate()함수를 잘 알아두면 매우 편리할 것이다. 

[백준] 1080번 행렬문제 간단하게 해결하는 법

1. 문제

1) 링크

www.acmicpc.net/problem/1080

2) 문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

3) 입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

4) 출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

더 자세한 문제의 입력/출력 제한사항을 보기 위해서는 위의 링크를 클릭해보자

---

2. 풀이

이 문제는 3*3 씩 배열을 바꿀 수 있으므로 3*3의 가장 좌측 상단의 칸을 index로 기준삼아서 만약 그 칸의 배열이 서로 다르다면 전체 3*3 칸을 바꾸어 주는 식으로 진행한다. 

      예시 그림

예를 들어 위와 같은 5*5 칸이 있다면 살색으로 칠해진 3*3 배열을 움직이면서 보는 것이다. 그 중에서도 좌측 상단에 남색으로 칠해있는 칸의 배열 값이 바뀌어야 한다면 전체 3*3 배열을 바꾸는 식으로 진행한다. 

 

---

이렇게 진행하면 좌측 상단이기 때문에 검사를 하는 칸이 열 n개 중 n-2개, 행 m개 중 m-2개밖에 할 수 없다. 

따라서 좌측 상단의 칸을 기준으로 검사를 한 뒤에 다시 한번 모든 칸에 대해 값이 일치하는지를 검사하여 가능한지의 여부를 검사하게 된다. 

 

3. 코드 

위의 설명을 코드로 나타낸 것은 아래와 같다.

 

import java.util.*;

public class Main{
    static int a[][];
    static void change(int x, int y){
        for(int i=x; i<=x+2; i++){
            for(int j=y; j<=y+2; j++){
                a[i][j]=1-a[i][j]; //1은 0으로, 0은 1로
            }
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        a=new int[n][m];
        int b[][]=new int[n][m];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m ; j++){
                a[i][j]=s.charAt(j)-'0';
            }
        }
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m ; j++){
                b[i][j]=s.charAt(j)-'0';
            }
        }
        int count=0;
        for(int i=0; i<n-2; i++){
            for(int j=0; j<m-2; j++){
                if (a[i][j]!=b[i][j]){
                    count++;
                    change(i,j);
                }
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (a[i][j]!=b[i][j]){
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }
        System.out.println(count);
    }
}

[백준] 11399번 ATM 문제 간단하게 해결해보기

1. 문제

1) 링크

www.acmicpc.net/problem/11399

2) 문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

3) 입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

4) 출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

더 자세한 문제의 사항을 알아보기 위해서는 위의 링크를 클릭해서 살펴보자.

---

2. 풀이

이 문제는 처음부터 기다리는 시간을 누적해서 더하는 것이기 때문에 입력받은 배열을 오름차순으로 정렬한 뒤에 답을 구해주면 그것이 최소 대기시간이 될수밖에 없다.

 

왜냐하면 만약 사람이 5명이라면 1번 사람의 대기 시간은 5번 더해지고, 2번 사람의 대기시간은 4번 더해지고... 이런식이기 때문에 오름차순으로 정렬해서 1번 사람의 대기시간이 가장 짧아야 전체 시간도 가장 짧아질 수 있다.

 

이것만 확실히 하면 비교적 간단한 문제이다. 즉 순열을 만들면서 모든 경우를 테스트 할 필요가 없는 문제이다. 

3. 코드 

이를 코드화 한 전체 코드는 아래와 같다.

 

---

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int a[]=new int[n];
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a);
        int sum=0; 
        int answer=0;
        for(int i=0; i<n; i++){
            sum+=a[i];
            answer+=sum;
        }
        System.out.println(answer);
    }
}

여기서 sum 과 answer가 있는 이유는 ex) 2번 사람의 경우 1번 사람 대기시간 + 2번 사람 대기시간을 한 뒤에 그것을 다시 답의 전체 대기시간에다가 더해주어야 하기 때문이다. 

3번 사람은 1번 +2번 +3번 대기시간을 더해서 sum에 넣어주고 그것을 다시 answer 에 더해주는 이런 식이다.