행운의 바퀴
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 128 MB | 9372 | 2424 | 1717 | 23.798% |
문제
상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다.
바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.
상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.
희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 바퀴에 적은 알파벳을 알아내려고 한다.
상덕이가 종이에 적어놓은 내용과 바퀴의 칸의 수가 주어졌을 때, 바퀴에 적어놓은 알파벳을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 바퀴의 칸의 수 N과 상덕이가 바퀴를 돌리는 횟수 K가 주어진다. (2 ≤ N ≤ 25, 1 ≤ K ≤ 100)
다음 줄부터 K줄에는 바퀴를 회전시켰을 때 화살표가 가리키는 글자가 몇 번 바뀌었는지를 나타내는 S와 회전을 멈추었을 때 가리키던 글자가 주어진다. (1 ≤ S ≤ 100)
출력
첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면 "!"를 출력한다.
문제풀이
문제는 바퀴를 시계방향으로 S칸 돌릴때마다 화살표가 가리키는 글자가 주어질 때 바퀴의 각 칸에 적어놓은 알파벳을 알아내야 한다.
이번 문제는 배열인데 시작과 끝이 연결되어 있는 배열이다.
이것을 환열이라고 한다. 배열을 사용해서 환열처럼 풀어보자.
1. 바퀴의 커서 인덱스를 S만큼움직인다.
1-0. 인덱스가 배열 범위를 넘어가지 못하면 조정한다.
((currentIndex - step) % N + N) % N는 나머지를 구하는 공식인데 JAVA에서는 음수가 나오면 음의 나머지를 구하게 되어 + N을 하여 양수가 나오게 한다. 마치 환열이다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 원의 칸 수
int K = sc.nextInt(); // 돌린 횟 수
int currentIndex = 0;
while(K-->0) {
int step = sc.nextInt(); // 시계방향으로 step만큼 이동
int nextIndex = ((currentIndex - step) % N + N) % N; // 이동한 칸의 index (예정)
}
}
1-1. 도착한 칸이 아직 알아내지 못한 글자라면 기록한다.
처음 wheel의 배열을 ‘?’ 모두 채워 비교를 해준다.
char[] wheel = new char[N];
Arrays.fill(wheel, '?');
if (wheel[nextIndex] == '?') {
wheel[nextIndex] = nextAlphabet;
}
1-2. 도착한 칸의 글자가 적힌 글자와 다르다면 바퀴는 존재하지 않는다.
이미 글자가 작성이 되어있는데 다른 글자가 들어온다면 잘못된 바퀴이다.
else if (wheel[nextIndex] != nextAlphabet) {
System.out.println("!");
return;
}
1-3. 도착한 칸의 글자가 적힌 글자와 같다면 넘어간다.
위의 조건을 만족하지 않는다면 도착한 칸의 글자와 적힌 글자가 같다는 것이다.
1-4 바퀴에는 중복된 문자가 들어갈 수 없다.
알파벳 대문자 A~Z까지 중복된 문자가 들어갈 수 없기 때문에 isExist boolean 배열을 만들어 중복된 문자인지 검사한다.
boolean[] isExist = new boolean[26];
for (int i = 0; i<N; i++) {
if(wheel[i] == '?') continue;
if (isExist[wheel[i] - 'A']) {
System.out.println("!");
return;
}
isExist[wheel[i] - 'A'] = true;
}
2. 바퀴에 기록된 글자를 마지막으로 도착한 글자부터 출력한다.
currentIndex에는 마지막 nextIndex값이 들어가 있기 대문에 마지막으로 들어온 위치가 있다
요소 하나하나씩 순서대로 출력을 해야 하니 반복을 사용해서 출력해주자 이때 위치가 어디인지 모르니 모듈러를 사용해서 환열이 되도록 하자.
for (int i = 0; i<N; i++) {
System.out.print(wheel[(currentIndex + i) % N]);
}
전체코드
import java.util.Arrays;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
/// 1. 원의 칸 수, 돌린 횟 수, 변경된 칸 수, 나온 문자 입력 받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 원의 칸 수
int K = sc.nextInt(); // 돌린 횟 수
char[] wheel = new char[N];
Arrays.fill(wheel, '?');
int currentIndex = 0;
while(K-->0) {
int step = sc.nextInt(); // 시계방향으로 step만큼 이동
char nextAlphabet = sc.next().charAt(0);
int nextIndex = ((currentIndex - step) % N + N) % N; // 이동한 칸의 index (예정)
if (wheel[nextIndex] == '?') {
wheel[nextIndex] = nextAlphabet;
} else if (wheel[nextIndex] != nextAlphabet) {
System.out.println("!");
return;
}
currentIndex = nextIndex; // 현재 화살표 위치
}
boolean[] isExist = new boolean[26];
for (int i = 0; i<N; i++) {
if(wheel[i] == '?') continue;
if (isExist[wheel[i] - 'A']) {
System.out.println("!");
return;
}
isExist[wheel[i] - 'A'] = true;
}
for (int i = 0; i<N; i++) {
System.out.print(wheel[(currentIndex + i) % N]);
}
}
}
시간복잡도
이 알고리즘에 대한 시간복잡도는 O(max(N, K))인데 K값의 최대값이 더 크므로 O(K)라 봐도 된다.
ALPS식 투표
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 128 MB | 1375 | 491 | 373 | 37.114% |
문제
전대프연(전국 대학생 프로그래밍 대회 동아리 연합)에서는 매년 프로그래밍 대회를 연다. 올해도 무사히 대회를 개최한 전대프연 회장 성진은 수고해준 스태프들에게 수고비를 주기로 하였다. 하지만 몇몇 스태프는 일을 열심히하지 않았기 때문에 성진은 일을 열심히 한 사람에게만 주기로했다. 하지만 일을 무진장 열심히 한 사람과 덜 열심히 한 사람에게 수고비를 똑같이 주는 것은 불공평하다.
고민을 한 성진은 수고비를 받을 사람을 선출하는 방식으로 ALPS(Allegro Leader Picking System) 을 사용하기로 결심했다. ALPS는 이름에서 보이듯이, 아주 유쾌하고 빠르게 사람들을 선별하는 방법이다.
우선 대회 참가자들은 "수고비를 받을 가치가 있는 스태프" 한 명을 선택해 투표를 한다. (참가자가 투표를 하지 않을 수도 있다.) 이 투표결과, 전체 대회 참가자의 5% 미만의 득표를 얻은 사람은 열심히 일을 하지 않은 스태프이므로 후보에서 제외해버린다. 이제 남은 스태프마다, 받은 득표수를 1로 나눈 값, 2로 나눈 값... 14로 나눈 값을 구한다. 이렇게 구한 14개의 실수가 그 스태프의 '점수'들이 된다.
이렇게 14 * (후보 스태프의 명수) 개의 실수를 가진 점수집합을 얻을 수 있다. 이 점수집합에서의 값에 따라 각 스태프들에게 14개의 칩을 나눠주는데, 집합 내에서 가장 큰 점수를 가진 후보 스태프에게 1개의 칩을 주고, 집합 내에서 두 번째로 점수가 큰 후보 스태프에게 1개의 칩을, ... 14번째로 점수가 큰 후보 스태프에게 1개의 칩을 준다. 최종적으로 스태프마다 득표수에 따라 칩의 개수가 다르게 지급될 것이다. 이것이 바로 ALPS식 투표이다. 성진은 스태프가 가진 칩의 개수에 비례해서 수고비를 지급하기로 했다. 신비롭게도, 점수집합에 있는 실수들은 항상 서로 다르도록 투표결과가 나온다고 한다.
우리는 각 스태프마다 몇개의 표를 얻었는지를 알고있다. 이 득표수를 토대로, ALPS식 투표를 수행하게 된 후, 각 스태프가 받을 칩의 개수를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 전대프연 대회에 참가한 참가자들의 수 X( 1 ≤ X ≤ 2,500,000) 이 주어진다. 두 번째 줄에는 전대프연에 참가한 스태프의 수 N (0 ≤ N ≤ 10) 이 주어진다.
다음 N개의 줄에 걸쳐 각 스태프의 정보 -스태프의 이름(항상 대문자 알파벳이다.)과 그 스태프가 받은 득표수- 가 공백을 사이에 두고 주어진다.
출력
득표율이 전체의 5% 이상인 스태프에 대해, 스태프의 이름과 그 스태프가 받은 칩의 개수를 한줄에 하나씩 출력한다. 출력하는 순서는 스태프 이름의 사전순이여야한다.
문제풀이
문제는 득표수가 주어질 때 스태프가 받을 칩의 개수를 구하는 문제이다.
1. 전체 득표수의 5% 미만의 스태프를 후보에서 제외한다.
관리하기 편하도록 모든 배열을 N이 아닌 알파벳 이름 기준으로 기록하였다.
boolean[] validCandidate = new boolean[26];
double validCut = X * 0.05;
int candidateCount = 0;
for(int i=0; i<N; i++) {
String name = sc.next();
int vote = sc.nextInt();
if(vote >= validCut) {
int idx = name.charAt(0) - 'A';
validCandidate[idx] = true;
staffVote[idx] = vote;
candidateCount++;
}
}
2. 남은 스태프 마다 받은 득표수를 1~14로 나눈 점수를 구한다.
class Scroe {
int staffIndex;
double scr;
public Score(int staffIndex, double scr) {
this.staffIndex = staffIndex;
this.scr = scr;
}
}
Scroe[] scores = new Score[candidateCount * 14];
int score_idx = 0;
for (int i=0; i<26; i++) {
if (!validCandidate[i] continue;
for (int j=1; j<=14; j++)
scores[score_idx++] = new Score(i, (double)staffVote[i] / j);
}
3. 전체 점수 집합에서 점수가 큰 1~14번째 스태프에게 칩을 1개씩 지급한다.
sorting을 하여 점수가 큰 스태프에게 칩을 1개씩 지급
sortScroes(scores);
int[] ans = new int[26];
for (int i=0; i<14; i++)
ans[scores[i].staffIndex]++;
/// score 클래스를 내림차순 정렬하는 함수
public static void sortScroes(Score[] arr) {
for (int i=0; i<arr.length; i++) {
for (int j=0; j<i; j++) {
if (arr[j].scr < arr[i].scr) {
Score cur = arr[i]
for (int k=i; k>j; k--)
arr[k] = arr[k-1]
arr[j] = cur;
break;
}
}
}
}
4. 스태프 이름에 대해 사전순으로 후보 스태프와 받은 칩의 수를 출력한다.
for(int i=0; i<26; i++)
if(validCandidate[i])
System.out.println((char)('A'+i) + " " + ans[i));
전체코드
import java.util.Scanner;
class Main {
static class Score {
Score(int staffIndex, double scr) {
this.staffIndex = staffIndex;
this.scr = scr;
}
int staffIndex;
double scr;
}
/// score 클래스를 내림차순 정렬하는 함수
public static void sortScroes(Score[] arr) {
for (int i=0; i<arr.length; i++) {
for (int j=0; j<i; j++) {
if (arr[j].scr < arr[i].scr) {
Score cur = arr[i];
for (int k=i; k>j; k--)
arr[k] = arr[k-1];
arr[j] = cur;
break;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
int N = sc.nextInt();
// 1. 전체 득표수의 5%미만인 스태프를 후보에서 제외
double validCout = X*0.05;
boolean[] validCandidate = new boolean[26];
int[] staffVote = new int[26];
int candidateCount = 0;
for (int i=0; i<N; i++) {
String name = sc.next();
int vote = sc.nextInt();
if(vote >= validCout) {
int index = name.charAt(0) - 'A';
validCandidate[index] = true;
staffVote[index] = vote;
candidateCount++;
}
}
// 2. 남은 스태프 마다 받은 득표수를 1~14로 나눈 점수를 구한다.
Score[] scores = new Score[candidateCount * 14];
int score_idx = 0;
for (int i=0; i<26; i++) {
if (!validCandidate[i]) continue;
for (int j=1; j<=14; j++)
scores[score_idx++] = new Score(i, (double)staffVote[i] / j);
}
// 3. 전체 점수 집합에서 점수가 큰 1~14번째 스태프에게 칩을 1개씩 지급한다.
sortScroes(scores);
int[] ans = new int[26];
for (int i=0; i<14; i++)
ans[scores[i].staffIndex]++;
// 4. 스태프 이름에 대해 사전순으로 후보 스태프와 받은 칩의 수를 출력한다.
for(int i=0; i<26; i++)
if(validCandidate[i])
System.out.println((char)('A'+i) + " " + ans[i]);
}
}
시간복잡도
이 알고리즘의 시간복잡도는 O((validateCount * 14)^2)
'알고리즘 > Brute Force' 카테고리의 다른 글
| [코딩테스트] [10250] ACM호텔 & [1730] 판화 (1) | 2024.12.04 |
|---|---|
| [코딩테스트] [11068] 회문인 수 & [3085] 사탕게임 (0) | 2024.12.03 |
| [코딩테스트] (완전탐색,시뮬레이션) & [10448] 유레카 이론 & [11005] 진법 변환2 (0) | 2024.12.03 |
| [백준/Silver V] 셀프 넘버 - 4673 (0) | 2024.05.24 |