프로세스와 쓰레드

  • 프로세스는 '실행 중인 프로그램(program)' 입니다.
  • 프로그램을 실행하면 OS로부터 실행에 필요한 자원(메모리)을 할당받아 프로세스가 됩니다.
  • 프로세스는 '프로그램을 수행하는 데 필요한 데이터와 메모리 등의 자원 + 쓰레드' 로 구성되어 있습니다.
  • 프로세스의 자원을 이용해 실제로 작업을 수행하는 것이 바로 Thread입니다.
  • 모든 프로세스하나 이상의 쓰레드를 가지며, 둘 이상의 쓰레드를 가진 프로세스를 '멀티쓰레드 프로세스( multi-threaded process)'라고 합니다.

멀티쓰래딩의 장단점

멀티쓰레딩의 장점
1. CPU의 사용률을 향상시킨다.
2. 자원을 보다 효율적으로 사용할 수 있다.
3. 사용자에 대한 응답성이 향상된다.
4. 작업이 분리되어 코드가 간결해진다.

멀티쓰레딩의 단점
1. 동기화( Synchronization ), 교착상태( Deadlock )와 같은 문제들이 발생할 수 있다.

 

쓰레드의 구현과 실행

쓰레드의 구현

  • 쓰레드구현하는 방법은 다음과 같이 두 가지가 있습니다.
    1. Thread 클래스를 상속 받는 방법 
    2. Runnable 인터페이스를 구현하는 방법
  • 쓰레드를 구현할 때 어느 쪽을 선택해도 별 차이가 없지만 클래스를 상속받으면 다른 클래스를 상속받을 수 없기 때문에, Runnable 인터페이스를 구현하는 것이 일반적인 방법입니다.
public class ThreadEx1 {

    public static void main(String[] args) {
        ThreadEx1_1 t1 = new ThreadEx1_1();

        Runnable r = new ThreadEx1_2();
        Thread t2 = new Thread(r);

        t1.start();
        t2.start();
    }
}

class ThreadEx1_1 extends Thread {

    @Override
    public void run() {
        for (int i = 0; i < 5; i++) {
            System.out.println(getName());
        }
    }
}

class ThreadEx1_2 implements Runnable {

    @Override
    public void run() {
        for (int i = 0; i < 5; i++) {
            System.out.println(Thread.currentThread().getName());
        }
        
    }
}
  • 위 코드에서 확인할 수 있듯이 Thread 클래스를 상속받은 경우와 Runnable 인터페이스를 구현한 경우의 인스턴스 생성 방법다릅니다.
  • Runnable 인터페이스를 구현한 경우, Runnable 인터페이스를 구현한 클래스의 인스턴스를 생성하여 Thread 클래스의 생성자의 매개변수전달해야 합니다.
  • Thread 클래스를 상속받는 경우, 자손 클래스에서 조상인 Thread 클래스의 메서드를 직접 호출할 수 있지만, Runnable을 구현하면 Thread 클래스의 static 메서드인 currentThread() 를 호출하여 쓰레드에 대한 참조를 얻어 와야 합니다.
  • 쓰레드이름은 다음과 같은 생성자메서드를 통해 지정 또는 변경할 수 있으며, 쓰레드이름을 지정하지 않으면 ' Thread - 번호 '의 형식으로 이름이 정해집니다.
Thread(Runnable target, String name)
Thread(String name)
void setName(String name)

 

쓰레드의 실행 - start( )

  • 쓰레드를 실행하는 메서드입니다. 
  • start() 메서드를 호출한다고 쓰레드가 바로 실행되는 것이 아니며, OS 스케쥴러에 의해 자기 차례가 된 경우 쓰레드가 실행됩니다.
  • 하나의 쓰레드에 대해 start()한 번만 호출될 수 있습니다. 하나의 쓰레드에 대해 start()두 번 이상 호출하는 경우 IllegalThreadStateException이 발생합니다.

start() 와 run()

