Roothyo
루시오의 Devlog
Roothyo
전체 방문자
오늘
어제
  • 분류 전체보기 (92)
    • ComputerScience (56)
      • 자료구조 (1)
      • 알고리즘 (6)
      • 네트워크 (12)
      • 코딩테스트 (34)
      • AI & ML (1)
      • BlockChain (1)
      • Security (1)
    • Programming Language (8)
      • JavaScript (8)
      • Python (0)
    • 서비스개발(Web, App) (18)
      • Front-End (2)
      • Back-End (8)
      • Cloud Server (2)
      • DevOps (4)
    • 프로젝트 (9)
      • UNY (4)
      • ThrowOrNot (4)
      • MoA (1)
    • 잡담 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 비디오광고
  • Nest.js
  • level2
  • Node
  • Python3
  • Redis
  • 코테
  • nodejs
  • vmap
  • 알고리즘
  • VPAID
  • chat
  • 코딩테스트
  • Python
  • FRONT-END
  • Socket.io
  • 네트워크
  • 애자일프로젝트
  • 프로그래머스
  • TLS
  • 완전탐색
  • github
  • JavaScript
  • OpenVidu
  • js
  • 백준
  • 클라우드서버
  • node.js
  • Vast
  • 네트워크공부

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Roothyo

루시오의 Devlog

ComputerScience/코딩테스트

백준 1713번 Java 풀이

2021. 1. 11. 22:55

후보 추천하기성공출처분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초 128 MB 4956 1579 1271 33.351%

문제

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

  1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
  2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
  3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
  4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
  5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력

첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

출력

사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

예제 입력 1복사

3
9
2 1 4 3 5 6 2 7 2

예제 출력 1복사

2 6 7

출처

Olympiad > 한국정보올림피아드 > KOI 2007 > 초등부 1번

  • 잘못된 데이터를 찾은 사람: devetude, myungwoo
  • 문제의 오타를 찾은 사람: lg8375

알고리즘 분류

  • 구현
  • 시뮬레이션

풀이

Person 객체를 생성하여, Compatator와 CompareTo를 사용하여, count별, timeStamp별 정렬을 통해 나열한다.
마지막 리턴 시 학생 번호 순서대로 정렬하는 것을 잊지 않도록 조심한다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int N;
	static int R;
	static List<Person> list = new ArrayList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		boolean isThere = false;
		
		for (int r = 0 ; r < R ; r++) {
			int num = sc.nextInt();
			
			//앨범에 존재하는 경우
			for(Person p : list) {
				if (p.num == num) {
					p.count++;
					isThere = true;
					break;
				}
			}
			//앨범에 존재하지 않는 경우
			if (!isThere) {
				if(list.size() < N ) {		//앨범에 자리가 나는 경우
					list.add(new Person(num, 1, r));
				}
				else {						//앨범에 자리가 나지 않는 경우
					list.sort(new Comparator<Person>() {
						@Override
						public int compare(Person o1, Person o2) {
							if(o1.count < o2.count) {
								return -1;
							}
							else if (o1.count == o2.count) {
								if(o1.timeStamp < o2.timeStamp) {
									return -1;
								}
								else if (o1.timeStamp == o2.timeStamp) {
									return 0;
								}
								else {
									return 1;
								}
							}
							else {
								return 1;
							}
						}
					});
					list.remove(0);
					list.add(new Person(num, 1, r));
				}
			}
			isThere = false;
		}

		Collections.sort(list);
		for(Person a : list)
			System.out.print(a.num + " ");
	}
}
class Person implements Comparable<Person>{
//class Person {
	int num;
	int count;
	int timeStamp;
	
	public Person(int num, int count, int timeStamp) {
		this.num = num;
		this.count = count;
		this.timeStamp = timeStamp;
	}
	
	@Override
	public String toString() {
		return "Person [num=" + num + ", count=" + count + ", timeStamp=" + timeStamp + "]";
	}
	@Override
	public int compareTo(Person o) {
		if(this.num < o.num) {
			return -1;
		}
		// 0 = Same = 바꾸지 않음.
		else if (this.num == o.num) {
			return 0;
		}
		// 1 = wrong order
		else {
			return 1;
		}
	}
}

'ComputerScience > 코딩테스트' 카테고리의 다른 글

[프로그래머스] 모의고사 - python3  (0) 2021.06.22
[프로그래머스] 전화번호목록 - python3  (0) 2021.06.21
[프로그래머스] 로또의 최고순위와 최저순위 - python3  (0) 2021.06.19
[프로그래머스] 완주하지 못한 선수 - python3  (0) 2021.06.19
[프로그래머스] 2020 카카오 인턴십 키패드 누르기 - python3  (0) 2021.06.18
    'ComputerScience/코딩테스트' 카테고리의 다른 글
    • [프로그래머스] 전화번호목록 - python3
    • [프로그래머스] 로또의 최고순위와 최저순위 - python3
    • [프로그래머스] 완주하지 못한 선수 - python3
    • [프로그래머스] 2020 카카오 인턴십 키패드 누르기 - python3
    Roothyo
    Roothyo
    개발 관련 지식 포스팅/ 잡담 블로그 입니다. 반갑습니다! (github : https://github.com/geun9716)

    티스토리툴바