โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Back Tracking

[๋ฐฑํŠธ๋ž˜ํ‚น / Kotlin] BOJ 15649 ~ 15652 - N๊ณผ M (1 ~ 4)

N๊ณผ M (1) ๋ฌธ์ œ ํ’€์ด ์–ธ์–ด Kotlin ์ฝ”๋“œ import java.util.* lateinit var visit: Array lateinit var input: Array var n: Int = 0 var m: Int = 0 fun main() = with(Scanner(System.`in`)) { n = nextInt() m = nextInt() visit = Array(n + 1) { 0 } input = Array(n + 1) { 0 } dfs(0) } fun dfs(depth: Int) { if (depth == m) { for (i in 0 until m) { print("${input[i]} ") } println() return } for (i in 0 until n) { if (vis..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/String

[๋ฌธ์ž์—ด / Kotlin] 2019 ์นด์นด์˜ค ๊ฐœ๋ฐœ์ž ๊ฒจ์šธ ์ธํ„ด์‹ญ - ํŠœํ”Œ

๋ฌธ์ œ ํ’€์ด ์–ธ์–ด Kotlin ์ฝ”๋“œ class Solution { fun solution(s: String): IntArray { val string = s.slice(2 until s.length - 2) val array = string.split("},{") val sortedArray = array.sortedBy { it.length } val answer = mutableListOf() for (e in sortedArray) { val splitString = e.split(',') for (num in splitString) { if (answer.contains(num.toInt()).not()) answer.add(num.toInt()) } } return answer.toIntArray..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[BFS][Kotlin] 2021 ์นด์นด์˜ค ์ฑ„์šฉ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ - ๊ฑฐ๋ฆฌ๋‘๊ธฐ ํ™•์ธํ•˜๊ธฐ

๋ฌธ์ œ ํ’€์ด ์–ธ์–ด Kotlin ์ฝ”๋“œ import java.util.* class Solution { fun solution(places: Array): IntArray { val answer = mutableListOf() val size = places.size for (place in places) { var check = 0 for (i in 0 until size) { for (j in 0 until size) { if (place[i][j] == 'P') { if (bfs(place, i, j, size).not()) { check = 1 break } } } if (check == 1) { break } } if (check == 1) answer.add(0) else answer..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/String

[๋ฌธ์ž์—ด / Kotlin] 2019 KAKAO BLIND RECRUITMENT - ์˜คํ”ˆ์ฑ„ํŒ…๋ฐฉ

๋ฌธ์ œ ํ’€์ด ์–ธ์–ด Kotlin ์ฝ”๋“œ class Solution { fun solution(record: Array): Array { val history = arrayListOf() val name = mutableMapOf() val result = arrayListOf() for (e in record.iterator()) { val act = e.split(" ") when (act[0]) { "Enter" -> { name[act[1]] = act[2] history.add(Pair(act[0], act[1])) } "Leave" -> { history.add(Pair(act[0], act[1])) } "Change" -> { name[act[1]] = act[2] } } } history.map ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Implementation

[๊ตฌํ˜„ / Kotlin] 2022 SK ICT Family ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ ์ฑŒ๋ฆฐ์ง€ - 2๋ฒˆ

์šฐ์„  ๊ฐ„๋งŒ์— ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ์ ‘ํ–ˆ๋˜ ํ„ฐ๋ผ ๋งŽ์ด ์–ด๋ ค์› ๋‹ค. FE / APP ๊ฐœ๋ฐœ ์ง๊ตฐ์„ ์„ ํƒํ–ˆ๊ณ  ์ด 4๋ฌธ์ œ๊ฐ€ ๋‚˜์™”๋Š”๋ฐ DP 1, ๊ตฌํ˜„ 1, ๊ทธ๋ž˜ํ”„ 2 ์ด๋ ‡๊ฒŒ ๋‚˜์™”๋‹ค. ์‚ฌ์ •์ด ์žˆ์–ด์„œ 30๋ถ„ ์ •๋„ ๋’ค๋Šฆ๊ฒŒ ์ฐธ์„ํ–ˆ๊ณ  2์‹œ๊ฐ„ ๋™์•ˆ 2๋ฒˆ ํ•˜๋‚˜๋งŒ ํ’€์—ˆ๋‹ค. ์‹œ๊ฐ„์ด ๋” ์žˆ์—ˆ์–ด๋„ ๋‹ค๋ฅธ ๋ฌธ์ œ๋ฅผ ํ’€์ง€ ๋ชปํ–ˆ์„ ๊ฒƒ์ด๋‹ค. ์•ˆ๋“œ๋กœ์ด๋“œ ๊ณต๋ถ€ ๋•Œ๋ฌธ์— ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์†Œํ™€ํžˆ ํ–ˆ๋Š”๋ฐ ์•ž์œผ๋กœ๋Š” ํŽธ์‹ํ•˜์ง€ ๋ง๊ณ  ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ๊พธ์ค€ํžˆ ํ’€์–ด์•ผ๊ฒ ๋‹ค. ๋ฌธ์ œ ๋ฌธ์ œ ์ €์ž‘๊ถŒ์— ์˜ํ•ด์„œ ์บก์ณ๋Š” ํ•˜์ง€ ๋ชปํ–ˆ๊ณ  ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜์ž๋ฉด ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์„ ์žฌ์ •๋ ฌํ•˜๋Š” ๋ฌธ์ œ์˜€๋‹ค. ์‹œ๊ณ„ ๋ฐฉํ–ฅ, ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ์ด 2๊ฐ€์ง€์˜ ๋ฐฉํ–ฅ์ด ์žˆ์—ˆ์œผ๋ฉฐ ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋Š” ํ™€์ˆ˜์™€ ์ง์ˆ˜๊ฐ€ ์กด์žฌํ–ˆ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ ์ด 4๊ฐ€์ง€ ๊ฒฝ์šฐ ๋Œ€ํ•ด ๋ฐฐ์—ด์„ ์žฌ์ •๋ ฌํ•˜๋Š” ๋ฌธ์ œ์˜€๋‹ค. ํ’€์ด ์–ธ์–ด Kotlin ์ฝ”๋“œ class Solution ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/String

[๋ฌธ์ž์—ด / Kotlin] 2020 KAKAO BLIND RECRUITMENT - ๋ฌธ์ž์—ด ์••์ถ•

ํ’€์ด ์–ธ์–ด Kotlin ์ฝ”๋“œ fun solution(s: String): Int { var minLength = s.length for (i in 0 until s.length / 2) { var subString = s.slice(0..i) var answer = "" var cnt = 1 var last = 0 for (j in i + 1 until s.length - i step i + 1) { // ๋งˆ์ง€๋ง‰ Index ๋ฅผ ์ €์žฅํ•œ๋‹ค. last = j + i + 1 // ๊ฐ™์€ SubString ์ธ ๊ฒฝ์šฐ ์ด๋ฅผ ์นด์šดํŠธํ•œ๋‹ค. if (subString == s.slice(j..j + i)) cnt += 1 // ๋‹ค๋ฅธ SubString ์ธ ๊ฒฝ์šฐ else { if (cnt > 1) { // ์ˆซ์ž + SubStri..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Two Pointer

[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 1644 - ์†Œ์ˆ˜์˜ ์—ฐ์†ํ•ฉ

๋ฌธ์ œ ํ•˜๋‚˜ ์ด์ƒ์˜ ์—ฐ์†๋œ ์†Œ์ˆ˜์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋Š” ์ž์—ฐ์ˆ˜๋“ค์ด ์žˆ๋‹ค. ๋ช‡ ๊ฐ€์ง€ ์ž์—ฐ์ˆ˜์˜ ์˜ˆ๋ฅผ ๋“ค์–ด ๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 3 : 3 (ํ•œ ๊ฐ€์ง€) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (์„ธ ๊ฐ€์ง€) 53 : 5+7+11+13+17 = 53 (๋‘ ๊ฐ€์ง€) ํ•˜์ง€๋งŒ ์—ฐ์†๋œ ์†Œ์ˆ˜์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์—†๋Š” ์ž์—ฐ์ˆ˜๋“ค๋„ ์žˆ๋Š”๋ฐ, 20์ด ๊ทธ ์˜ˆ์ด๋‹ค. 7+13์„ ๊ณ„์‚ฐํ•˜๋ฉด 20์ด ๋˜๊ธฐ๋Š” ํ•˜๋‚˜ 7๊ณผ 13์ด ์—ฐ์†์ด ์•„๋‹ˆ๊ธฐ์— ์ ํ•ฉํ•œ ํ‘œํ˜„์ด ์•„๋‹ˆ๋‹ค. ๋˜ํ•œ ํ•œ ์†Œ์ˆ˜๋Š” ๋ฐ˜๋“œ์‹œ ํ•œ ๋ฒˆ๋งŒ ๋ง์…ˆ์— ์‚ฌ์šฉ๋  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, 3+5+5+7๊ณผ ๊ฐ™์€ ํ‘œํ˜„๋„ ์ ํ•ฉํ•˜์ง€ ์•Š๋‹ค. ์ž์—ฐ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์ž์—ฐ์ˆ˜๋ฅผ ์—ฐ์†๋œ ์†Œ์ˆ˜์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค...

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Two Pointer

[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 1806 - ๋ถ€๋ถ„ ํ•ฉ

๋ฌธ์ œ 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ๊ธธ์ด N์งœ๋ฆฌ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜์—ด์—์„œ ์—ฐ์†๋œ ์ˆ˜๋“ค์˜ ๋ถ€๋ถ„ํ•ฉ ์ค‘์— ๊ทธ ํ•ฉ์ด S ์ด์ƒ์ด ๋˜๋Š” ๊ฒƒ ์ค‘, ๊ฐ€์žฅ ์งง์€ ๊ฒƒ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N (10 โ‰ค N < 100,000)๊ณผ S (0 < S โ‰ค 100,000,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜์—ด์˜ ๊ฐ ์›์†Œ๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ์œผ๋ฉฐ, 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ์ตœ์†Œ์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์ผ ๊ทธ๋Ÿฌํ•œ ํ•ฉ์„ ๋งŒ๋“œ๋Š” ๊ฒƒ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์•ž์„  2๋ฌธ์ œ์™€ ๋‹ค๋ฅด๊ฒŒ ์ •๋ ฌ์„ ํ•  ํ•„์š”๊ฐ€ ์—†๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ฃผ์–ด์ง„ ๋ฐฐ์—ด ์ž์ฒด์—์„œ์˜ ๊ฐ€์žฅ ์ž‘์€ ๊ธธ์ด์˜ ๋ถ€๋ถ„ ํ•ฉ์„ ์ฐพ์•„์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค. 1. le..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Two Pointer

[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 2470 - ๋‘ ์šฉ์•ก

๋ฌธ์ œ KOI ๋ถ€์„ค ๊ณผํ•™์—ฐ๊ตฌ์†Œ์—์„œ๋Š” ๋งŽ์€ ์ข…๋ฅ˜์˜ ์‚ฐ์„ฑ ์šฉ์•ก๊ณผ ์•Œ์นผ๋ฆฌ์„ฑ ์šฉ์•ก์„ ๋ณด์œ ํ•˜๊ณ  ์žˆ๋‹ค. ๊ฐ ์šฉ์•ก์—๋Š” ๊ทธ ์šฉ์•ก์˜ ํŠน์„ฑ์„ ๋‚˜ํƒ€๋‚ด๋Š” ํ•˜๋‚˜์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ ธ์žˆ๋‹ค. ์‚ฐ์„ฑ ์šฉ์•ก์˜ ํŠน์„ฑ๊ฐ’์€ 1๋ถ€ํ„ฐ 1,000,000,000๊นŒ์ง€์˜ ์–‘์˜ ์ •์ˆ˜๋กœ ๋‚˜ํƒ€๋‚ด๊ณ , ์•Œ์นผ๋ฆฌ์„ฑ ์šฉ์•ก์˜ ํŠน์„ฑ๊ฐ’์€ -1๋ถ€ํ„ฐ -1,000,000,000๊นŒ์ง€์˜ ์Œ์˜ ์ •์ˆ˜๋กœ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๊ฐ™์€ ์–‘์˜ ๋‘ ์šฉ์•ก์„ ํ˜ผํ•ฉํ•œ ์šฉ์•ก์˜ ํŠน์„ฑ๊ฐ’์€ ํ˜ผํ•ฉ์— ์‚ฌ์šฉ๋œ ๊ฐ ์šฉ์•ก์˜ ํŠน์„ฑ๊ฐ’์˜ ํ•ฉ์œผ๋กœ ์ •์˜ํ•œ๋‹ค. ์ด ์—ฐ๊ตฌ์†Œ์—์„œ๋Š” ๊ฐ™์€ ์–‘์˜ ๋‘ ์šฉ์•ก์„ ํ˜ผํ•ฉํ•˜์—ฌ ํŠน์„ฑ๊ฐ’์ด 0์— ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์šฉ์•ก์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ฃผ์–ด์ง„ ์šฉ์•ก๋“ค์˜ ํŠน์„ฑ๊ฐ’์ด [-2, 4, -99, -1, 98]์ธ ๊ฒฝ์šฐ์—๋Š” ํŠน์„ฑ๊ฐ’์ด -99์ธ ์šฉ์•ก๊ณผ ํŠน์„ฑ๊ฐ’์ด 98์ธ ์šฉ์•ก์„ ํ˜ผํ•ฉํ•˜๋ฉด ํŠน์„ฑ๊ฐ’์ด -1์ธ ์šฉ์•ก์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๊ณ , ์ด ์šฉ์•ก..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Two Pointer

[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 3273 - ๋‘ ์ˆ˜์˜ ํ•ฉ

๋ฌธ์ œ n๊ฐœ์˜ ์„œ๋กœ ๋‹ค๋ฅธ ์–‘์˜ ์ •์ˆ˜ a1, a2, ..., an์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ์ˆ˜์—ด์ด ์žˆ๋‹ค. ai์˜ ๊ฐ’์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 1000000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ž์—ฐ์ˆ˜ x๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ai + aj = x (1 โ‰ค i < j โ‰ค n)์„ ๋งŒ์กฑํ•˜๋Š” (ai, aj)์Œ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด์˜ ํฌ๊ธฐ n์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” ์ˆ˜์—ด์— ํฌํ•จ๋˜๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์…‹์งธ ์ค„์—๋Š” x๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค n โ‰ค 100000, 1 โ‰ค x โ‰ค 2000000) ์ถœ๋ ฅ ๋ฌธ์ œ์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ์Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ ์ ‘ํ–ˆ์„ ๋•Œ๋Š” ์ฝ”ํ‹€๋ฆฐ์˜ find๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ๋‹ค. ์šฐ์„  ์ž…๋ ฅ ๋ฐ›์€ ๋ฐฐ์—ด์„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๊ณ , ๋งจ ์•ž๋ถ€ํ„ฐ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•˜๋ฉด์„œ ์ž…๋ ฅ๋ฐ›์€ x - ..

kodo_o
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก (2 Page)