run() 

  • main 메서드에서 run()을 호출하는 것은 생성된 쓰레드를 실행시키는 것이 아닌 단순히 클래스에 선언된 메서드를 호출하는 것일 뿐입니다.

main 메서드에서 run()을     호출했을 때의 호출 스택

start() 

  • 새로운 쓰레드가 작업을 실행하는데 필요한 호출스택( call stack )을 생성한 다음 run()을 호출해서, 생성된 호출스택에 run()이 첫 번째로 올라가게 합니다.
  • 모든 쓰레드는 독립적인 작업을 수행하기 위해 자신만의 호출스택을 필요로 하기 때문에, 새로운 쓰레드생성하고 실행시킬 때마다 새로운 호출스택생성되고 쓰레드종료되면 작업에 사용된 호출스택은 소멸됩니다.

(1)                                                                                                                 (2)
(3)                                                                                                                    (4)

  • 새로운 쓰레드를 생성하고 start()를 호출한 후 호출스택의 변화
    (1) main 메서드에서 쓰레드의 start()를 호출합니다.
    (2) start()는 새로운 쓰레드를 생성하고, 쓰레드가 작업하는데 사용될 호출스택을 생성합니다.
    (3) 새로 생성된 호출스택에 run()이 호출되어, 쓰레드가 독립된 공간에서 작업을 수행합니다.
    (4) 이제 호출 스택이 2개이므로 스케줄러가 정한 순서에 의해서 번갈아 가면서 실행됩니다.

main 쓰레드

  • main 메서드의 작업을 수행하는 쓰레드입니다.
  • 프로그램을 실행하면 기본적으로 하나의 쓰레드를 생성하고, 그 쓰레드가 main 메서드를 호출해서 작업이 수행되도록 합니다.

 

싱글쓰레드와 멀티쓰레드

  • 두 개의 작업하나의 쓰레드로 처리하는 경우와 두 개의 쓰레드로 처리하는 경우를 가정해보겠습니다.
  • 하나의 쓰레드로 두 작업을 처리하는 경우는 한 작업을 마친 후에 다른 작업을 시작하지만, 두 개의 쓰레드로 작업 하는 경우에는 짧은 시간동안 두 개의 쓰레드가 번갈아 가면서 작업을 수행합니다.
  • 두 개의 쓰레드로 작업을 하는 경우 쓰레드 간 작업 전환( context switching )에 시간이 걸리기 때문에, 싱글 코어에서 단순히 CPU만을 사용하는 계산작업이라면 멀티 쓰레드보다 싱글 쓰레드로 프로그래밍 하는 것이 더 효율적일 수 있습니다.
  • 두 개의 쓰레드가 서로 다른 자원을 사용하는 작업의 경우에는 싱글쓰레드 프로세스보다 멀티쓰레드 프로세스가 더 효율적입니다. ( 예를 들면 사용자로부터 데이터를 입력받는 작업, 네트워크로 파일을 주고받는 작업, 프린터로 파일을 출력하는 작업과 같이 외부기기와의 입출력을 필요로 하는 경우가 이에 해당합니다. )

하나의 쓰레드로 사용자 입력과 출력 처리하는 코드

class ThreadExA {

    public static void main(String[] args) throws Exception {
        String input = JOptionPane.showInputDialog("사용자 값 입력.");
        System.out.println("입력하신 값은 " + input + "입니다. ");

        for (int i = 10; i > 0; i--) {
            System.out.println(i);
            try {
                Thread.sleep(1000); // 1초마다 숫자를 출력하기 위함
            } catch (Exception e) {

            }
        }
    }
}

출력 결과 - 사용자의 입력을 마치기 전까지는 화면에 숫자가 출력되지 않습니다.

두 개의 쓰레드로 사용자 입력과 출력 처리하는 코드

class ThreadB{
    public static void main(String[] args) {
        CustomThread thread = new CustomThread();
        thread.start();

        String input = JOptionPane.showInputDialog("사용자 값 입력.");
        System.out.println("입력하신 값은 " + input + "입니다.");
    }
	
