2차원 배열
봉우리
지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있다.
각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이다.
봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하시오.
격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개이다.
[[5, 3, 7, 2, 3], [3, 7, 1, 6, 1], [7, 2, 5, 3, 4], [4, 3, 6, 4, 1], [8, 7, 3, 5, 2]]
-> 10입력
매개변수 board에 N*N(2<=N<=100)크기의 격자판 정보가 주어진다.
출력
봉우리의 개수를 반환
dx = {-1, 0, 1, 0}
dy = {0, 1, 0, -1}
nx = i + dx[k]
ny = j + dyk for문 이용
import java.util.*;
public class Main {
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
public int solution(int[][] board) {
int answer=0;
int n=board.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
boolean flag=true;
for(int k=0;k<4;k++) {
int nx=i+dx[k];
int ny=j+dy[k];
if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]>=board[i][j]) {
flag=false;
break;
}
}
if(flag) { answer++; }
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
int[][] arr = {{5,3,7,2,3},{3,7,1,6,1},{7,2,5,3,4},{4,3,6,4,1},{8,7,3,5,2}};
System.out.println(T.solution(arr));
}
}파이썬
가장자리 0으로 채우기
board.insert(0, [0]*n)
board.append([0]*n)
for x in board:
x.insert(0, 0)
x.append(0)any: for문에서 조건이 한번이라도 참이면 true 되고 바로 break (<-> all)
if any(board[i][j]<=board[i+dx[k]][j+dy[k]] for k in range(4)):
continue스카이라인
NN 격자판에 NN개의 도시 빌딩의 높이정보가 주어진다.
앞에서 봤을 때 스카이 라인은 왼쪽부터 해서 [7, 8, 9, 8]의 높이정보로 보이고, 옆에서 보면 위쪽에서부터 해서 [7, 9, 5, 8]이다.
도시의 각 빌딩들의 높이를 높이는데 도시의 스카이라인은 변함이 없이 각 빌딩의 높이를 최대한 높이고자 한다. 각 빌딩의 높이를 증가시킬 수 있는 최대 높이의 합을 구하는 프로그램을 작성하시오.
[[2, 5, 7, 3], [6, 8, 9, 7], [3, 2, 4, 5], [7, 2, 5, 8]]
-> 28
[[3, 7, 6, 2], [5, 3, 8, 7], [3, 2, 5, 7], [7, 7, 5, 3]]
-> 33입력
매개변수 board에 N(3<=N<=100)길이의 수열이 주어진다. (원소는 자연수)
출력
증가할 수 있는 빌딩의 최대 높이의 합을 반환
일단 스카이라인을 구하여 배열로 만들어준다.
-> 배열 row에는 각 행의 최대값을 넣어주고 배열 col에는 각 열의 최대값을 넣어준다.
각 숫자는 해당 행과 열의 스카이라인과의 차이-1만큼을 높일 수 있다.
-> 각 숫자를 row[i], clo[j]와 비교한다.
import java.util.*;
public class Main {
public int solution(int[][] board) {
int answer=0;
int n=board.length;
int[] row = new int[n];
int[] col = new int[n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(board[i][j] > row[i]) { row[i]=board[i][j]; }
if(board[j][i] > col[i]) { col[i]=board[j][i]; }
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
answer+=Math.min(row[i], col[j])-board[i][j];
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
int[][] arr = {{2,5,7,3},{6,8,9,7},{3,2,4,5},{7,2,5,8}};
System.out.println(T.solution(arr));
}
}회장선거
(작년 카카오 공채 1번문제)
현수네 반 N명의 학생이 각자 회장후보를 추천한다. 한 학생이 여러명을 추천할 수 있다.
추천횟수가 k번 이상이 학생들만 회장선거에 출마할 수 있다. 회장선거에 출마한 학생들은 자기를 추천해준 학생들에게 감사의 이메일을 보내기로 함
0번 학생부터 N-1번 학생까지 각 학생이 감사이메일을 받는 횟수를 알아내는 프로그램
만약 0번 학생이 3번 학생을 추천했다면 [0, 3]의 순서쌍 입력정보가 들어온다.
만약 반 학생이 4명이고, 각 학생의 추천정보가 [0, 1], [0, 3], [1, 2], [2, 0], [2, 3], [3, 0]이고, k=2이면 회장후보는 0번과 3번이다. 그리고 각 학생이 받는 감사이메일 횟수는 0번은 1통, 1번은 0통, 2번은 2통, 3번은 1통이다.
4, [[0, 1], [0, 3], [1, 2], [2, 0], [2, 3], [3, 0]], 2
-> [1, 0, 2, 1]
입력
매개변수 n(3<=n<=100)에 반학생수가 전달된다.
매개변수 votes에 추천정보가 주어지고, 매개변수 k에 값이 전달된다.
(모든 학생이 추천을 하는 것은 아님. 할 수도, 안 할 수도)
출력
각 학생이 받는 감사메일 횟수를 배열의 형태로 반환
votes의 첫번째 열에는 투표하는 학생 번호, 두번째 열에는 추천받은 학생 번호
이걸로 2차원 배열로 첫번째 열을 행으로 하여 투표를 받으면 1이 되도록 하고 j고정으로 for문 돌려서 그 열의 합계를 출력하도록 한다.
혼자 한거
import java.util.*;
public class Main {
public ArrayList<Integer> solution(int n, int[][] votes, int k) {
ArrayList<Integer> answer=new ArrayList<>();
int[][] report = new int[n][n];
int[] candidate = new int[n];
for(int i=0;i<votes.length;i++) {
report[votes[i][0]][votes[i][1]]++;
}
for(int i=0;i<n;i++) {
int sum=0;
for(int j=0;j<n;j++) {
sum+=report[j][i];
}
if(sum>=k) {
candidate[i]++;
}
}
for(int i=0;i<n;i++) {
int sum=0;
for(int j=0;j<n;j++) {
if(report[i][j]==1&&candidate[j]==1) {
sum++;
}
}
answer.add(sum);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
int[][] arr = {{0, 1}, {0, 3}, {1, 2}, {2, 0}, {2, 3}, {3, 0}};
System.out.println(T.solution(4, arr, 2));
}
}수정
import java.util.*;
public class Main {
public ArrayList<Integer> solution(int n, int[][] votes, int k) {
ArrayList<Integer> answer=new ArrayList<>();
int[][] report = new int[n][n];
int[] candidate = new int[n];
for(int[] x : votes) {
report[x[0]][x[1]]=1;
}
for(int i=0;i<n;i++) {
int cnt=0;
for(int j=0;j<n;j++) {
if(report[j][i]==1) { cnt++; }
}
if(cnt>=k) { candidate[i]=1; }
}
for(int i=0;i<n;i++) {
int cnt=0;
for(int j=0;j<n;j++) {
if(report[i][j]==1 && candidate[j]==1) { cnt++; }
}
answer.add(cnt);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
int[][] arr = {{0, 1}, {0, 3}, {1, 2}, {2, 0}, {2, 3}, {3, 0}};
System.out.println(T.solution(4, arr, 2));
}
}학생번호가 아니라 이름으로 작성할 경우
해쉬 사용
사람 이름을 key로, 위에서 행을 value로
['john', 'tom', 'park', 'nick']
john:0
tome:1
park:2
nick:3이를 이용하여 report 만들고 나머진 그대로
스택
올바른 괄호
괄호가 입력되면 올바른 괄호면 "YES", 올바르지 않으면 "NO"를 출력한다.
(())() -> YES
(()())) -> NO입력
매개변수 s에 괄호 문자열 입력 (최대 길이 30)
출력
YES, NO 반환
소스코드
import java.util.*;
class Main {
public String solution(String s){
String answer="YES";
Stack<Character> stack = new Stack<>();
for (char x : s.toCharArray()) {
if(x=='(') { stack.push(x); }
else {
if(stack.empty()) { return "NO"; }
stack.pop();
}
}
if(!stack.empty()) { answer="NO"; }
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("(()(()))(()"));
}
}여는 괄호는 stack에 넣고 닫는 괄호를 만나면 어떠한 로직(ex. pop)
닫는 괄호를 만나면 그 짝꿍은 스택의 최상단에 있음
마지막까지 했을 때 올바른 괄호면 스택이 비어있고 올바르지 않으면 남아있음
(()))일 경우엔 비어있는 스택에서 pop -> return NO
괄호문자 제거
입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력한다.
(A(BC)D)EF(G(H)(IJ)K)LM(N)
-> EFLM입력
매개변수 s에 문자열 입력 (최대 길이 100)
출력
남은 문자만 반환
소스코드1
닫는 괄호 만나면 여는 괄호 만날때까지 pop하고 남은거를 string으로
import java.util.*;
class Main {
public String solution(String s){
String answer="";
Stack<Character> stack = new Stack<>();
for (char x : s.toCharArray()) {
if(x!=')') { stack.push(x); }
else {
while(true) {
if(stack.pop()=='(')
break;
}
//while(stack.pop()!='(');
}
}
while(!stack.empty())
answer=stack.pop()+answer;
//for(char x : stack) { answer += x; }
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("(A(BC)D)EF(G(H)(IJ)K)LM(N)"));
}
}소스코드 2
괄호만 스택에 넣기
닫는 괄호 만나면 여는 괄호 pop
알파벳을 만났는데 스택이 비어있다 -> 괄호 밖에 있다 -> answer에 더해줌
import java.util.*;
class Main {
public String solution(String s){
String answer="";
Stack<Character> stack = new Stack<>();
for (char x : s.toCharArray()) {
if(x=='(') stack.push(x);
else if(x==')') stack.pop();
else {
if(stack.empty()) answer+=x;
}
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("(A(BC)D)EF(G(H)(IJ)K)LM(N)"));
}
}충돌하는 수열
N 길이의 음수와 양수로 이루어진 수열이 주어진다.
음수의 값은 왼쪽으로 이동하고, 양수의 값은 오른쪽으로 이동한다. 이동하다가 양수와 음수가 부딪치면 다음과 같은 결과가 나온다.
1. 부딪치는 양수와 음수가 서로 절대값의 크기가 다르면 절대값이 큰 값이 살아남고 작은 값은 수열에서 사라진다.
2. 만약 부딪치는 양수와 음수가 절대값이 같다면 두 수 모두 사라진다.
(같은 방향으로 움직이는 숫자들은 절대 부딪칠일이 없다.)
[3, 5, -2, -5] -> [3]
[-2, -1, -3, 1, 3] -> [-2, -1, -3, 1, 3]
[-2, -1, 2, 1, -3, 2] -> [-2, -1, -3, 2]입력
매개변수 nums에 N(3<=N<=100,000)길이의 수열이 주어진다.
출력
최종적으로 남은 수열 반환 (결과가 빈 배열은 없음)
양수는 무조건 집어넣기
음수는 스택이 비어있거나 스택 상단이 음수면 넣기
음수 중 이 경우가 아니면 조건에 맞는지 봐야됨
import java.util.*;
class Main {
public ArrayList<Integer> solution(int[] nums){
ArrayList<Integer> answer = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
for(int x : nums) {
if(x>0) { stack.push(x); } // 양수는 무조건 넣기
else {
// 음수는 스택이 비었거나 스택 상단이 음수일 때 넣기
if(stack.empty()||stack.peek()<0) { stack.push(x); }
else {
boolean flag = false;
while(!stack.empty() && stack.peek()>0) {
int left = stack.pop();
if(Math.abs(x)>left) { flag = true; } // left는 무조건 양수
// x가 없어질땐 break가 꼭 있어야됨
else if(Math.abs(x)==left) {
flag=false;
break; // 다 없애고 끝
}
else {
stack.push(left);
flag=false;
break;
}
}
if(flag) { stack.push(x); }
}
}
}
for (int x : stack) { answer.add(x); }
return answer;
}
public static void main(String[] args){
Main T = new Main();
int[] arr = {-2, -1, -3, 1, 3};
int[] arr1 = {-2, -1, 2, 1, -3, 2};
System.out.println(T.solution(arr));
System.out.println(T.solution(arr1));
}
}쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기를 자른다.
- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예이다.
굵은 실선: 쇠막대기
점선: 레이저 위치
점선 화살표: 레이저의 발사 방향
괄호를 이용하여 왼쪽부터 순서대로 표현
1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '( )'으로 표현됨 모든 '( )'는 반드시 레이저를 표현함
2. 쇠막대기의 왼쪽 끝은 여는 괄호 '( '로, 오른쪽 끝은 닫힌 괄호 ' )'로 표현된다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
()(((()())(())()))(()) -> 17
(((()(()()))(())()))(()()) -> 24입력
매개변수 s에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 문자열로 주어진다.
출력
잘려진 조각의 총 개수를 나타내는 숫자를 반환
여는 괄호는 넣고 닫는 괄호 만났을때 이것이 레이저인지 쇠막대기인지 판별해야함
바로 앞에 문자가 여는 괄호면 레이저임
틀린 소스코드
레이저로 자른 오른쪽 막대 주워담음
()면 -1+size, (면 +1
-> stack에서 pop으로 '('인지 확인하면 안되고 string에서 확인해야됨
satck에서 pop하면 무조건 '('
import java.util.*;
class Main {
public int solution(String s){
int answer=0;
Stack<Character> stack = new Stack<>();
for (char x : s.toCharArray()) {
if(x=='(') {
stack.push(x);
answer++;
}
else {
if(stack.pop()=='(') {
answer--;
answer+=stack.size();
}
}
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("()(((()())(())()))(())"));
}
}소스코드
레이저로 자른 왼쪽 막대 주워 담음
닫는 괄호 만나면 무조건 pop
answer은 ()면 +size / )면 +1
import java.util.*;
class Main {
public int solution(String s){
int answer=0;
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length(); i++) {
if(s.charAt(i)=='(') { stack.push(s.charAt(i)); }
else {
stack.pop();
if(s.charAt(i-1)=='(') {
answer+=stack.size();
}
else {
answer++;
}
}
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("(((()(()()))(())()))(()())"));
}
}가장 큰 수
숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수 만들기
만약 5276823에서 3개의 자릿수를 제거한다면 7823이 가장 큰 숫자가 됨
5276823 3 -> 7823
9977252641 5 -> 99776입력
매개변수 num에 숫자(최대 길이 30)와 매개변수 m에 제거해야할 자릿수의 개수가 주어짐
출력
가장 큰 수 반환
스택 상단이 더 크면 다 빼냄 더 작으면 넣음 -> 무조건 오름차순
가장 작은 수가 만들어짐
1 4 3 6 5 8 7 4 9
-> 1 3 4 9스택 상단이 더 작으면 다 빼냄 더 크면 넣음 -> 내림차순
import java.util.*;
class Main {
public String solution(String s, int m){
String answer="";
Stack<Integer> stack = new Stack<>();
for (char x : s.toCharArray()) {
while(!stack.empty() && m>0 && stack.peek()<(x-48)) {
stack.pop();
m--;
}
stack.push(x-48);
}
while(m>0) { // 위에 코드 실행 후에도 빼야하는 횟수가 남을 경우 뒤에서부터 빼줌
stack.pop();
m--;
}
for(int x : stack) { answer+=x; }
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("5276823", 3));
System.out.println(T.solution("753421", 3));
}
}stack이 정수형이라서 x-48로 문자형을 정수형으로 변환해줌
