import java.util.ArrayDeque;
import java.util.Scanner;
public class Main_BJ_10773_제로 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
ArrayDeque<Integer> q = new ArrayDeque<>();
for(int i=0; i<k; i++){
int n = sc.nextInt();
if(n!=0)
q.offer(n);
else
q.pollLast();
}
int ans = 0;
while(!q.isEmpty()){
ans+= q.poll();
}
System.out.println(ans);
}//main
}
queue는 First In First Out 자료구조이므로 ArrayDeque를 이용해서 풀이했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_BJ_틀 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String str;
while((str=br.readLine())!=null){
st = new StringTokenizer(str);
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(a+b).append("\n");
}
System.out.println(sb);
}
}
입력을 그냥 끝까지 받아야 할 때 어떻게 해야할지 잘 몰라서 검색했다.(이전에 이와 관련된 문제 올린듯..)
BufferedReader일 경우엔 문자열을 입력받을때, 존재하지 않는다면 null을 리턴하기 때문에 null인지 아닌지 확인하면 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main_BJ_1715_카드정렬하기 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i=0; i<n; i++){
pq.offer(Integer.parseInt(br.readLine()));
}
int max = 0;
while(pq.size()>1){
int a = pq.poll();
int b = pq.poll();
pq.offer(a+b);
max += a+b;
}
System.out.println(max);
}//main
}
해당 문제는 greedy로 해결할 수 있다.
1. 카드를 priority queue에 넣어두고 차례로 뽑는다.(자동으로 오름차순 정렬!)
2. 그 후 priority queue에서 두 개씩 뽑으며 수를 더하고, 다시 priority queue에 넣어둔다.(누적합이기 때문)
3. 이때, 뽑은 두 수를 더한 값을 계속 누적해서 더해줄 변수에 넣어둔다.
4. 이 수를 출력하면 끝!
사실 본격적으로 풀기 전에 어쩌다보니 푸는걸 얼핏 들은적이 있어서... 금방 풀었디만...
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main_BJ_1946_신입사원 {
public static class person implements Comparable<person>{
int paper;
int interview;
public person(int paper, int interview){
this.paper = paper;
this.interview = interview;
}
@Override
public int compareTo(person p){
return this.paper-p.paper;
}
}//person
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for(int tc = 0; tc<t; tc++){
int n = Integer.parseInt(br.readLine());
ArrayList<person> arr = new ArrayList<>();
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
arr.add(new person(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(arr);
// 이미 오름차순 정렬을 했기 때문에, 마지막으로 합격한 사람보다 인터뷰 순위가 작으면 무조건 합격!
// 서류는 이미 이전사람보다 클 것이고, 인터뷰 순위마저 큰다면 조건에 위배가 된다.
int ans = 1;
// 처음은 서류1등 인터뷰 성적
int min = arr.get(0).interview;
// 서류 2등 친구부터
for(int i=1; i<arr.size(); i++){
// 만약 기준 등수 보다 살펴보는 친구의 등수가 높다면? -> 선발
// 가장 최근에 채용된 지원자의 면접 순위보다 높은 지원자 찾기
if(arr.get(i).interview < min){
// 기준 등수 갱신
min = arr.get(i).interview;
// 선발
ans++;
}
}//for
// 시간초과 나는 코드
// for(int i=1; i<arr.size(); i++){
// for(int j=0; j<i; j++){
// if(arr.get(i).interview < arr.get(j).interview){
// ans++;
// break;
// }
// }
// }//for
sb.append(ans+"\n");
}//tc
System.out.print(sb);
}//main
}
진짜 시간초과가 도저히 해결이 안 나서 여러 블로그를 읽어보고...
왜 저렇게 푸는지 생각한 것 같다.
일단... 절대절대 2중 for문 돌려서 해결할 생각 하지 말 것!!!!
시간초과가 난다...(N이 10만이라서 시간 초과 난다)
먼저, 서류 성적 순으로 정렬을 해준다!
Collections.sort는 NlogN으로 정렬을 해주기 때문에 시간초과 걱정은 할 필요 없다.
그리고 기준 변수를 정해주고, 확인하는 방식으로 해야한다.
이때, 변수란 마지막으로 합격한 사람의 인터뷰 성적이다.
이미 오름차순 정렬을 했기 때문에, 마지막으로 합격한 사람보다 인터뷰 순위가 작으면 무조건 합격!!!
서류는 이미 이전 사람보다 클 것이고(등수가 낮을 것이고), 인터뷰 순위마저 크다면 조건에 위배가 된다!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_BJ_14503_로봇청소기 {
static int n, m, ans;
static int[][] map;
// 상하좌우
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
simulation(r, c, d);
System.out.println(ans);
}//main
private static void simulation(int r, int c, int d){
int x = r;
int y = c;
int dir = d;
while(true){
boolean flag = false;
if(map[x][y] == 0) {
//현재 칸 청소
map[x][y] = 2;
ans++;
}
//주변 살펴보기
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 청소되지 않은 칸이 있는 경우
if(check(nx, ny) && map[nx][ny] == 0){
// 반시계 방향으로 회전
dir--;
if(dir < 0)
dir = 3;
flag = true;
break;
}
}//for
//주변 청소되지 않은 칸이 있을 때
if(flag){
// 앞쪽 칸이 청소되지 않았을 때
int[] next = front(x, y, dir);
if(check(next[0], next[1]) && map[next[0]][next[1]] == 0) {
//전진
x = next[0];
y = next[1];
}
}
// 주변 4칸 중 청소되지 않은 빈 칸이 없을 때
else {
int[] next = back(x, y, dir);
//한 칸 후진할 수 있으면
if(check(next[0], next[1])){
x = next[0];
y = next[1];
}
//없으면 탈출
else
break;
}
}//while
}//simulation
private static boolean check(int x, int y){
if(x<0 || y<0 || x>=n || y>=m || map[x][y] == 1)
return false;
return true;
}//check
private static int[] front(int x, int y, int dir){
switch (dir) {
case 0: {//북
int nx = x - 1;
return new int[]{nx, y, dir};
}
case 1: { //동
int ny = y + 1;
return new int[]{x, ny, dir};
}
case 2: {//남
int nx = x + 1;
return new int[]{nx, y, dir};
}
case 3: { //서
int ny = y - 1;
return new int[] {x, ny, dir};
}
}//switch
//아무것도 아닐 때
return new int[] {-1, -1, -1};
}//front
private static int[] back(int x, int y, int dir){
switch (dir) {
case 0: {//북
int nx = x + 1;
return new int[]{nx, y, dir};
}
case 1: { //동
int ny = y - 1;
return new int[]{x, ny, dir};
}
case 2: {//남
int nx = x - 1;
return new int[]{nx, y, dir};
}
case 3: { //서
int ny = y + 1;
return new int[] {x, ny, dir};
}
}//switch
//아무것도 아닐 때
return new int[] {-1, -1, -1};
}//back
}