    // 내부 클래스
    private static class CustomThread extends Thread{
        public void run() {
            for (int i = 10; i > 0; i--) {
                System.out.println(i);

                try {
                    sleep(1000);
                } catch (Exception e) {

                }
            }
        }
    }
    
}

출력 결과 - 사용자의 입력과 숫자 출력을 두 개의 쓰레드로 나누어 처리했기 때문에, 사용자가 입력을 마치지 않아도 화면에 숫자가 출력됩니다.

 

데몬 쓰레드 ( daemon thread )

  • 데몬 쓰레드는 다른 일반 쓰레드( 데몬 쓰레드가 아닌 쓰레드 )의 작업을 돕는 보조적인 역할을 하는 쓰레드입니다.
  • 일반 쓰레드가 모두 종료되면 데몬 쓰레드강제적으로 자동 종료됩니다.
  • 가비지 컬렉터, 워드프로세서의 자동저장, 화면자동갱신 등이 데몬 쓰레드에 해당합니다.
  • 데몬 쓰레드무한루프조건문을 이용해서 실행 후 대기하고 있다가 특정 조건이 만족되면 작업을 수행하고 다시 대기하도록 작성합니다.
  • 데몬 쓰레드일반 쓰레드작성방법과 실행방법이 같으며 쓰레드를 생성한 후 실행하기 전에 setDaemon(true)를 호출하여야 합니다.
  • 데몬 쓰레드생성한 쓰레드는 자동적으로 데몬 쓰레드가 됩니다.
boolean isDaemon() : 쓰레드가 데몬 쓰레드인지 확인하는 메서드. 데몬 쓰레드이면 true를 반환합니다.

void setDaemon(boolean on) : 쓰레드를 데몬 쓰레드 또는 사용자 쓰레드로 변경하는 메서드입니다.

 

데몬 쓰레드 설정 코드

class ThreadExDaemon implements Runnable{

    static boolean autoSave = false;

    public static void main(String[] args) {
        Thread thread = new Thread(new ThreadExDaemon());
        thread.setDaemon(true);
        thread.start();

        for (int i = 1; i <= 10; i++) {
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {}

			System.out.println(i);
            if (i == 5) {
                autoSave = true;
            }
        }
        System.out.println("프로그램을 종료합니다.");
    }

    @Override
    public void run() {
    	// 무한 루프와 조건문을 사용해서 구현
        while (true) {
            try {
            	// 3초마다 확인
                Thread.sleep(3 * 1000);
            } catch (InterruptedException e) {}
			    
            if (autoSave) {
                autoSave();
            }
        }
    }
    
    public void autoSave() {
        System.out.println("작업파일이 자동저장되었습니다.");
    }
}
  •  3초마다 autoSave의 값을 확인해서 그 값이 true이면, autoSave()를 호출하는 일을 무한히 반복하는 데몬 쓰레드를 생성하였습니다.
  • 쓰레드데몬 쓰레드로 설정하지 않았다면, 무한루프로 인해 프로그램 강제종료를 하지 않는 한 종료되지 않을 것입니다.
  • setDaemon 메서드는 반드시 start()호출하기 전에 실행되어야 합니다.
    ( 그렇지 않으면IllegalThreadStateException이 발생합니다. )

지네릭스란?

  • Generics는 다양한 타입의 객체들을 다루는 메서드컬렉션 클래스컴파일 시 타입 체크 ( Complie - time type check )를 해주는 기능입니다.
  • 컴파일 시 객체의 타입을 체크하기 때문에 객체의 타입 안정성을 줄이고, 형변환의 번거로움을 줄여줍니다.
Generics 장점
1. 타입 안정성을 제공한다.
2. 타입체크와 형변환을 생략할 수 있으므로, 코드가 간결해 진다.

 

지네릭 클래스의 선언

Class Box<T> {			// 지네릭 타입 T를 선언
	
    T item;
    
    void setItem(T item){ 
    	this.item = item;
    }
    
    T getItem(){
    	return this.item;
    }
}
  • T를 '타입 변수(type variable)'라고 하며, 'Type'의 첫 글자에서 따온 것이라고 합니다.
  • 타입 변수는 '임의의 참조형 타입'을 의미합니다. 
  • 타입 변수T가 아닌 다른 것을 사용해도 되며, 상황에 맞게 의미있는 문자를 선택해서 사용하는 것이 좋습니다.
    1. ArrayList<E>의 경우, 타입 변수 E는 'Element(요소)' 의 첫 글자를 따서 사용했습니다.
    2. Map<K, V>의 경우, 타입 변수 K는 'Key(키)'를 의미하고, 타입 변수 V는 'Value(값)'를 의미합니다.

지네릭 클래스 객체 생성하기

Box<String> box = new Box<String>();	// 실제 타입을 지정
b.setItem(new Object());		// 에러. String이외의 타입 지정 불가 ( 타입 안정성 )
b.setItem("ItemA");			// 정상적인 코드 : String 타입 입력
String item = b.getItem();		// 형변환이 필요 없음 ( 코드가 간결해짐 )
  • 지네릭 클래스타입 변수String 타입으로 지정했기 때문에 , String 타입이 아닌 경우 타입에러가 발생합니다.

지네릭스의 용어

Class Box<T> {}

Box<T>	: 지네릭 클래스. 'T의 Box' 또는 'T Box'라고 읽습니다.
T	: 타입 변수 또는 타입 매개변수. ( T는 타입 문자 )
Box	: 원시 타입( raw type )

Box<String> box = new Box<String>();

Box<String>	: 타입 매개변수에 타입을 지정하는 것으로 '지네릭 타입 호출'이라고 합니다.
String		: 매개변수화된 타입( parameterized type )
  • 컴파일 이후에 Box<String>는 지네릭 타입이 제거되워 원시 타입인 Box로 바뀝니다. ( 아래의 지네릭 타입의 제거 부분 )

지네릭스의 제한

  • T인스턴스 변수로 간주되기 때문에 모든 객체에 대해 동일하게 동작해야하는 static 멤버타입 변수 T사용할 수 없습니다
  • 지네릭 타입의 배열을 생성하는 것은 허용되지 않습니다.
Class Box<T>{

	T[] itemArr;	// 지네릭 배열 타입의 참조변수 선언은 가능합니다.
    
    	T[] toArray(){
    	T[] tmpArr = new T[itemArr.leghth];	// 에러. 지네릭 배열 생성 불가
    	...
        return tmpArr;
    	}

}
지네릭 배열을 생성할 수 없는 이유는 new 연산자 때문입니다. new 연산자는 컴파일 시점에 타입 T가 뭔지 정확히 알아야 하지만, 위 코드에 정의된 Box<T> 클래스를 컴파일하는 시점에서는 T가 어떤 타입이 될지 전혀 알 수 없습니다.

 

제한된 지네릭 클래스

  • 지네릭 클래스에 저장할 수 있는 타입의 종류 제한할 수 있습니다.
  • 'extends' 키워드를 사용하면 특정 타입의 자손들만 대입할 수 있게 제한할 수 있습니다.
  • 인터페이스구현해야 한다는 제약이 필요할 때도 extends 키워드를 사용합니다.
  • 자손인터페이스 제약을 둘 다 주기 위해서는 '&' 기호를 사용합니다.
class FruitBox<T extends Fruit> {	// Fruit 클래스의 자손만 타입으로 지정 가능
	...
}
interface Eatable{}

class FruitBox<T extends Eatable>{...}	// 인터페이스를 구현해야 한다는 제약 추가

 

class FruitBox<T extends Fruit & Eatable>// T는 Fruit의 자손이면서 Eatable 인터페이스를 구현한 클래스
{...}

 

와일드 카드

static Juice makeJuice(FruitBox<Fruit> box){
...
}

static Juice makeJuice(FruitBox<Apple> box){	// 지네릭 타입만 다른 메서드 중복 정의
...
}
  • 메서드매개변수지네릭 타입만이 다른 것만으로는 오버로딩이 성립되지 않습니다.
    ( 이 경우는 '메서드 중복 정의' 로 에러가 발생합니다. 
  • 위 경우에 사용하는 것이 '와일드 카드' 로 기호 '?' 로 표현하며 와일드카드는 어떠한 타입도 될 수 있습니다.
  • '?' 만으로는 Object 타입과 다를 것이 없으므로, 'extends'로 상한을, 'super'로 하한을 제한할 수 있습니다.
< ? extends T >	와일드 카드의 상한 제한. T와 그 자손들만 가능
< ? super T >	와일드 카드의 하한 제한. T와 그 조상들만 가능
< ? >		제한 없음. 모든 타입이 가능합니다. < ? extends Object >와 같습니다.

 

지네릭 메서드

  • 메서드선언부지네릭 타입이 선언된 메서드를 지네릭 메서드라고 합니다. ( 지네릭 타입의 선언 위치반환 타입의 바로 앞입니다. )
  • 지네릭 클래스에 정의된 타입 매개변수지네릭 메서드에 정의된 타입 매개변수는 전혀 다른 별개의 것이므로 같은 참조 문자 T를 사용해도 같은 것이 아니라는 것에 주의해야 합니다. 
  • 지네릭 메서드지네릭 클래스가 아닌 클래스에도 정의될 수 있습니다.

지네릭 메서드 예시

class FruitBox<T>{
	...
	static <T> void sort ( List<T> list, comparator<? super T> c){
    	...
    }
    ...
}
  • 위 코드에서 지네릭 클래스 FruitBox에 선언된 타입 매개변수 T와 지네릭 메서드 sort()에 선언된 타입 매개변수 T는 타입 문자만 같을 뿐 서로 다른 것입니다.
  • static 멤버에는 타입 매개변수를 사용할 수 없지만, 이처럼 메서드지네릭 타입을 선언하여 사용하는 것은 가능합니다.

 

복잡하게 선언된 지네릭 메서드

 

public static <T extends Comparable< ? super T>> void sort ( List<T> list)
  • Collections 클래스의 sort() 메서드입니다. 
  • 이해하기
    1. 타입 T를 요소로 하는 List 매개변수로 허용합니다. 
    2. (<T extends Comparable>) : 'T'는 Comparable구현한 클래스여야 합니다.
    3. (Comparable<? super T>) : 'T' 또는 그 조상의 타입을 비교하는 Comparable이어야 한다는 것을 의미합니다.( 만약 TStudent이고, Person자손이라면? <? super T>Student, Person, Object가 가능합니다. )

지네릭 타입의 제거

  •  컴파일러지네릭 타입을 이용해서 소스파일체크하고, 필요한 곳에 형변환을 넣어줍니다. 그리고 지네릭 타입제거합니다. 즉, 컴파일된 파일(*.class)에 지네릭 타입에 대한 정보가 남지 않습니다. 

지네릭 타입 제거 과정

 

1. 지네릭 타입의 경계( bound )를 제거합니다.

  • 지네릭 타입이 < T extends Fruit >라면 T는 Fruit로 치환됩니다. <T>인 경우는 T는 Object로 치환되며, 클래스 옆의 선언은 제거됩니다. 
Class Box <T extends Fruit> {
	void add (T t){
    	...
    }
}

-- 1. 지네릭 타입의 경계 (bound)를 제거한다. --
Class Box{
	void add (Fruit t){
    	...
    }
}

2. 지네릭 타입을 제거한 후에 타입이 일치하지 않으면, 형변환을 추가합니다.

  • List의 get()은 Object 타입을 반환하므로 형변환이 필요합니다.
T get(int i){
	return list.get(i);
}


-- 2. 지네릭 타입을 제거한 후에 타입이 일치하지 않으면, 형변환을 추가한다. -- 
Fruit get(int i ){
	return (Fruit)list.get(i);
}

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

시간 제한 : 1초

메모리 제한 : 512 MB


풀이

스택 자료구조를 활용하여 문제를 풀었습니다.
원소앞에서부터 순서대로 순회하며 만약 현재 원소스택의 가장 위에 있는 원소보다 큰 경우 현재 원소 그 원소( 스택 가장 위에 있는 원소 )의 오큰수가 됩니다. 만약 꺼낸 이후에도 스택 가장 위에 있는 원소보다 현재 원소가 여전히 크다면 마찬가지로 현재 원소는 그 수의 오큰수가 됩니다. 이런 방식으로 현재 원소가 스택의 에 있는 원소보다 작거나 같아질 때까지 꺼내면서 오큰수를 찾았습니다.

 

원소의 인덱스와 값을 저장할 Element 내부 클래스 생성

    private static class Element{

        int index;
        int value;

        public Element(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

 

오큰수 배열 초기화

int NGE[] = new int[N];

// NGE 초기화
Arrays.fill(NGE, -1);

 

오큰수 찾기 ( 입력을 처리하면서 공백을 기준으로 잘라 원소 하나씩 진행했습니다. )

String s[] = BufferedReader.readLine().split(" ");	// 원소 입력

for (int i = 0; i < s.length; i++) {	// 입력을 처리하면서 로직 진행

	int index = i;	// 원소의 인덱스
	int value = Integer.parseInt(s[i]);	// 원소의 값
    
	Element element = new Element(index, value);	// 현재 원소

	// 스택의 가장 위의 값보다 현재 원소가 큰 경우
	if ( !stack.isEmpty() &&  ( stack.peek().value < element.value ) ) {
    
		while (!stack.isEmpty()) {
        
    			// 스택의 가장 위의 값보다 현재 원소가 작거나 같으면 오큰수가 아니므로 탐색 종료
			if(stack.peek().value >= element.value) break;
			
            		// 오큰수인 경우 꺼내고 인덱스를 통해 NGE 배열 수정
        		Element pop = stack.pop();
			NGE[pop.index] = element.value;
		
        	}	// while문 종료       
            
	}	// if문 종료
    
	stack.add(element);

}	// for문 종료

전체 코드

더보기
import java.io.*;
import java.util.Arrays;
import java.util.Stack;

/**
 * 오큰수
 */
public class BOJ17298 {

    static int N;

    static int[] A;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(bufferedReader.readLine());
        Stack<Element> stack = new Stack<>();
        
        A = new int[N];
        int NGE[] = new int[N];

        String s[] = bufferedReader.readLine().split(" ");

        // NGE 초기화
        Arrays.fill(NGE, -1);

        for (int i = 0; i < s.length; i++) {

            Element element = new Element(i, Integer.parseInt(s[i]));

            if ( !stack.isEmpty() &&  ( stack.peek().value < element.value ) ) {

                while (!stack.isEmpty()) {

                    if(stack.peek().value >= element.value) break;

                    Element pop = stack.pop();
                    NGE[pop.index] = element.value;
                }
            }

            stack.add(element);
        }

        Arrays.stream(NGE).forEach( e -> {
            try {
                bufferedWriter.append(e + " ");
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedWriter.flush();
    }

    private static class Element{

        int index;
        int value;

        public Element(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

}


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

 

17298번: 오큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

 

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K이하인 햄버거를 먹을 수 있다.

햄버거 사람 햄버거 사람 햄버거 사람 햄버거 햄버거 사람 사람 햄버거 사람
1 2 3 4 5 6 7 8 9 10 11 12

위의 상태에서 인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

  • 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
  • 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
  • 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
  • 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
  • 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
  • 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

  • 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
  • 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
  • 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
  • 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
  • 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
  • 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 , 햄버거를 선택할 수 있는 거리 , 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

 

시간 제한 : 0.5초

메모리 제한 : 256MB


풀이

  • 사람이 햄버거를 못 먹는 경우는 다음과 같이 두 가지가 있습니다.
    1. 햄버거가 너무 앞에 있어서 거리K초과하는 경우
    2. 햄버거가 너무 뒤에 있어서 거리K초과하는 경우
  • 어떤 사람이 (1)의 이유로 햄버거선택하지 못하는 경우, 그 사람 뒤에 나오는 사람은 거리가 더 멀어지므로 햄버거선택하지 못하게 됩니다. 따라서 이 경우는 햄버거버려줍니다.
  • 반면에 어떤 사람이 (2)의 경우로 햄버거선택하지 못하는 경우, 그 사람 뒤에 나오는 사람은 선택할 수 있는 가능성이 있으므로 햄버거버리지 않고 다음 사람으로 진행합니다.  

코드

1. 입력 받기

    private static void insertPersonBurger(String s, ArrayList<Integer> people, Queue<Integer> burgers) {
        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == 'H') burgers.add(i + 1);

            else people.add(i + 1);

        }
    }
  • 입력받은 문자열에서 사람리스트에 저장하였고, 햄버거저장하였습니다. 
  • 만약 햄버거리스트저장하는 경우 어떤 햄버거까지 확인했는지 인덱스를 저장하여야 합니다. 

2. 사람 리스트를 순회하며 선택 가능한지 확인

        for (int i = 0; i < people.size(); i++) {
            Integer person = people.get(i);

            if(canEatBurger(person, burgers)) result++;
        }
  • 앞 사람부터 조사하며 햄버거를 선택할 수 있다면 결과( result )를 1증가시켰습니다. 
    private static boolean canEatBurger(Integer person, Queue<Integer> burgers) {

        while (!burgers.isEmpty()) {
            
            Integer burger = burgers.peek();

            int distance = findDistance(person, burger);

            if (person > burger) {

                burgers.poll();

                if (distance <= K) return true;
            }

            if (burger > person) {

                if (distance <= K) {
                    burgers.poll();
                    return true;
                }

                break;
            }
        }

        return false;
    }
  • canEatBurger() 메서드는 현재 조사하는 사람(i번째 사람)이 햄버거선택할 수 있다면 true반환하고 선택할 수 없다면 false반환하는 메서드입니다.
  • 햄버거사람거리를 계산하여 K 이하인 경우 true반환합니다.
    private static int findDistance(int A, int B) {
        return A > B ? (A - B) : (B - A);
    }
  • 햄버거사람거리를 구하는 메서드입니다. 

전체 코드

더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ19941 {

    static int N;
    static int K;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = bufferedReader.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);

        int max = findMax(bufferedReader.readLine());

        System.out.println(max);
    }

    private static int findMax(String s) {
        ArrayList<Integer> people = new ArrayList<>();
        Queue<Integer> burgers = new LinkedList<>();
        int result = 0;

        insertPersonBurger(s, people, burgers);

        for (int i = 0; i < people.size(); i++) {
            Integer person = people.get(i);

            if(canEatBurger(person, burgers)) result++;
        }

        return result;
    }

    private static boolean canEatBurger(Integer person, Queue<Integer> burgers) {

        while (!burgers.isEmpty()) {

            Integer burger = burgers.peek();

            int distance = findDistance(person, burger);

            if (person > burger) {

                burgers.poll();

                if (distance <= K) return true;
            }

            if (burger > person) {

                if (distance <= K) {
                    burgers.poll();
                    return true;
                }

                break;
            }
        }

        return false;
    }

    private static int findDistance(int A, int B) {
        return A > B ? (A - B) : (B - A);
    }


    private static void insertPersonBurger(String s, ArrayList<Integer> people, Queue<Integer> burgers) {
        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == 'H') burgers.add(i + 1);

            else people.add(i + 1);

        }
    }

}


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

 

19941번: 햄버거 분배

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사

www.acmicpc.net

+ Recent posts